Parallel simulation of Markovian queueing networks

Abstract

Consider simulating a large queueing network, i.e., one with many queues and jobs, on a parallel computer. Suppose the network is partitioned so that each processor is assigned a set of queues to simulate. The basic difficulty in parallel simulation is synchronizing the simulation clocks on each of the processors so that events appear to get executed in the proper order. If the network possesses a Markovian structure, there are algorithms that can be used to simplify the clock synchronization problem. For appropriately structured queueing networks, these algorithms are quite efficient and large speedups have been obtained; in one example a speedup of 220 was measured on 256 processors of the Intel Touchstone Delta computer. The synchronization algorithms are based on uniformization. Specifically, a Poisson process with rate λij is generated. For the purpose of parallel simulation, the times of the uniformizing Poisson processes can be sampled in advance of actually running the simulation. By doing so, each processor can become aware of a superset of instances in time at which it (i) may receive jobs from another processor, and (ii) may be required to send jobs to another processor. Thus, the times of these Poisson processes become interprocessor synchronization times. Because these times are pre-sampled, all synchronization times are known in advance of actually running the simulation. A variety of parallel simulation algorithms can be devised that take advantage of these known synchronization times in somewhat different fashions.