article · 1993
Fast Parallel Permutation Algorithms
Jörg Keller, Torben Hagerup, Torben Hagerup
Cited by 0Abstract and details only
Abstract
We investigate the problem of permuting n data items on an EREW PRAM with p processors using little additional storage. We present a simple algorithm with run time O((n=p) log n) and an improved algorithm with run time O(n=p+ log n log log(n=p)). Both algorithms require n additional global bits and O(1) local storage per processor. If prefix summation is supported at the instruction level, the run time of the improved algorithm is O(n=p). The algorithms can be used to rehash the address space of a PRAM emulation. Keywords: Parallel Algorithms, Permutations, Shared Memory, Rehashing 1 Introduction Consider the task of permuting n data items on an EREW PRAM with p n processors according to a permutation ß given in the form of a constant-time "black-box" program. The task is trivial if n additional (global or local) memory cells are available: The items are first moved to the additional storage, with each processor handling O(n=p) items, and then written back in permuted order. We res...
Cite this paper
Keller, J., Hagerup, T., & Hagerup, T. (1993). Fast Parallel Permutation Algorithms.
Keller, Jörg, et al. “Fast Parallel Permutation Algorithms.” 1993.
Keller, Jörg, Torben Hagerup, and Torben Hagerup. 1993. “Fast Parallel Permutation Algorithms.”
Keller, J., Hagerup, T. and Hagerup, T. (1993) ‘Fast Parallel Permutation Algorithms’.
@article{keller1993fast,
title = {{Fast Parallel Permutation Algorithms}},
author = {Keller, Jörg and Hagerup, Torben and Hagerup, Torben},
year = {1993}
}Made from the index record. Check names, capitalisation and page numbers against the paper. Need another style? AI for Research has over 10,000.