No Access

FAST PARALLEL PERMUTATION ALGORITHMS

Max-Planck-Institut für Informatik, 66123 Saarbrücken, Germany

Supported by the ESPRIT Basic Research Actions Program of the EU under contract No. 7141 (project ALCOM II).

and

Universität des Saarlandes, Fachbereich 14 Informatik, Postfach 151150, 66041 Saarbrücken, Germany

Supported by the Dutch Science Foundation (NWO) through NFI project ALADDIN under contract number NF 62–376 and by the German Science Foundation (DFG) through SFB 124. Part of the work was done when this author was at CWI, Postbus 94079, 1090 GB Amsterdam, The Netherlands.

Search for more papers by this author

https://doi.org/10.1142/S0129626495000126Cited by:1 (Source: Crossref)

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: