Random Data Accesses on a Coarse-grained Parallel Machine
                      I. One-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 dynamic permutations on a coarse-grained parallel machine. Our
analysis shows that the general permutation operation 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 size of the permutation
or the number of elements distributed across the $p$ processors, $\tau$ is
the start-up overhead and $1/\mu$ 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. The dynamic permutation operation
provides the framework for the communication-efficient simulation of an
EREW PRAM on a coarse-grained distributed memory parallel machine. A
companion paper deals with the problem of random data accesses with hot
spots.