Engineering Parallel In-Place Random Generation of Integer Permutations

Jens Gustedt 1
1 ALGORILLE - Algorithms for the Grid
INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
Abstract : We tackle the feasibility and efficiency of two new parallel algorithms that sample random permutations of the integers [M] = {1, ..., M} The first reduces the communication for p processors from O(M) words (O(M logM) bits, the coding size of the permutation) to O(M log p= logM) words (O(M log p) bits, the coding size of a partition of [M] into M=p sized subsets). The second exploits the common case of using pseudo-random numbers instead of real randomness. It reduces the communication even further to a use of bandwidth that is proportional to the used real randomness. Careful engineering of the required subroutines is necessary to obtain a competitive implementation. Especially the second approach shows very good results which are demonstrated by large scale experiments. It shows high 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.
Type de document :
Communication dans un congrès
Catherine C. McGeoch. International Workshop on Experimental Algorithms, WEA 2008, May 2008, Provincetown, MA, United States. Springer Verlag, 5038, pp.129-141, 2008, LNCS
Liste complète des métadonnées

https://hal.inria.fr/inria-00312131
Contributeur : Jens Gustedt <>
Soumis le : lundi 25 août 2008 - 12:05:31
Dernière modification le : jeudi 11 janvier 2018 - 06:19:48

Identifiants

  • HAL Id : inria-00312131, version 1

Collections

Citation

Jens Gustedt. Engineering Parallel In-Place Random Generation of Integer Permutations. Catherine C. McGeoch. International Workshop on Experimental Algorithms, WEA 2008, May 2008, Provincetown, MA, United States. Springer Verlag, 5038, pp.129-141, 2008, LNCS. 〈inria-00312131〉

Partager

Métriques

Consultations de la notice

264