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

                 Ravi V. Shankar(S)     Sanjay Ranka
            School of Computer and Information Science
           Syracuse University, Syracuse, NY 13244-4100
             e-mail: rshankar, ranka@top.cis.syr.edu
                           October 1994

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{\mu}n/p$ ($+$ lower order terms) time and is
optimal and scalable provided $n \ge O(p^3+p^2{\tau/\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. 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 deals with the problem of performing dynamic permutations.