Pipelined Block-Cyclic Redistributions in Complete 2D Tori

All-to-all communication (all-to-all personalized exchange) [11] occurs in many important applications in parallel computing (i.e multidimensional FFT and matrix transposition). Generally, the all-to-all communication pattern involves the distribution of a data block from a source processor to all target processors of the system [5], [7], [8], [12]. In this paper, we address a more generalized instance of the problem, that is, to redistribute variable-sized data blocks between processors. We assume a communication model of a torus where each processor can simultaneously send/receive messages from its neighboring nodes. Tori have become a popular topology due to their better scalability compared to multi-dimensional networks such as hypercubes [11]. Our strategy fully utilizes the block-cyclic redistribution properties discussed in the literature [1], [2], [3], [4], [9]. More specifically, we prove that there are specified groups of processor classes (see Desprez et al. [1]), which we name superclasses, that communicate with exactly the same pattern. Our communtication schedulirng is based on pipelining distributions between members of superclasses.