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

Reconfiguration algorithms for synchronous communication on switch based degradable arrays

PARALLEL COMPUTING 2022年 111卷

作者： Wu, Yalan Wu, Jigang Liu, Peng Han, Yinhe Srikanthan, Thambipillai Guangdong Univ Technol Sch Comp Sci & Technol Guangzhou 510006 Guangdong Peoples R China Chinese Acad Sci Inst Comp Technol Beijing 100190 Peoples R China Nanyang Technol Univ Sch Comp Sci & Engn Singapore 639798 Singapore

Synchronous communication is one of the most important issues in high performance architectures for large scale of parallel computing, such as matrix computing, image processing, etc. mesh-connected processor array is characteristic of synchronous communication due to the same length of the interconnects between the neighboring processing elements (PEs) in rows/columns. But long interconnects caused by faulty PEs clearly impact the synchronous communication between the adjacent rows/columns. If long interconnects exist between two adjacent rows, we say that a synchronous communication delay is caused. This paper contributes algorithms to construct logical arrays with synchronous communication in a given host array. Specifically, an algorithm for synchronous communication array (ASCA) is firstly presented, to construct a maximum logical array with synchronous communication. When all of the long interconnects are independent each other, the proposed algorithm is proved to be optimal. After that, two heuristic algorithms are also proposed, to construct a logical array with given size, by integrating the proposed ASCA and two exclusion schemes. The proposed two exclusion schemes are based on strategies of divide-and-conquer and the longest logical column first, respectively. In addition, the lower bound of synchronous communication delay for a logical array is calculated by an algorithm also developed in this paper, in order to evaluate the synchronous performance of reconfiguration algorithms. Simulation results show that, the proposed two heuristic algorithms have their own advantages for different cases. The synchronous communication delay of the logical arrays is significantly reduced, and it is very close to the lower bound for the cases of small fault density and larger exclusion rate. For 32 x 32 physical arrays with exclusion rates that are larger than 15%, the synchronous communication delay of logical array is reduced from 11.09 to 6.97, which is more closer t

关键词： mesh-connected processor array Reconfiguration algorithm Fault-tolerance Synchronous communication

来源：评论

学校读者我要写书评

暂无评论

A Novel On-Chip Interconnection Topology for mesh-connected processor arrays

A Novel On-Chip Interconnection Topology for Mesh-Connected ...

引用

IEEE Annual Symposium on VLSI (ISVLSI)

作者： Wang, Xiaofang Villanova Univ Dept Elect & Comp Engn 800 Lancaster Ave Villanova PA 19085 USA

ISBN: (纸本)9780769540764

Prior studies on packet-switching on-chip networks have primarily focused on the microarchitecture of the router to reduce the communication latency. In this paper, we propose a novel interconnection topology for mesh-connected processor arrays. By sharing routers among PEs and PEs among routers, our network significantly reduces the average hop count for a packet, thereby reducing the network latency and improving the throughput of the network. The interconnection network also requires less area compared to the conventional mesh organization, leaving more resources for the computing fabric. Extensive simulation results show that the proposed network reduces the network latency by up to 50.3% for a multiprocessor with 64 PEs.

关键词： hop count mesh organization mesh-connected processor array microprocessor chips multiprocessor multiprocessor interconnection networks network latency network router network routing network throughput network topology on-chip interconnection topology processing element

来源：评论

学校读者我要写书评

暂无评论

A graph-theoretic approach to minimizing the number of dangerous processors in fault-tolerant mesh-connected processor arrays

引用

IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS 2001年第11期E84D卷 1462-1470页

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

First, we give a graph-theoretic formalization for the spare assignment problems for two cases of reconfiguring N x N mesh-connected processor arrays with spares on a diagonal line in the array or two orthogonal lines at the edges of the array. Second, we discuss the problems for minimizing the numbers of "dangerous processors" for the cases. Here, a dangerous processor is a nonfaulty one for which there remains no spare processor to be assigned if it becomes faulty, without modifying the spare assignments to other faulty processors. The problem for the latter case, originally presented by Melhem [1], [2], has already been discussed and solved by the O(N-2) algorithm in [3], but it's procedure is very complicated. Using the above graph-theoretic formalization, we give efficient plain algorithms for minimizing the numbers of dangerous processors by which the problems for both the cases can be solved in O(N) time.

关键词： fault-tolerance reconfiguration algorithm dangerous processor mesh-connected processor array graph-theoretic approach

来源：评论

学校读者我要写书评

暂无评论

INDEXING FUNCTIONS AND TIME LOWER BOUNDS FOR SORTING ON A mesh-connected COMPUTER

引用

DISCRETE APPLIED MATHEMATICS 1992年第2期36卷 141-152页

作者： HAN, YJ IGARASHI, Y TRUSZCZYNSKI, M GUNMA UNIV DEPT COMP SCI KIRYU GUNMA 376 JAPAN

We introduce a parameter of indexing functions and show its relation to lower bounds for sorting algorithms on mesh-connected computers that follow from the Chain Theorem. We give lower and upper bounds for the parameter. Conclusions from our results are: (1) no matter what indexing function is used any sorting algorithm must execute 2.27n + THETA(1) steps;(2) the best lower bound true for all indexing functions that we can hope to prove by the Chain Theorem argument is 2.5n + THETA(1).

关键词： SORTING PARALLEL COMPUTATION mesh-connected processor array LOWER BOUND COMPLEXITY INDEXING SCHEME INDEXING FUNCTION

来源：评论

