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.
Liste complète des métadonnées

Littérature citée [14 références]  Voir  Masquer  Télécharger
Contributeur : Jens Gustedt <>
Soumis le : vendredi 4 janvier 2008 - 11:48:39
Dernière modification le : dimanche 20 mai 2018 - 20:20:10
Document(s) archivé(s) le : vendredi 25 novembre 2016 - 19:50:08


Accord explicite pour ce dépôt


  • HAL Id : inria-00201503, version 3


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



Consultations de la notice


Téléchargements de fichiers