检索结果-内蒙古大学图书馆

Self-reconfiguring of 1 1/2-track-switch mesh arrays with spares on one row and one column by simple built-in circuit

引用

IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS 2004年第10期E87D卷 2318-2328页

作者： Takanami, I Ichinoseki Natl Coll Technol Ichinoseki 0218511 Japan

We present a built-in self-reconfiguring system for a mesh-connected processor array where faulty processor elements are compensated for by spare processing elements located in one row and one column. It has advantages in that the number of spare processing elements is small and additional control circuits and networks for changing interconnections of processing elements is so simple that hardware overhead for reconfiguration is also small. First, to indicate the motivation to the proposed reconfiguration scheme, we briefly describe other schemes with the same number of spares as that of the proposed scheme where faulty processing elements are replaced using straight shifts toward spares, and compare their reconfiguration probabilities to each other. Then, we show that a variant of the proposed scheme has the highest probability. Next, we present a built-in self-reconfiguring system for the scheme and formally prove that it works correctly. It can automatically replace faulty processors by spare processors on detecting faults of processors.

关键词： mesh array fault-tolerance reconfiguration self-repair built-in circuit

来源：评论

学校读者我要写书评

暂无评论

SOME NEW DESIGNS OF 2-D array FOR MATRIX MULTIPLICATION AND TRANSITIVE CLOSURE

引用

IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS 1995年第4期6卷 351-362页

作者： TSAY, JC CHANG, PY Institute of Computer Science and Information Engineering College of Engineering National Chiao Tung University Hsinchu Taiwan

In this paper, we present some new regular iterative algorithms for matrix multiplication and transitive closure. With these algorithms, by spacetime mapping the 2-D arrays with 2N-1 and [(3N-1)/2] execution times for matrix multiplication can be obtained, Meanwhile, we can derive a 2-D array with 4N-2 execution time for transitive closure based on the sequential Warshall-Floyd algorithm. All these new 2-D arrays for matrix multiplication and transitive closure have the advantages of faster and more regular than other previous designs.

关键词： ALGORITHM MAPPING MATRIX MULTIPLICATION mesh array SYSTOLIC array SPHERICAL array TRANSITIVE CLOSURE VLSI

来源：评论

学校读者我要写书评

暂无评论

Scheduling tree dags on parallel architectures

引用

ALGORITHMICA 1996年第4期15卷 373-396页

作者： Kalpakis, K Yesha, Y Computer Science Department University of Maryland Baltimore County Baltimore USA

We provide optimal within a constant explicit upper bounds on the makespan of schedules for tree-structured programs on mesh arrays of processors, and provide polynomial-time algorithms to find schedules with makespan matching these bounds. In particular, we show how to find, in polynomial time, a (nonpreemptive) schedule for a binary tree dag with n unit execution time tasks and height h on a d-dimensional mesh array with m processors and links of unit bandwidth and unit propagation delay whose makespan is O(n/m + n(l/(d+1)) + h), i.e., optimal within a constant factor. Further, we extend these schedules to bounded degree forest dags with arbitrary positive integer execution time tasks and to meshes when the propagation delay of all the links is an arbitrary positive integer. Thus, we provide a polynomial-time approximation algorithm for an NP-hard problem, with a performance ratio that is a constant. We also show how to schedule tree dags on any parallel architecture that satisfies certain natural, not very restrictive, conditions that are satisfied by most parallel architectures used in practice. Let epsilon be a fixed positive real number. We provide polynomial time computable schedules for binary tree dags with n unit execution time tasks and height h is not an element of (g(n)n(-epsilon), g(n) log n) on any parallel architecture satisfying those conditions, with unit bandwidth and unit propagation delay Links, with optimal up to a constant makespan O(g(n) + h), where g is a function that depends only on that architecture. The number of processors used is optimal within a constant factor if h less than or equal to g(n)n(-epsilon), and is optimal within an O(log n) factor if h greater than or equal to g(n) log n. As an example, for hypercube and complete binary tree architectures, we achieve optimal within a constant makespan O(h) when h = Omega(log(2) n), using an optimal within an O (log n) factor number of processors. Further, we extend these schedules to the

关键词： multiprocessing parallel computation parallel architectures communication delay scheduling tree dags linear array mesh array tree decomposition

来源：评论

学校读者我要写书评

暂无评论

Upper and lower bounds on the makespan of schedules for tree dags on linear arrays

引用

ALGORITHMICA 1999年第2期23卷 159-179页

作者： Kalpakis, K Yesha, Y Univ Maryland Baltimore Cty Dept Comp Sci & Elect Engn Baltimore MD 21250 USA Univ Maryland Inst Adv Comp Studies College Pk MD 20742 USA

We find, in polynomial time, a schedule for a complete binary tree directed acyclic graph (dag) with n unit execution time tasks on a linear array whose makespan is optimal within a factor of 1 + o(1). Further, given a binary tree dag T with n tasks and height h, we find, in polynomial time, a schedule for T on a linear array whose makespan is optimal within a factor of 5 + o(1). On the other hand, we prove that explicit lower and upper bounds on the makespan of optimal schedules of binary tree dags on linear arrays differ at least by a factor of 1 + root 2/2. We also find, in polynomial time, schedules for bounded tree dags with n unit execution time tasks, degree d, and height h is an element of o(n(1/2)) boolean OR omega(n(1/2)) on a linear array which are optimal within a factor of 1 + o(1), this time under the assumption of links with unlimited bandwidth. Finally, we compute an improved upper bound on the makespan of an optimal schedule for a tree dag on the architecture independent model of Papadimitriou and Yannakakis [14], provided that its height is not too large.

