Multi-Mesh-an efficient topology for parallel processing
Swagatam Das, Bhabani P. Sinha · 2002
This paper introduces a new interconnection scheme, called Multi-Mesh (MM) network, for parallel processing which uses multiple meshes as the basic building blocks interconnected in a suitable manner. The interconnection pattern is regular and suitable for VLSI implementation. Each processor in the network has degree four with a resulting diameter upper bounded by 2n for n/sup 4/ processors. Routing can easily be done within 2n time on this network. Sum/minimum/maximum of n/sup 4/ data values can be found in O(n) time. Two n/spl times/n matrices can be multiplied by the MM network in O(n/sup 0.6/) with an AT-cost of O(n/sup 3/). The DFT of n sample points can be computed in O(n/sup 0.6/) time on this network. Sorting of n/sup 3/ data elements resident on n/sup 3/ processors can be done in 2n log n+14n+o(n) time.>