学校读者我要写书评

暂无评论

TOPOLOGICAL NUMBERING OF FEATURES ON A mesh

引用

ALGORITHMICA 1991年第5期6卷 762-769页

作者： ATALLAH, MJ HAMBRUSCH, SE TEWINKEL, LE 1. Department of Computer Sciences Purdue University 47907 West Lafayette IN USA

Assume we are given an n x n binary image containing horizontally convex features;i.e., for each feature, each of its row's pixels form an interval on that row. In this paper we consider the problem of assigning topological numbers to such features, i.e., assign a number to every feature f so that all features to the left of f in the image have a smaller number assigned to them. This problem arises in solutions to the stereo matching problem. We present a parallel algorithm to solve the topological numbering problem in O(n) time on an n x n mesh of processors. The key idea of our solution is to create a tree from which the topological numbers can be obtained even though the tree does not uniquely represent the "to the left of" relationship of the features.

关键词： IMAGE PROCESSING mesh-connected processor array PARALLEL COMPUTATION STEREO MATCHING TOPOLOGICAL SORTING TREE COMPUTATION

来源：评论

学校读者我要写书评

暂无评论

TIME LOWER BOUNDS FOR SORTING ON MULTIDIMENSIONAL mesh-connected processor arrayS

引用

INFORMATION PROCESSING LETTERS 1990年第5期33卷 233-238页

作者： HAN, Y IGARASHI, Y GUNMA UNIV DEPT COMP SCI KIRYU GUNMA 376 JAPAN

The authors of the present paper have shown that 2.2247n steps are a time lower bound independent of indexing schemes for sorting n super(2) items on the n x n mesh-connected model. This lower bound has recently been improved to 2.27n steps. The existence of a poor indexing scheme with 4n - 2 square root 2n - 3 time lower bound has also been shown. These results have been obtained using a new technique called the chain argument. In this paper the authors develop the chain argument in order that they can apply its extended version to derive nontrivial lower bounds for sorting. They show a theorem that gives a relation between computing time for sorting n super(d) items and the number of processors in a certain region of the mesh-connected model. They can numerically calculate the best lower bound obtainable from the theorem.

关键词： Sorting parallel computation time lower bound mesh-connected processor array

来源：评论

学校读者我要写书评

暂无评论

A SIMPLE SYSTOLIC METHOD TO FIND ALL BRIDGES OF AN UNDIRECTED GRAPH

引用

PARALLEL COMPUTING 1989年第1期12卷 107-111页

作者： SCHIMMLER, M SCHRODER, H AUSTRALIAN NATL UNIV DEPT ENGN PHYSCANBERRAACT 2601AUSTRALIA

An algorithm to find all bridges of an undirected graph on a mesh-connected processor array is presented. Asymptotically it has the same complexity in terms of time and space as the best previous known algorithm, the one of Atallah and Kosaraju. But it has a significantly simpler structure and therefore, it gains a constant factor of about two in time.

关键词： bridges in graphs complexity mesh-connected processor array systolic algorithm transitive closure

来源：评论

学校读者我要写书评

暂无评论

THE INSTRUCTION SYSTOLIC array - A PARALLEL ARCHITECTURE FOR VLSI

引用

INTEGRATION-THE VLSI JOURNAL 1986年第1期4卷 65-74页

作者： LANG, HW UNIV KIEL INST INFORMAT & PRAKT MATHD-2300 KIEL 1FED REP GER

A new parallel architecture is presented that is more flexible than the systolic array: the Instruction Systolic array (ISA). In the ISA the instructions (instead of data, as in a systolic array) are pumped through an array of processors. While systolic arrays are special purpose architectures, the ISA is more universal: It is capable of executing different programs. The Instruction Systolic array is well suited for implementation in VLSI technology.

关键词： Computer architectures mesh-connected processor array systolic array VLSI

来源：评论

学校读者我要写书评

暂无评论

GRAPH PROBLEMS ON A mesh-connected processor array

引用

JOURNAL OF THE ACM 1984年第3期31卷 649-667页

作者： ATALLAH, MJ KOSARAJU, SR JOHNS HOPKINS UNIV BALTIMOREMD 21218

Algorithms that run in O(n) steps are given for solving a number of graph problems on an n multiplied by n array of processors. The problems considered include: finding the bridges and articulation points of an undirected graph, finding the length of a shortest cycle, finding a minimum spanning tree, and a number of other problems.

关键词： adjacency matrix breadth-first search graph algorithms mesh-connected processor array parallel computations

来源：评论

学校读者我要写书评

暂无评论

SYSTOLIC SORTING ON A mesh-connected NETWORK

引用

IEEE TRANSACTIONS ON COMPUTERS 1985年第7期34卷 652-658页

作者： LANG, HW SCHIMMLER, M SCHMECK, H SCHRODER, H Institut für Informatik und Praktische Mathematik Christian-Albrechts-Universität Kiel

A parallel algorithm for sorting n data items in O(n) steps is presented. Its simple structure and the fact that it needs local communication only make it suitable for an implementation in VLSI technology. The algorithm is based on a merge algorithm that merges four subfiles stored in a mesh-connected processor array. This merge algorithm is composed of the perfect shuffle and odd-even-transposition sort. For the VLSI implementation a systolic version of the algorithm is presented. The area and time complexities for a bit-serial and a bit-parallel version of this implementation are analyzed.

关键词： Odd-even-transposition sort VLSI algorithms VLSI complexity mesh-connected processor array perfect shuffle sorting systolic array

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：