Skip to Main content Skip to Navigation
Reports

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

https://hal.inria.fr/inria-00201503
Contributor : Jens Gustedt <>
Submitted on : Friday, January 4, 2008 - 11:48:39 AM
Last modification on : Friday, February 26, 2021 - 3:28:02 PM
Long-term archiving on: : Friday, November 25, 2016 - 7:50:08 PM

File

RR-6403.pdf
Explicit agreement for this submission

Identifiers

  • HAL Id : inria-00201503, version 3

Citation

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

Share

Metrics

Record views

293

Files downloads

132