License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SEA.2023.5
URN: urn:nbn:de:0030-drops-183550
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/18355/
Go to the corresponding LIPIcs Volume Portal

Penschuck, Manuel

Engineering Shared-Memory Parallel Shuffling to Generate Random Permutations In-Place

pdf-format:
LIPIcs-SEA-2023-5.pdf (1 MB)

Abstract

Shuffling is the process of placing elements into a random order such that any permutation occurs with equal probability. It is an important building block in virtually all scientific areas. We engineer, - to the best of our knowledge - for the first time, a practically fast, parallel shuffling algorithm with O(√n log n) parallel depth that requires only poly-logarithmic auxiliary memory (with high probability). In an empirical evaluation, we compare our implementations with a number of existing solutions on various computer architectures. Our algorithms consistently achieve the highest through-put on all machines. Further, we demonstrate that the runtime of our parallel algorithm is comparable to the time that other algorithms may take to acquire the memory from the operating system to copy the input.

BibTeX - Entry

@InProceedings{penschuck:LIPIcs.SEA.2023.5,
  author =	{Penschuck, Manuel},
  title =	{{Engineering Shared-Memory Parallel Shuffling to Generate Random Permutations In-Place}},
  booktitle =	{21st International Symposium on Experimental Algorithms (SEA 2023)},
  pages =	{5:1--5:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-279-2},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{265},
  editor =	{Georgiadis, Loukas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2023/18355},
  URN =		{urn:nbn:de:0030-drops-183550},
  doi =		{10.4230/LIPIcs.SEA.2023.5},
  annote =	{Keywords: Shuffling, random permutation, parallelism, in-place, algorithm engineering, practical implementation}
}

Keywords: Shuffling, random permutation, parallelism, in-place, algorithm engineering, practical implementation
Collection: 21st International Symposium on Experimental Algorithms (SEA 2023)
Issue Date: 2023
Date of publication: 19.07.2023
Supplementary Material: Software (Source Code): https://crates.io/crates/rip_shuffle
Software (Source Code and Raw Data): https://zenodo.org/record/7876820

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI