Parallel simulation by time segmentation: methodology and applications

ABSTRACT

In this paper we present a time parallel simulation approach and discuss conditions under which this approach is applicable. Our approach involves distributing the available processors among segments of the time horizon of the simulation. We show that under certain conditions, sample paths of the system generated by a common sequence of potential events will couple (i.e., become identical) with probability one. This property will be exploited to efficiently combine the information collected on different segments of the sample path and generate a complete valid sample path. We show that the expected coupling time of the system (i.e., the amount of time required for all the sample paths of the system to couple) is essential to the efficiency of the approach. We apply our parallel simulation approach to a class of Markovian queueing networks and investigate the efficiency of the method by providing bounds and estimates for the expected coupling times.

REFERENCES

• 1: Sigrún Andradóttir , Teunis J. Ott, Time-segmentation parallel simulation of networks of queues with loss or communication blocking, ACM Transactions on Modeling and Computer Simulation (TOMACS), v.5 n.4, p.269-305, Oct. 1995 [doi>10.1145/226275.226276]
• 2: Cazsandras, C. G., and S. G. Strickland. 1989. Sample Path Properties of Timed Discrete Event Systems. Proceeding8 of the IEEE 77(1):59-71.
• 3: Chen, L., and R. Serfozo. 1995. Parallel Simulation by Multi-Instruction, Longest-Path Algorithms. Preprint.
• 4: Richard M. Fujimoto, Parallel and distributed discrete event simulation: algorithms and applications, Proceedings of the 25th conference on Winter simulation, p.106-114, December 12-15, 1993, Los Angeles, California, United States [doi>10.1145/256563.256596]
• 5: Albert G. Greenberg , Boris D. Lubachevsky , Isi Mitrani, Unboundedly parallel simulations via recurrence relations, Proceedings of the 1990 ACM SIGMETRICS conference on Measurement and modeling of computer systems, p.1-12, April 1990, Univ. of Colorado, Boulder, Colorado, United States
• 6: Philip Heidelberger, Discrete event simulations and parallel processing: statistical properties, SIAM Journal on Scientific and Statistical Computing, v.9 n.6, p.1114-1132, November 1988 [doi>10.1137/0909077]
• 7: Philip Heidelberger , Harold S. Stone, Parallel trace-driven cache simulation by time partitioning, Proceedings of the 22nd conference on Winter simulation, p.734-737, December 09-12, 1990, New Orleans, Louisiana, United States
• 8: Hoseyni-Ncsab, M., and S. Andrad6ttir. 1996s. Efficiency of Time Segmentation Parallel Simulation of Finite Markovian Queueing Networks. Working Paper.
• 9: Hoseyni-Nasab, M., and S. Andrad6ttir. 1996b. Parallel Simulation of Transfer Lines by Time Segmentation. Working Paper.
• 10: Yi-Bing Lin , Edward D. Lazowska, A time-division algorithm for parallel simulation, ACM Transactions on Modeling and Computer Simulation (TOMACS), v.1 n.1, p.73-83, Jan. 1991 [doi>10.1145/102810.214307]
• 11: Vakili, P. 1991. Using a Standard Clock Technique for Efficient Simulation. Operations Research Letters 10(8):445-452.