Fast Parallel Permutation Algorithms

摘要

The problem of permuting n data items, each covering D global memory cells, on anEREW PRAM with n/(log n) processors and less than Dn additional storage is investigated. A family of algorithms (A(sub k))(sub k), where k = 1, 2, ..., log* n, such that A(sub k) needs time Dlog nlog(sup k)n, is presented. Here, log(sup k)n, denotes k times application of log to n, and log* n = min(k such that log(sup k)n less than or equal to 1). All algorithms need Theta(n) operations, which is optimal. The storage requirements for A(sub k) are n global bits,