Skip to Main content Skip to Navigation

Sublinear Communication for Integer Permutations

Jens Gustedt 1 
1 ALGORILLE - Algorithms for the Grid
INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
Abstract : In [\cite{GUSTEDT:2006:INRIA-00000900:2}] we have shown that random shuffling of data can be realised with linear resource usage, CPU time as well as communication, and this for a large variaty of paradigms, in particular distributed and out-of-core computation. In this paper we restrict to the case of permutations of the integers $[M] = \{1, \ldots, M\}$ and show first show how the communication for a $p$ processor setting can be reduced from $O(M)$ words ($O(M \log M)$ bits, the coding size of the permutation) to $O(M \log p / \log M)$ words ($O(M \log p)$ bits, the coding size of a partition of $[M]$ into $M / p$ sized subsets). % For the common case of using pseudo-random numbers instead of real randomness, this coding size is in fact not a valid lower bound; we show the communication can be lowered to a use of bandwidth that is proportional to the used real randomness. % The efficiency and feasibility of this second approach is demonstrated by large scale experiments where it proves its scalability and outperforms the previously known approaches by far. First, we compare our algorithm to the classical sequential data shuffle algorithm, where we get a speedup of about $1.5$. Then, we show how the algorithm parallelizes well on a multicore system and scales to a cluster of $440$ cores.
Complete list of metadata

Cited literature [14 references]  Display  Hide  Download
Contributor : Jens Gustedt Connect in order to contact the contributor
Submitted on : Friday, January 4, 2008 - 11:48:39 AM
Last modification on : Saturday, June 25, 2022 - 7:40:14 PM
Long-term archiving on: : Friday, November 25, 2016 - 7:50:08 PM


Explicit agreement for this submission


  • HAL Id : inria-00201503, version 3


Jens Gustedt. Sublinear Communication for Integer Permutations. [Research Report] RR-6403, INRIA. 2007, 20 p. ⟨inria-00201503v3⟩



Record views


Files downloads