Random Data Accesses on a Coarse-Grained Parallel Machine II. One-to-Many and Many-to-One Mappings
Ravi V. Shankar, Sanjay Ranka · Journal of Parallel and Distributed Computing · 1997
This paper describes deterministic communication-efficient algorithms for performing random data accesses with hot spots on a coarse-grained parallel machine. The general random access read-write operations with hot spots can be completed inCμn/p(+ lower order terms) time and is optimal and scalable providedn⪢p3+p2τ/μ (nis the number of elements distributed acrosspprocessors, τ is the start-up overhead and 1/μ is the data transfer rate).Cis a small constant between 3 and 4 for the random access write operation, slightly higher for the random access read operation. Monotonic random access reads/writes can be completed with smaller constants and are optimal for smallernas well. A companion paper [26] deals with the problem of performing dynamic permutations.