2005 · 18 citations · 13 references
ComputingCommunicationComputer ScienceComputer NetworksDigital CommunicationParallel AlgorithmsCommunication ComplexityDistributed AlgorithmsDistributed ComputingHypercube NetworksConcurrent ComputationDisjoint SetsMaximum SpeedPermutationsSpan Analysis
All-to-all personalized communication is a class of permutations in which each processor sends a unique message to every other processor. We present optimal algorithms for concurrent communication on all channels in Boolean cube networks, both for the case with a single permutation, and the case where multiple permutations shall be performed on the same local data set, but on different sets of processors. For K elements per processor our algorithms give the optimal number of elements transfer, K=2. For a succession of all-to-all personalized communications on disjoint subcubes of β dimensions each, our best algorithm yields (K/2)+σ-β element exchanges in sequence, where is the total number of processor dimensions in the permutation. An implementation on the Connection Machine of one of the algorithms offers a maximum speed-up of 50% compared to the previously best known algorithm.
13
Data communication in hypercubes
Martin H. Schultz · Journal of Parallel and Distributed Computing · 1989 · 148 citations · Full text