The scheduling algorithm from Section 2 can be used as a subroutine in algorithms for emulating shared-memory machines on bounded-degree networks. A shared-memory machine with a large address space can be emulated by randomly hashing the memory locations to the nodes of a butterfly as in [11] and [29]. The hashing ensures that the congestion of the packets implementing each memory access step is small. The algorithm from Section 2 is used to schedule the movements of these packets.

Given a set of *N* packets whose paths have congestion *c* on a
leveled network with depth *L*, a setting of ranks that
ensures delivery in time can be found can be found
off-line deterministically in time . The proof
uses the Raghavan-Spencer technique [27, 33] to
sequentially find a setting of the ranks so that no bad event
corresponding to a delay sequence occurs.

One application is in preparing simulations by volume and
area-universal networks off-line so that no random bits are needed.
As before, the first step is to map the processors of the network to
be simulated, *B*, to the processors of the area-universal network,
*U*, from Section 7 using the recursive decomposition
strategy from [21]. Network *U* has *N* processors, and
*B* has area . To simulate each step of *B*, network *U* must
route a set of messages with load factor . The second step is to find paths for the messages. Since
these messages link the same processors at every step of *B*, it is
sufficient to find paths once off-line. They can be reused over and
over during the simulation. Given a set of *n* messages with load
factor , it is possible to find a set of paths with
congestion and dilation in a
fat-tree with root capacity *M* off-line deterministically in time
polynomial in *n* and *M*. The final step is to find a set of ranks
for the messages. These ranks can also be reused at each step of the
simulation. Network *U* has root capacity . Thus, both the paths and the ranks for the packets can be
determined off-line deterministically in time polynomial in *N* so
that the time to simulate each step of *B* is .

By making minor modifications to the definition of a delay sequence,
it is possible to prove that not only does the late arrival of some
packet imply that a bad event occurs, but also if a bad event occurs
then some packet is delayed. More precisely, some packet arrives at
step *L+w* where *w = m+qf* if and only if a bad event corresponding
to a delay sequence of length with *m+qf* packets
occurs.

Mon Jul 22 22:57:44 EDT 1996