TY - GEN
T1 - Parallel simulation of Markovian queueing networks
AU - Heidelberger, Philip
AU - Nicol, David M.
PY - 1994
Y1 - 1994
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=0027929076&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=0027929076&partnerID=8YFLogxK
M3 - Conference contribution
AN - SCOPUS:0027929076
SN - 0818652926
T3 - Proceedings of the IEEE International Workshop on Modeling, Analysis, and Simulation of Computer and Telecommunication Systems
SP - 35
EP - 36
BT - Proceedings of the IEEE International Workshop on Modeling, Analysis, and Simulation of Computer and Telecommunication Systems
A2 - Madisetti, Vijay
A2 - Gelenbe, Erol
A2 - Walrand, Jean
PB - Publ by IEEE
T2 - Proceedings of the 2nd International Workshop on Modeling, Analysis, and Simulation of Computer and Telecommunication Systems
Y2 - 31 January 1994 through 2 February 1994
ER -