Title
Random Data Accesses on a Coarse-grained Parallel Machine II. One-to-many and Many-to-one Mappings
Document Type
Article
Date
1994
Keywords
deterministic communication-efficient algorithms, random data access, coarse-grained parallel machines
Language
English
Disciplines
Computer Sciences
Description/Abstract
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 Clanip (+ lower order terms) time and is optimal and scalable provided n _> O(pa+p2r/l) (n is the number of elements distributed across p processors, r is the start-up overhead and 1/It 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. The random access read/write operations provide the framework for the communication-efficient simulation of CREW and CRCW PRAMs on a coarse- grained distributed memory parallel machine. A companion paper [24] deals with the problem of performing dynamic permutations.
Recommended Citation
Shankar, Ravi V. and Ranka, Sanjay, "Random Data Accesses on a Coarse-grained Parallel Machine II. One-to-many and Many-to-one Mappings" (1994). College of Engineering and Computer Science - Former Departments, Centers, Institutes and Projects. 37.
https://surface.syr.edu/lcsmith_other/37
