Optimal communication algorithms for regular decompositions on the hypercube

Abstract

We discuss optimal communication and decomposition algorithms for a class of regular problems on concurrent computers with a hypercube topology, using a general technique we call the method of cube geodesics. We address the calculation of various transformations (convolutions, functionals etc.) of data distributed over the hypercube; examples are the Fast Fourier Transform, matrix algorithms, global scalar products and vector sums, sorting. These all involve long distance inter-node interactions and require more intricate communication that the simple local problems with static spatial decomposition such as partial differential equations. We believe that our library of optimal communication routines is applicable to these and many other problems. The simple example of a database application is sketched. We implement the algorithms on the Caltech/JPL Mark II hypercube and present a detailed performance analysis.

Additional details