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

A unified formulation of honeycomb and diamond networks

IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS 2001年第1期12卷 74-80页

作者： Parhami, B Kwai, DM Univ Calif Santa Barbara Dept Elect & Comp Engn Santa Barbara CA 93106 USA Worldwide Semicond Corp Hsinchu Taiwan

Honeycomb and diamond networks have been proposed as alternatives to mesh and torus architectures for parallel processing. When wraparound links are included in honeycomb and diamond networks. the resulting structures can be viewed as having been derived via a systematic pruning scheme applied to the links of 2D and 3D tori, respectively. The removal of links, which is performed along a diagonal pruning direction, preserves the network's node-symmetry and diameter. while reducing its implementation complexity and VLSI layout area. In this paper, we prove that honeycomb and diamond networks are special subgraphs of complete 2D and 3D tori, respectively. and show this viewpoint to hold important implications for their physical layouts and routing schemes. Because pruning reduces the node degree without increasing the network diameter, the pruned networks have an advantage when the degree-diameter product is used as a figure of merit. Additionally, if the reduced node degree is used as an opportunity to increase the link bandwidths to equalize the costs of pruned and unpruned networks, a gain in communication performance may result.

关键词： Cayley graph k-ary n-cube network topology processor array pruned torus network VLSI layout

来源：评论

学校读者我要写书评

暂无评论

Algorithm transformations for the data broadcast elimination method

引用

INTERNATIONAL JOURNAL OF COMPUTER MATHEMATICS 2000年第4期73卷 433-461页

作者： Gusev, M Evans, DJ Nottingham Trent Univ Dept Comp Nottingham England Univ Kiril I Metofif Skopje PMF Inst Informat YU-91000 Skopje North Macedonia Loughborough Univ Technol Parallel Algorithms Res Ctr Loughborough LE11 3TU Leics England

VLSI technology has had tremendous success in revolutionizing computer design with processor arrays. Local communication and interconnection is a constraint that dictates the design of processor arrays. The shared bus and global access to memory are now no longer used, since they lower the speed. Consequently, parallel algorithms must be designed according to these constraints. One of the problems that must be resolved for the above mentioned constraints is data broadcast elimination. Algorithms must be transformed into a form that uses data propagation instead of data broadcast. Here systems of affine recurrence equations are analyzed and data broadcast is defined in context of the definition of data dependence and affine recurrence equations. A method for data broadcast elimination is introduced in [I] and expands the system of affine recurrence equations into new recurrence equations, that define data propagation and eliminates the data dependences where data broadcast occurs. Parallel algorithms are usually given as a set of similar tasks repetitively performed on different data. The iteration form of presenting the algorithms is most common. Several techniques are introduced to transform the algorithm to a single assignment form of recurrence equations. Some improvements of these techniques are presented to make the application of the data broadcast elimination method easier and more straight forward. The presented techniques are classified as the transformation of iterative algorithms to a recurrence form, the transformation of recurrence form to a single assignment form, and fulfilling the index forms of the algorithms. A system of affine recurrence equations with the data broadcast property is always obtained by applying these procedures. The method of data broadcast elimination successfully transforms this system of affine recurrence equations into a system of uniform recurrence equations which can be used for parallel implementation on VLSI processor array

关键词： VLSI technology processor array systolic algorithm data broadcast elimination

来源：评论

学校读者我要写书评

暂无评论

SPEED-UP OF SCALABLE ITERATIVE LINEAR SOLVERS IMPLEMENTED ON AN array OF TRANSPUTERS

引用

PARALLEL COMPUTING 1995年第4期21卷 669-682页

作者： ASENOV, A REID, D BARKER, JR Nanoelectronics Research Centre Department of Electronics and Electrical Engineering University of Glasgow Glasgow G12 8QQ UK

A detailed model is presented for the speed-up of parallel linear iterative solvers. The mapping of a topologically rectangular discrete grid onto a processor array of N x M transputers leads to step-like behaviour in the local communication and calculation time. This results in a typical oscillatory behaviour of 'speed-up' when problem sizes are increased monotonously. The theory is compared with experimental results obtained on a Parsytec Super Cluster Model 64 using a black-red SOR algorithm coded in 3L Parallel Fortran.

关键词： PARALLEL ITERATIVE SOLVERS processor array TRANSPUTERS SPEED-UP PREDICTION

来源：评论

学校读者我要写书评

暂无评论

An improved generalization of mesh-connected computers with multiple buses

引用

IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS 2001年第3期12卷 293-305页

作者： Pan, Y Zheng, SQ Li, KQ Shen, H Georgia State Univ Dept Comp Sci Atlanta GA 30303 USA Univ Texas Dept Comp Sci Richardson TX 75083 USA SUNY Albany Dept Math & Comp Sci New Paltz NY 12561 USA Griffith Univ Sch Comp & Informat Technol Nathan Qld 4111 Australia

Mesh-connected computers (MCCs) are a class of important parallel architectures due to their simple and regular interconnections. However, their performances are restricted by their large diameters. Various augmenting mechanisms have been proposed to enhance the communication efficiency of MCCs. One major approach is to add nonconfigurable buses for improved broadcasting. A typical example is the mesh-connected computer with multiple buses (MMB). We propose a new class of generalized MMBs, the improved generalized MMBs (IMMBs). We compare IMMBs with MMBs and a class of previously proposed generalized MMBs (GMMBs). We show the power of IMMBs by considering semigroup and prefix computations. Specifically, as our main result we show that for any constant 0 < < 1, one can construct an N-1/2 x N-1/2 square IMMB using which semigroup and prefix computations on N operands can be carried out in O(N-) time, while maintaining 0(1) broadcasting time. Compared with the previous best complexities O(N-1/6) and O(N-1/16) achieved on a rectangular MMB and GMMB, respectively, for the same computations, our results show that IMMBs are more powerful than MMBs and GMMBs.

关键词： bus mesh-connected computer mesh-connected computer with multiple buses parallel algorithm parallel architecture parallel computing processor array

来源：评论

学校读者我要写书评

暂无评论

ON THE PARALLEL COMPUTATION OF THE ALGEBRAIC PATH PROBLEM

引用

IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS 1992年第2期3卷 251-256页

作者： CHEN, GH WANG, BF LU, CJ Department of Computer Science and Information Engineering National Taiwan University Taipei Taiwan

The algebraic path problem is a general description of a class of problems, including some important graph problems such as transitive closure, all pairs shortest paths, minimum spanning tree, etc. In this paper, the algebraic path problem is solved on the processor array with a reconfigurable bus system. The proposed algorithms are based on repeated matrix multiplications. The multiplication of n x n matrices takes O(log n) time in the worst case. But, for some special cases, O(1) time is possible. It is shown that three instances of the algebraic path problem: transitive closure, all pairs shortest paths, and minimum spanning tree, can be solved in O(log n) time, which is as fast as on the CRCW PRAM.

关键词： ALGEBRAIC PATH PROBLEM ALL PAIRS SHORTEST PATHS MATRIX MULTIPLICATION MINIMUM SPANNING TREE processor array RECONFIGURABLE BUS TRANSITIVE CLOSURE

来源：评论

学校读者我要写书评

暂无评论

Constant time Boolean matrix multiplication on a linear array with a reconfigurable pipelined bus system

引用

JOURNAL OF SUPERCOMPUTING 1997年第4期11卷 391-403页

作者： Li, KQ SUNY Albany Dept Math & Comp Sci New Paltz NY 12561 USA

We show that the product of two N x N boolean matrices can be calculated in constant time on an LARPBS with O(N-3/log N) processors. All data communications and computations are performed on the bit level. To the best of the author's knowledge, this is the first parallel boolean matrix multiplication algorithm that has constant execution time, and is executed on a distributed memory system with o(N-3) processors. By using our boolean matrix multiplication algorithm, it is shown that the transitive closure of a directed graph can be obtained in O(log N) time (measured by bit level operations) on an LARPBS with O(N-3/log N) processors. To the best of our knowledge, this is the first parallel algorithm for transitive closure of directed graphs with time complexity O (log N) (comparable to that of CRCW PRAM) and cost O(N-3) on a realistic parallel computing model, which has no shared memory, and interprocessor communications are dealt with explicitly and efficiently.

关键词： Boolean matrix closure Boolean matrix multiplication cost optical bus processor array reconfigurability time complexity transitive closure

来源：评论

学校读者我要写书评

暂无评论

A mathematical programming method for constructing the shortest interconnection VLSI arrays

引用

INTEGRATION-THE VLSI JOURNAL 2021年 81卷 167-174页

作者： Ding, Hao Qian, Junyan Zhao, Lingzhong Zhai, Zhongyi Guilin Univ Elect Technol Guangxi Key Lab Trusted Software Guilin 541004 Peoples R China Guangxi Normal Univ Guangxi Key Lab Multisource Informat Min & Secur Guilin 541004 Peoples R China

Mesh-connected processor array is an extensively investigated architecture in parallel processing. Massive studies have addressed the problem of using reconfiguration algorithms to solve the fault tolerance of faulty mesh-connected processor arrays. However, the subarrays generated by the previous studies still contain large interconnection length, which will lead to the increase of capacitance, power dissipation and dynamic communication cost. First, a mathematical model is established for the array reconfiguration. Then, the proposed method treats the interconnections between each PEs as a function with different integer variables, which can be solved by using effective integer programming techniques. Finally, an effective solver is called to find the optimal solution. Simulation results show that the proposed method can reduce the interconnection length of the array in the row and column directions simultaneously, thereby generating a subarray with the shortest interconnection length. On a 32 x 32 host array with fault density of 30%, the total interconnection length of the subarray can be reduced by 8.36% compared with state-of-the-art, and the average interconnection length can be reduced by 39.30%, which is more closer to the lower bound.

