Random Data Accesses on a Coarse-Grained Parallel Machine II. One-to-Many and Many-to-One Mappings

✍ Scribed by Ravi V. Shankar; Sanjay Ranka

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

✦ Synopsis

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 in Cµn/p (+ lower order terms) time and is optimal and scalable provided n >> p 3 + p 2 τ/µ (n is the number of elements distributed across p processors, τ is the start-up overhead and 1/µ is the data transfer rate). C is 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 smaller n as well. A companion paper [26] deals with the problem of performing dynamic permutations.