Engineering Shared-Memory Parallel Shuffling to Generate Random Permutations In-Place
Autor: | Penschuck, Manuel |
---|---|
Rok vydání: | 2023 |
Předmět: |
practical implementation
FOS: Computer and information sciences parallelism Computer Science - Data Structures and Algorithms random permutation Shuffling random permutation parallelism in-place algorithm engineering practical implementation Shuffling in-place Data Structures and Algorithms (cs.DS) Theory of computation → Shared memory algorithms algorithm engineering |
DOI: | 10.48550/arxiv.2302.03317 |
Popis: | 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. LIPIcs, Vol. 265, 21st International Symposium on Experimental Algorithms (SEA 2023), pages 5:1-5:20 |
Databáze: | OpenAIRE |
Externí odkaz: |
načítá se...