关键词： processor array Fault tolerance Reconfiguration Algorithm Integer programming

来源：评论

学校读者我要写书评

暂无评论

SYSTOLIC PARSING OF CONTEXT-FREE LANGUAGES

引用

INTERNATIONAL JOURNAL OF PARALLEL PROGRAMMING 1990年第4期19卷 333-355页

作者： LANGLOIS, L UNIV MONTREAL MONTREAL H3C 3J7QUEBECCANADA

We report on a new systolic context-free language parsing algorithm. We present both single parse and multiple parse versions of the algorithm. For an input of length n the single parse version has a time complexity of O(n) and a space complexity of O(n2). This equals the performance of the most efficient known single parse algorithm. The space complexity of the multiple parse version is also of O(n2) while its time complexity is of O(mn) where m is the number of different parses for the input. This equals the time complexity of the most efficient known multiple parse algorithms and brings an improvement of a factor of log n over its space complexity.

关键词： PARALLEL PARSING processor array SYSTOLIC array DYNAMIC PROGRAMMING COMPILING

来源：评论

学校读者我要写书评

暂无评论

PARALLEL PARSING ALGORITHMS AND VLSI IMPLEMENTATIONS FOR SYNTACTIC PATTERN-RECOGNITION

引用

IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE 1984年第3期6卷 302-314页

作者： CHIANG, YT FU, KS PURDUE UNIV SCH ELECT ENGN W LAFAYETTE IN 47907 USA

Earley"s algorithm has been commonly used for the parsing of general context-free languages and the error-correcting parsing in syntactic pattern recognition. The time complexity for parsing is 0(n3). This paper presents a parallel Earley"s recognition algorithm in terms of an ``X*"" operator. By restricting the input context-free grammar to be λ-free, the parallel algorithm can be executed on a triangular-shape VLSI array. This array system has an efficient way of moving data to the right place at the right time. Simulation results show that this system can recognize a string with length n in 2n + 1 system time. We also present a parallel parse-extraction algorithm, a complete parsing algorithm, and an error-correcting recognition algorithm. The parallel complete parsing algorithm has been simulated on a processor array which is similar to the triangular VLSI array. For an input string of length n the processor array will give the correct right-parse at system time 2n + 1 if the string is accepted. The error-correcting recognition algorithm has also been simulated on a triangular VLSI array. This array recognizes an erroneous string of length n in time 2n + 1 and gives the correct error count. These parallel algorithms are especially useful for syntactic pattern recognition.","doi":"10.1109/TPAMI.1984.4767522","publicationTitle":"IEEE Transactions on Pattern Analysis and Machine Intelligence","startPage":"302","endPage":"314","rightsLink":"http://***/AppDispatchServlet?publisherName=ieee&publication=0162-8828&title=Parallel+Parsing+Algorithms+and+VLSI+Implementations+for+Syntactic+Pattern+Recognition&isbn=&publicationDate=May+1984&author=Y.+T.+Chiang&ContentID=10.1109/TPAMI.1984.4767522&orderBeanReset=true&startPage=302&endPage=314&volumeNum=PAMI-6&issueNum=3","displayPublicationTitle":"IEEE Transactions on Pattern Analysis and Machine Intelligence","pdfPath":"/iel5/34/4767514/***","keywords":[{"type":"IEEE Keywords","kwd":["Very large scale

关键词： Very large scale integration Pattern recognition Parallel algorithms Automata Error correction Dynamic programming Algorithm design and analysis Logic gates Delay Read-write memory Author Keywords Earley"s algorithm error-correcting recognition parallel CFL parsing parallel CFL recognition parse extracting parsing matrix processor array syntactic pattern recognition VLSI array

来源：评论

学校读者我要写书评

暂无评论

OPTIMAL BOUNDS FOR FINDING MAXIMUM ON array OF processorS WITH K-GLOBAL BUSES

引用

IEEE TRANSACTIONS ON COMPUTERS 1986年第1期35卷 62-64页

作者： AGGARWAL, A IBM T. J. Watson Research Center Abstract Authors References Cited By Keywords Metrics Similar Download Citation Email Print Request Permissions

The problem of finding the maximum of a set of values stored one per processor on a two-dimensional array of processors with a time-shared global bus is considered. The algorithm given by Bokhari is shown to be optimal, within a multiplicative constant, for this network and for other d-dimensional arrays. We generalize this model and demonstrate optimal bounds for finding the maximum of a set of values stored in a d-dimensional array with k time-shared global buses.

关键词： Computing maximum global bus matrix multiplication processor array sorting

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：