Efficient Automatic Simulation of Parallel Algorithms on Network of Workstations

Andrews introduced a number of techniques for automaticallyhiding latency when performing simulations of networks with unit delay links on networks with arbitrary unequal delay links. In their work, they assume that processors of the host network are identicalin computational power to those of the guest network being simulated.They further assume that the links of the host are able to pipelinemessages, i.e., they are able to deliver P packets in time O(P+ d) where d is the delay on the link. In this paper we examine the effect of eliminating one or both of theseassumptions. In particular, we provide an efficient simulation of a linear array of homogenous processors with unit delay links on a linear array of hetrogenous processors with arbitrary delay links and we show that the slowdown achieved by our simulation is optimal. We also consider the case of simulating a clique of homogenous processors with unit delay links on a clique of hetrogenous processors with arbitrary delay reducing the slowdown from the obvious bound of the maximum delay link to the average of the link delays. For the case of the linear array we consider both links with and without pipelining. For the clique simulation the links are not assumed to support pipelining.The main motivation of our results is to mitigate the degradation of performance when executing parallel programs designed for different architectures on a Network of Workstations (NOW). In such a setting is unlikely that the links provided by the NOW will support pipelining and it is quite probable the processors will be heterogenous. Combining our result on clique simulation with well-known techniques for simulating shared memory PRAMs on distributed memory machines provides an effective automatic compilation of a PRAM algorithm on a NOW