Random Data Accesses on a Coarse-Grained Parallel Machine I. One-to-One Mappings
Ravi V. Shankar, Sanjay Ranka · Journal of Parallel and Distributed Computing · 1997
This paper describes deterministic communication-efficient algorithms for performing dynamic permutations on a coarse-grained parallel machine. Our analysis shows that the general permutation operation can be completed inCμn/p(+ lower order terms) time and is optimal and scalable providedn⪢p3+p2τ/μ (nis the size of the permutation or the number of elements distributed across thepprocessors, τ is the start-up overhead, and 1/μ is the data transfer rate).Cis a small constant typically between 2 and 3 for write permutations, slightly higher for read permutations. Modifications to exploit locality of access are presented. Special classes of permutations that are optimal for smaller sizes are also described. A companion paper [22] deals with the problem of random data accesses with hot spots.