A METHOD FOR EXPLOITING COMMUNICATION COMPUTATION OVERLAP IN HYPERCUBES/

This paper presents a method to derive efficient algorithms for hyperc ubes, The method exploits two features of the underlying hardware: a) the parallelism provided by the multiple communication links of each n ode and b) the possibility of overlapping computations and communicati ons which is a feature of machines supporting an asynchronous communic ation protocol. The method can be applied to a generic class of hyperc ube algorithms whose distinguishing features are quite frequent in com mon algorithms for hypercubes. Many examples of this class of algorith ms are found in the literature for different problems, The paper shows the efficiency of the method for two case studies. The results show t hat the reduction in communication overhead is very significant in man y cases. They also show that the algorithms produced by our method are always very close to the optimum in terms of execution time. (C) 1998 Elsevier Science B.V. All rights reserved.