Abstract
This paper surveys topics that presently define the state of the art in parallel simulation. Included in the tutorial are discussions on new protocols, mathematical performance analysis, time parallelism, hardware support for parallel simulation, load balancing algorithms, and dynamic memory management for optimistic snchronization.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
I.F. Akyildiz, L. Chen, S.R. Das, R.M. Fujimoto and R. Serfozo, Performance analysis of Time Warp with limited memory,Proc. 1992 ACM SIGMETRICS Conf. on Measuring and Modeling Computer Systems, Vol. 20 (1992).
H. Ammar and S. Deng, Time Warp simulation using time scale decomposition, in:Advances in Parallel and Distributed Simulation, Vol. 23, SCS Simulation Series (1991) pp. 11–24.
R. Ayani, A parallel simulation scheme based on the distance between objects,Proc. SCS Multiconf. on Distributed Simulation, Vol. 21 (1989) pp. 113–118.
R. Baccelli and M. Canales, Parallel simulation of stochastic Petri nets using recurrence equations, ACM TOMACS 3(1993)20–41.
D. Ball and S. Hoyt, The adaptive Time-Warp concurrency control algorithm,Proc. SCS Multiconf. on Distributed Simulation, Vol. 20 (1990) pp. 174–177.
S. Bellenot, Global virtual time algorithms,Proc. SCS Multiconf. on Distributed Simulation, Vol. 22 (1990) pp. 122–127.
S. Bellenot, State skipping performance with the Time Warp operating system, in:6th Workshop on Parallel and Distributed Simulation, Vol. 24, SCS Simulation Series (1992) pp. 53–64.
B. Berkman and R. Ayani, Parallel simulation of multistage interconnection networks on an SIMD computer, in:Advances in Parallel and Distributed Simulation, Vol. 23, SCS Simulation Series (1991) pp. 133–140.
J.V. Briner, Parallel mixed-level simulation of digital circuits using virtual time, Ph.D. Thesis, Duke University, Durham, NC (1990).
R.E. Bryant, Simulation of packet communication architecture computer systems, MIT-LCS-TR-188, Massachusetts Institute of Technology (1977).
C.A. Buzzell, M.J. Robb and R.M. Fujimoto, Modular VME rollback hardware for Time Warp,Proc. SCS Multiconf. on Distributed Simulation, Vol. 22 (1990) pp. 153–156.
W. Cai and S.J. Turner, An algorithm for distributed discrete-event simulation — the “carrier null message” approach,Proc. SCS Multiconf. on Distributed Simulation, Vol. 22 (1990) pp. 3–8.
K.M. Chandy, A survey of analytic models of rollback and recovery strategies, IEEE Comp. 8(1975)40–47.
K.M. Chandy and R. Sherman, The conditional event approach to distributed simulation,Proc. SCS Multiconf. on Distributed Simulation, Vol. 21 (1989) pp. 93–99.
K.M. Chandy and R. Sherman, Space, time, and simulation,Proc. SCS Multiconf. on Distributed Simulation, Vol. 21 (1989) pp. 53–57.
K.M. Chandy and J. Misra, Distributed simulation: A case study in design and verification of distributed programs, IEEE Trans. Software Eng. SE-5(1979)440–452.
A.I. Concepcion, A hierarchical computer architecture for distributed simulation, IEEE Trans. Comp. C-38(1989)311–319.
S.R. Das and R.M. Fujimoto, A performance study of the cancelback protocol for Time Warp, Technical Report GIT-CC-92/50, College of Computing, Georgia Institute of Technology, Atlanta, GA (1992).
M. Davoren, A structural mapping for parallel difital logic simulation, in:Proc. SCS Multiconf. on Distributed Simulation, Vol. 21, SCS Simulation Series (1989) pp. 179–182.
E. DeBenedictis, S. Ghosh and M.-L. Yu, A novel algorithm for discrete-event simulation, Computer 24(6)(1991)21–33.
P.M. Dickens, Performance analysis of parallel simulations, Ph.D. Thesis, University of Virginia (1992).
S. Eick, A. Greenberg, B. Lubachevsky and A. Weiss, Synchronous relaxation for parallel simulations with applications to circuit-switched networks, in:Advances in Parallel and Distributed Simulation, Vol. 23, SCS Simulation Series (1991) pp. 151–162.
R. Felderman and L. Kleinrock, An upper bound on the improvement of asynchronous versus synchronous distributed processing, in:Distributed Simulation, Vol. 22, SCS Simulation Series (1990) pp. 131–136.
R. Felderman and L. Kleinrock, Bounds and approximations for self-initiating distributed simulation without lookahead, ACM Trans. Modeling Comp. Simul. 1(1991).
R. Felderman and L. Kleinrock, Two processor Time Warp analysis: Some results on a unifying approach, in:Advances in Parallel and Distributed Simulation, Vol. 23, SCS Simulation Series (1991) pp. 3–10.
M.A. Franklin, D.F. Wann and K.F. Wong, Parallel machines and algorithms for discrete-event simulation,Proc. 1984 Int. Conf. on Parallel Processing (1984) pp. 449–458.
R.M. Fujimoto, Time Warp on a shared memory multiprocessor, Trans. Soc. Comp. Simul. 6(1989)211–239.
R.M. Fujimoto, The virtual time machine,Int. Symp. on Parallel Algorithms and Architectures (1989) pp. 199–208.
R.M. Fujimoto, Parallel discrete event simulation, Commun. ACM 33(1990)30–53.
R.M. Fujimoto, J. Tsai and G. Gopalakrishnan, Design and evaluation of the rollback chip: Special purpose hardware for Time Warp, IEEE Trans. Comp. C-41(1992)68–82.
A. Gafni, Rollback mechanisms for optimistic distributed simulation systems,Proc. SCS Multiconf. on Distributed Simulation, Vol. 19 (1988) pp. 61–67.
B. Gaujal, A. Greenberg and D. Nicol, A sweep algorithm for massively parallel simulation of circuit-switched networks, ICASE Technical Report ICASE-92-30 (1992), to appear in J. Parallel Distr. Comp.
E. Gelenbe, On the optimum checkpoint interval, J. ACM 26(1979)259–270.
P.I. Georgiadis, M.P. Papazoglou and D.G. Maritsas, Towards a parallel simula machine,Proc. 8th Annual Symp. on Computer Architecture, Vol. 9 (1982) pp. 263–278.
K. Ghosh and R.M. Fujimoto, Parallel discrete event simulation using space-time memory,Proc. 1991 Int. Conf. on Parallel Processing, Vol. 3 (1991) pp. 201–208.
D.W. Glazer, Load balancing parallel discrete-event simulation, Ph.D. Thesis, McGill University (1992).
A. Goldberg, Virtual time synchronization of replicated processes, in:6th Workshop on Parallel and Distributed Simulation, Vol. 24, SCS Simulation Series (1992) pp. 107–116.
G. Gopalakrishnan and R.M. Fujimoto, Design and verification of the rollback chip using HOP: A case study of formal methods applied to hardware design, Technical Report UUCS-91-015, Department of Computer Science, University of Utah (1991).
A.G. Greenberg, B.D. Lubachevsky and I. Mitrani, Algorithms for unboundedly parallel simulations, ACM Trans. Comp. Syst. 9(1991)201–221.
A. Gupta, I.F. Akyildiz and R.M. Fujimoto, Performance analysis of Time Warp with multiple homogeneous processors, IEEE Trans. Software Eng. SE-17(1991)1013–1027.
P. Heidelberger and D. Nicol, Conservative parallel simulation of continuous time Markov chains using uniformization, IBM Technical Report RC-16780, IBM Research Division (1991), to appear in IEEE Trans. Parallel Distr. Syst.
P. Heidelberger and H. Stone, Parallel trace-driven cache simulation by time partitioning, IBM Technical Report RC-15500, IBM Research Division (1990).
D.R. Jefferson, Virtual time, ACM Trans. Progr. Languages Syst. 7(1985)404–425.
D.R. Jefferson, Virtual time II: Storage management in distributed simulation,Proc. 9th Annual ACM Symp. on Principles of Distributed Computing (1990) pp. 75–89.
D.S. Johnson, C.R. Aragon, L.A. McGeoch and C. Shevon, Optimization by simulated annealing: An experimental evaluation: Part I, graph partitioning, Oper. Res. 37(1989)865–892.
S.A. Kravitz and B.D. Ackland, Static vs. dynamic partitioning of circuits for a MOS timing simulator on a message-based multiprocessor, in:Proc. SCS Multiconf. on Distributed Simulation, Vol. 19, SCS Simulation Series (1988) pp. 136–140.
D. Kumar and S. Harous, An approach towards distributed simulation of timed Petri nets, in:Proc. 1990 Winter Simulation Conf., New Orleans, LA (1990) pp. 428–435.
F. Lin and R.M. Keller, The gradient model oad balancing method, IEEE Trans. Software Eng. SE-11(1987)32–38.
Y.-B. Lin, Memory management algorithms for optimistic parallel simulation, in:6th Workshop on Parallel and Distributed Simulation, Vol. 24, SCS Simulation Series (1992).
Y.-B. Lin and E.D. Lazowska, Optimality considerations of “Time Warp” parallel simulation, in:Distributed Simulation, Vol. 22, SCS Simulation Series (1990) pp. 29–34.
Y.-B. Lin and E.D. Lazowska, Determining the global virtual time in a distributed simulation, Technical Report 90-01-02, Department of Computer Science, University of Washington, Seattle, WA (1989).
Y.-B. Lin and E.D. Lazowska, Reducing the state saving overhead for Time Warp parallel simulation, Technical Report 90-02-03, Department of Computer Science, University of Washington, Seattle, WA (1990).
Y.-B. Lin and E.D. Lazowska, A time-division algorithm for parallel simulation, ACM Trans. Mod. Comp. Simul. 1(1991)73–83.
Y.-B. Lin, E.D. Lazowska and J.-L. Baer, Conservative parallel simulation for systems with no lookahead prediction,Proc. SCS Multiconf. on Distributed Simulation, Vol. 22 (1990) pp. 144–149.
Y.-B. Lin and E.D. Lazowska, A study of Time Warp mechanisms, ACM Trans. Mod. Comp. Simul. 1(1991)51–72.
Y.-B. Lin and E.D. Lazowska, A time-division algorithm for parallel simulation, ACM Trans. Mod. Comp. Simul. 1(1991)73–83.
R. Lipton and D. Mizell, Time Warp vs. Chandy-Misra: A worst-case comparison, in:Distributed Simulation, Vol. 22, SCS Simulation Series (1990) pp. 137–143.
B. Lubachevsky, A. Weiss and A. Shwartz, An analysis of rollback-based simulation, ACM Trans. Mod. Comp. Simul. 1(1991)154–192.
B.D. Lubachevsky, Scalability of the bounded lag distributed discrete event simulation,Proc. SCS Multiconf. on Distributed Simulation, Vol. 21 (1989) pp. 100–107.
B.D. Lubachevsky, A. Shwartz and A. Weiss, Rollback sometimes works ... if filtered,1989 Winter Simulation Conf. Proc. (1989) pp. 630–639.
V. Madissetti, D. Hardaker and R. Fujimoto, The mimdix operating system for parallel simulation, in:6th Workshop on Parallel and Distributed Simulation, Vol. 24, SCS Simulation Series (1992) pp. 65–74.
V. Madisetti, J. Walrand and D. Messerschmitt, Wolf: A rollback algorithm for optimistic distributed simulation systems,1988 Winter Simulation Conf. Proc. (1988) pp. 296–305.
J. Briner, Jr., Fast parallel simulation of digital systems, in:Advances in Parallel and Distributed Simulation, Vol. 23, SCS Simulation Series (1991) pp. 71–77.
P. Reynolds, Jr., An efficient framework for parallel simulations, in:Advances in Parallel and Distributed Simulation, Vol. 23, SCS Simulation Series (1991) pp. 167–174.
J. Misra, Distributed discrete-event simulation, ACM Comp. Surveys 18(1986)39–65.
B. Nandy and W. Loucks, An algorithm for partitioning and mapping conservative parallel simulation onto multicomputers, in:6th Workshop on Parallel and Distributed Simulation, Vol. 24, SCS Simulation Series (1992) pp. 139–146.
L.M. Ni, C.W. Zu and T.B. Gendreau, A distributed drafting algorithm for load balancing, IEEE Trans. Software Eng. SE-9(1985).
D. Nicol, Optimistic barrier synchronization, ICASE Technical Report 91–34 (1992).
D. Nicol, A. Greenberg, B. Lubachevsky and S. Roy, Massively parallel algorithms for trace-driven cache simulation, in:6th Workshop on Parallel and Distributed Simulation, Vol. 24, SCS Simulation Series (1992) pp. 3–11.
D. Nicol and P. Heidelberger, Optimistic parallel simulation of continuous time Markov chains using uniformization, J. Parallel Distr. Comp. 18(1993)395–410.
D. Nicol and P. Heidelberger, Parallel simulation of Markovian queueing networks using adaptive uniformization, in:Proc. 1993 SIGMETRICS Conf, Santa Clara, CA (1993) pp. 135–145.
D. Nicol and S. Roy, Parallel simulation of timed Petri nets, in:Proc. 1991 Winter Simulation Conf., Phoenix, AZ (1991) pp. 574–583.
D.M. Nicol, Performance bounds on parallel self-initiating discrete-event simulations, ACM Trans. Mod. Comp. Simul. 1(1991)24–50.
D.M. Nicol, The automated partitioning of simulations for parallel execution, Ph.D. Thesis, University of Virginia (1985).
D.M. Nicol, The cost of conservative synchronization in parallel discrete-event simulations, J. ACM 40(1993)304–333.
D.M. Nicol and P.F. Reynolds, Jr., A statistical approach to dynamic partitioning, in:Distributed Simulation 85, Vol. 15, SCS Simulation Series (1985) pp. 53–56.
D.M. Nicol and P.F. Reynolds, Jr., Optimal dynamic remapping of data parallel computations, IEEE Trans. Comp. C-39(1990)206–219.
C. Pancerella, Improving the efficiency of a framework for parallel simulations, in:6th Workshop on Parallel and Distributed Simulation, Vol. 24, SCS Simulation Series (1992) pp. 22–32.
B. Preiss, W. Loucks, I. MacIntyre and J. Field, Null message cancellation in conservative distributed simulation, in:Advances in Parallel and Distributed Simulation, Vol. 23, SCS Simulation Series (1991) pp. 33–38.
B. Preiss, I. MacIntyre and W. Loucks, On the trade-off between time and space in optimistic parallel discrete-event simulation, in:6th Workshop on Parallel and Distributed Simulation, Vol. 24, SCS Simulation Series (1992) pp. 33–42.
B.R. Preiss, The Yaddes distributed discrete event simulation specification language and execution environments,Proc. SCS Multiconf. on Distributed Simulation, Vol. 21 (1989) pp. 139–144.
P.L. Reiher and D. Jefferson, Dynamic load management in the Time Warp Operating System, Trans. Soc. Comp. Simul. 7(1990)91–120.
H.R. Ross,Stochastic Processes (Wiley, New York, 1983).
B. Samadi, Distributed simulation, algorithms and performance analysis, Ph.D. Thesis, University of California, Los Angeles (1985).
L.M. Sokol, D.P. Briscoe and A.P. Wieland, MTW: a strategy for scheduling discrete simulation events for concurrent execution,Proc. SCS Multiconf. on Distributed Simulation, Vol. 19 (1988) pp. 34–42.
L. Soule and A. Gupta, An evaluation of the Chandy-Misra-Byrant algorithm for digital logic simulation, ACM Trans. Mod. Comp. Simul. 1 (1991).
J. Steinman, Speedes: synchronous parallel environment for emulation and discrete event simulation, in:Advances in Parallel and Distributed Simulation, Vol. 23, SCS Simulation Series (1991) pp. 95–103.
W.K. Su and C.L. Seitz, Variants of the Chandy-Misra-Bryant distributed discrete-event simulation algorithm,Proc. SCS Multiconf. on Distributed Simulation, Vol. 21 (1989) pp. 38–43.
G. Thomas and J. Zahorjan, Parallel simulation of performance Petra nets: Extending the domain of parallel simulation, in:Proc. 1991 Winter Simulation Conf., Phoenix, AZ (1991) pp. 564–573.
S. Turner and M. Xu, Performance evaluation of the bounded Time Warp algorithm, in:6th Workshop on Parallel and Distributed Simulation, Vol. 24, SCS Simulation Series (1992) pp. 117–128.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Nicol, D., Fujimoto, R. Parallel simulation today. Ann Oper Res 53, 249–285 (1994). https://doi.org/10.1007/BF02136831
Issue Date:
DOI: https://doi.org/10.1007/BF02136831