A new network topology with multiple meshes

This paper introduces a new network topology, called Multi-Mesh (MM), which uses multiple meshes as the basic building blocks interconnected in a suit able manner. The proposed network consists of n(4) processors and is 4-regu lar with a diameter of 2n. The network also contains a Hamiltonian cycle. S imple routing algorithms for point-to-point communication, one-to-all broad cast, and multicast have been described for this network. It is shown that a simple n(2) x n(2) mesh can also be emulated on this network in O(1) time . Several application examples have been discussed for which this network i s found to be more efficient with regard to computational time than the cor responding mesh with the same number of processors. As examples, O(n) time algorithms for finding the sum. average, minimum, and maximum of n(4) data values, located at n(4) different processors have been discussed. Time-effi cient implementations of algorithms for solving nontrivial problems, e.g., Lagrange's interpolation, matrix transposition, matrix multiplication, and Discrete Fourier Transform (DFT) computation have also been discussed. The time complexity of Lagrange's interpolation on this network is O(n) for n(2 ) data points compared to O(n(2)) time on mesh of the same size. Matrix tra nspose requires O(n(0.5)) time for an n x n matrix. The time for multiplyin g two n x n matrices is O(n(0.6)) with an AT-cost of O(n(3)). DFT of n samp le points can be computed in O(n(0.6)) time on this network. Papers [6], [7 ] show that n(4) data elements can be sorted on this network in O(n) time.