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

The full text article is not available for purchase.

The publisher only permits individual articles to be downloaded by subscribers.


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 Cmun/p (+ lower order terms) time and is optimal and scalable provided n ยป p3 + p2tau/mu (n is the number of elements distributed across p processors, tau is the start-up overhead and 1/mu 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.

Document Type: Research Article

Affiliations: 1: Syracuse University, Syracuse, New York, 13244-4100 2: University of Florida, Gainesville, Florida, 32611-6120

Publication date: July 1, 1997

Related content



Share Content

Access Key

Free Content
Free content
New Content
New content
Open Access Content
Open access content
Subscribed Content
Subscribed content
Free Trial Content
Free trial content
Cookie Policy
Cookie Policy
ingentaconnect website makes use of cookies so as to keep track of data that you have filled in. I am Happy with this Find out more