Time-Parallel Simulation Using Partial State Matching for Queueing Systems

This paper describes partial state matching for approximate time-parallel simulation. The notion of degree of freedom in time-parallel simulation is introduced. Two partial state matching algorithms are proposed to simulate acyclic networks of FCFS G/G/1/K queues in which arriving customers that find the queue full are lost. The algorithms are suitable for SIMD as well as MIMD architectures. The performance of the algorithms is studied. Experiment results with M/M/1/K and M/D/1/K queueing networks show that the potential speedup and simulation accuracy of the algorithms are good. The worst performance of both algorithms occurs when traffic intensity is one. Arguments are made to explain this phenomenon.