OPTIMAL ARCHITECTURES AND ALGORITHMS FOR MESH-CONNECTED PARALLEL COMPUTERS WITH SEPARABLE ROW-COLUMN BUSES

A two-dimensional mesh of processing elements (PE's) with separable ro w and column buses (i.e., broadcast mechanisms for rows and columns th at can be logically divided into a number of local buses through the u se 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 routi ng. For meshes with separable row/column buses, we 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 col umn and discuss the VLSI implications of this new architecture. We fin d that with our basic two-level arrangement, square meshes are not opt imal for the above algorithms and that-the time complexity can be redu ced by using rectangular meshes. However, our method of building highe r order meshes allows the construction of an optimal square mesh from rectangular submeshes. We further observe that through more extensive use of PE-controlled switches in the mesh, a hierarchy of buses can be realized efficiently in VLSI. The time-complexity results are shown t o correspond to those previously published when certain parameters of our design are fixed at special values.