Efficient communication primitives on circuit-switched hypercubes

Abstract

We give practical algorithms, complexity analysis and implementation for all-to-all personalized communication and matrix transpose (with two-dimensional partitioning of the matrix) on hypercubes. We assume the following communication characteristics: circuit-switched e-cube routing and one-port communication model. For all-to-all personalized communication, we propose a hybrid algorithm that combines the well-known recursive doubling algorithm [22,12] and a direct-route algorithm [26,23]. Our hybrid algorithm balances between data transfer time and start-up time of these two algorithms, and its communication complexity is estimated to be better than the two previous algorithms for a range of machine parameters. For matrix transpose with two-dimensional partitioning of the matrix, our algorithm is measured to be better than the recursive transpose algorithm [8] by n nearest-neighbor communications [12]. Our algorithm takes advantage of circuit-switched routing and is congestion-free for a hypercube with e-cube routing. We also suggest a way of storing the matrix such that the transpose operation can take advantage of the routing of the machine.