Multi-mesh of trees with its parallel algorithms
In recent years the multi-mesh network [Proceedings of the Ninth International Parallel Processing Symposium, Santa Barbara, CA, April 2528, 1995, 17; IEEE Trans. on Comput. 68 (5) (1999) 536] has created a lot of interests among the researchers for its efficient topological properties. Several parallel algorithms for various trivial and nontrivial problems have been mapped on this network. However, because of its O(n) diameter, a large class of algorithms that involves frequent data broadcast in a row or in a column or between the diametrically opposite processors, requires O(n) time on an nn multi-mesh. In search of faster algorithms, we introduce, in this paper, a new network topology, called multi-mesh of trees. This network is built around the multi-mesh network and the mesh of trees. As a result it can perform as efficiently as a multi-mesh network and also as efficiently as a mesh of trees. Several topological properties, including number of links, diameter, bisection width and decomposition are discussed. We present the parallel algorithms for finding sum of n4 elements and the n2-point Lagrange interpolation both in O(logn)1 time. The solution of n2-degree polynomial equation, n2-point DFT computation and sorting of n2 elements are all shown to run in O(logn) time too. The communication algorithms one-to-all, row broadcast and column broadcast are also described in O(logn) time. This can be compared with O(n) time algorithms on multi-mesh network for all these problems.
multi-mesh mesh of trees bisection width decomposition dft computation sorting communication algorithms lagrange's interpolation durandkerner method ehrlich method matrix multiplication