Title :
Optimal architectures and algorithms for mesh-connected parallel computers with separable row/column buses
Author :
Serrano, Mauricio J. ; Parhami, Behrooz
Author_Institution :
Dept. of Electr. & Comput. Eng., California Univ., Santa Barbara, CA, USA
fDate :
10/1/1993 12:00:00 AM
Abstract :
A two-dimensional mesh of processing elements (PE´s) with separable row and column buses (i.e., broadcast mechanisms for rows and columns that can be logically divided into a number of local buses through the use of PE-controlled switches) has been shown to be quite effective for semigroup computation, prefix computation, and a wide class of other computations that do not require excessive communication or data routing. For meshes with separable row/column buses, the authors show how semigroup and prefix computations can be performed with the same asymptotic time complexity without the provision of buses for every row and every column and discuss the VLSI implications of this new architecture
Keywords :
computational complexity; parallel algorithms; parallel architectures; data routing; mesh-connected; parallel computers; prefix computation; processing elements; semigroup computation; separable row and column buses; time complexity; two-dimensional mesh; Broadcasting; Buildings; Communication switching; Computer architecture; Computer networks; Concurrent computing; Delay; Routing; Switches; Very large scale integration;
Journal_Title :
Parallel and Distributed Systems, IEEE Transactions on