Engineering Parallel In-Place Random Generation of Integer Permutations - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Communication Dans Un Congrès Année : 2008

Engineering Parallel In-Place Random Generation of Integer Permutations

Jens Gustedt

Résumé

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.
Fichier non déposé

Dates et versions

inria-00312131 , version 1 (25-08-2008)

Identifiants

  • HAL Id : inria-00312131 , version 1

Citer

Jens Gustedt. Engineering Parallel In-Place Random Generation of Integer Permutations. International Workshop on Experimental Algorithms, WEA 2008, May 2008, Provincetown, MA, United States. pp.129-141. ⟨inria-00312131⟩
121 Consultations
0 Téléchargements

Partager

Gmail Facebook X LinkedIn More