Skip to Main content Skip to Navigation
Conference papers

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.
Complete list of metadata
Contributor : Jens Gustedt Connect in order to contact the contributor
Submitted on : Monday, August 25, 2008 - 12:05:31 PM
Last modification on : Saturday, June 25, 2022 - 7:46:31 PM


  • HAL Id : inria-00312131, version 1



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⟩



Record views