All-to-all personalized communication in multidimensional torus and mesh networks

All-to-all personalized communication commonly occurs in many important par allel algorithms, such as FFT and matrix transpose. This paper presents new algorithms for all-to-all personalized communication or complete exchange in multidimensional torus- or mesh-connected multiprocessors. For an R x C torus or mesh where R less than or equal to C, the proposed algorithms have time complexities of O(C) message startups and O(RC2) message transmission s. The algorithms for three- or higher-dimensional tori or meshes follow a similar structure. Unlike other existing message-combining algorithms in wh ich the number of nodes in each dimension should be a power-of-two and squa re. the proposed algorithms accommodate non-power-of-two tori or meshes whe re the number of nodes In each dimension need not be power-of-two and squar e. In addition, destinations remain fixed over a larger number of steps in the proposed algorithms, thus making them amenable to optimizations. Finall y, the data structures used are simple, hence making substantial savings of message-rearrangement time.