关键词： multiprocessing parallel computation parallel architectures communication delay scheduling tree dags linear array mesh array tree decomposition

来源：评论

学校读者我要写书评

暂无评论

A PARALLEL ALGORITHM FOR FINDING THE MAXIMUM VALUE

引用

PARALLEL COMPUTING 1989年第1期10卷 101-108页

作者： HORIGUCHI, S MIRANKER, WL IBM Thomas J. Watson Research Center Yorktown Heights NY 10598 U.S.A.

A new parallel algorithm for finding the maximum value of a data set is proposed. Execution times are investigated by taking into account the effect of the overhead time of communication for four kinds of interconnection networks; cube connection array, linear array, mesh array, and three-dimensional mesh array. The optimal numbers of processors are derived in the case where the number of processors is less than the number of data. Those are O (N 1 2 ), O (N 2 3 ), O (N 3 4 ), and O (N) , respectively, for linear array, mesh array, three-dimensional mesh array, and cube-connected arrays.

关键词： cube-connection array execution time investigation finding the maximum value interconnection networks linear array mesh array Parallel algorithm three-dimensional mesh array

来源：评论

学校读者我要写书评

暂无评论

Restructuring mesh-connected processor arrays with spares on four sides by orthogonal side rotation 23

Restructuring mesh-connected processor arrays with spares on...

引用

23rd IEEE Pacific Rim International Symposium on Dependable Computing (PRDC)

作者： Takanami, Itsuo Fukushi, Masaru Yamaguchi Univ Grad Sch Sci & Technol Innovat Tokiwadai 2-16-1 Ube Yamaguchi Japan

ISBN: (纸本)9781538657003

An array with spares on four sides and the restructuring algorithm for it were proposed in [1]. However, the restructuring algorithm described in [1] is too complicated to be realized in hardware. Here, we propose a method to improve such the situation. First, the array is considered to be an (N + 2) x (N + 2) array if four PEs are added to the four comers of the array and the spares are included. The (N+ 2) x (N+ 2) array is divided into four subarrays, each of which is of size (N/2 + 1) x(N/2 + 1), and the orthogonal side rotation introduced here is individually applied to each subarray. The reliabilities are given by computer simulation. They fairly increase, comparing with those in [1].

关键词： fault-tolerance mesh array single track switch restructuring

来源：评论

学校读者我要写书评

暂无评论

Degradable restructuring of mesh-connected processor arrays with spares on orthogonal sides 23

Degradable restructuring of mesh-connected processor arrays ...

引用

23rd IEEE Pacific Rim International Symposium on Dependable Computing (PRDC)

作者： Takanami, Itsuo Fukushi, Masaru Yamaguchi Univ Grad Sch Sci & Technol Innovat Tokiwadai 2-16-1 Ube Yamaguchi Japan

ISBN: (纸本)9781538657003

We present a restructuring method to apply a degradation approach to mesh-connected processor arrays with spare processing elements on the orthogonal sides of the arrays. An array with faulty processing elements is restructured by shifting healthy processing elements toward faulty processing elements using single track switches. First, an algorithm which satisfies the necessary and sufficient condition (called a restructurable condition) that an array is restructured so that its logical size is kept is briefly explained. Next, a method that if the array does not satisfy the restructurable condition, its rows and/ or columns are functionally deleted so that the subarray with the remaining rows and columns satisfies the restructurable condition is presented. Finally, the simulation results are shown.

关键词： fault tolerance mesh array single track switch restructuring degradation

来源：评论

学校读者我要写书评

暂无评论

A Built-in Circuit for Self-Repairing mesh-Connected Processor arrays with Spares on Diagonal 22

A Built-in Circuit for Self-Repairing Mesh-Connected Process...

引用

IEEE 22nd Pacific Rim International Symposium on Dependable Computing (PRDC)

作者： Takanami, Itsuo Fukushi, Masaru Yamaguchi Univ Grad Sch Sci & Technol Innovat Tokiwadai 2-16-1 Ube Yamaguchi Japan

ISBN: (纸本)9781509056521

We present a built-in self-restructuring system for a mesh-connected processor array where faulty processing elements are compensated for by spare processing elements located on a diagonal. First, an algorithm for restructuring the array with faulty processing elements is presented. The reliability of the system is analyzed by simulation. It is compared with that of an array with spare processing elements on a line at the edge of the array which has the same number of spare processing elements as that in the proposed array. It is shown that the former is fairly higher than the latter. Next, a logical circuit realizing the algorithm is presented. The circuit controls interconnection of processing elements and is so simple that its hardware overhead is small. The proposed system is effective for the case where each processing element is fairly reliable and the small number of spares will be enough for retaining the reliability of an array so high under small hardware overhead. It is also effective in enhancing especially the run-time reliability of a processor array.

关键词： fault-tolerance mesh array self-repair built-in cirucuit

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：