Random Data Accesses on a Coarse-Grained Parallel Machine I. One-to-One Mappings

✍ Scribed by Ravi V. Shankar; Sanjay Ranka

• Publisher: Elsevier Science
• Year: 1997
• Tongue: English
• Weight: 271 KB
• Volume: 44
• Category: Article
• ISSN: 0743-7315
• DOI: 10.1006/jpdc.1997.1316

✦ Synopsis

This paper describes deterministic communication-efficient algorithms for performing dynamic permutations on a coarsegrained parallel machine. Our analysis shows that the general permutation operation can be completed in Cµn/p (+ lower order terms) time and is optimal and scalable provided n >> p 3 + p 2 τ/µ (n is the size of the permutation or the number of elements distributed across the p processors, τ is the startup overhead, and 1/µ is the data transfer rate). C is 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.