Multiphase complete exchange: a theoretical analysis

Complete exchange requires each of N processors to send a unique message to each of the remaining N-1 processors. For a circuit switched hypercube with N=2^d processors, the direct and standard algorithms for complete exchange are time optimal for very large and very small message sizes, respectively. For intermediate sizes, a hybrid multiphase algorithm is better. This carries out direct exchanges on a set of subcubes whose dimensions are a partition of the integer d. The best such algorithm for a given message size m could hitherto only be found by enumerating all partitions of d. The multiphase algorithm is analyzed assuming a high performance communication network. It is proved that only algorithms corresponding to equipartitions of d (partitions in which the maximum and minimum elements differ by at most one) can possibly be optimal. The runtimes of these algorithms plotted against m form a hull of optimality. It is proved that, although there is an exponential number of partitions: (1) the number of faces on this hull is Θ(√(d)); (2) the hull can be found in Θ(√(d)) time; and (3) once it has been found, the optimal algorithm for any given m can be found in Θ(log d) time. These results provide a very fast technique for minimizing communication overhead in many important applications, such as matrix transpose, fast Fourier transform, and alternating directions implicit (ADI)