On the processor scheduling problem in time warp synchronization

ABSTRACT

Time Warp is a synchronization mechanism for parallel/distributed simulation. It allows logical processes (LPs) to execute events without the guarantee of a causally consistent execution. Upon the detection of a causality violation, rollback procedures recover the state of the simulation to a correct value. When a rollback occurs there are two primary sources of performance loss: (1) CPU time must be spent for the execution of the rollback procedures and (2) waste of CPU time arises from the invalidation of event executions. In this paper we present a general framework for the problem of scheduling the next LP to be run on a processor in Time Warp simulations. The framework establishes a class of scheduling algorithms having the twofold aim to keep low the CPU time for the execution of the rollback procedures and also to guarantee low waste of time due to event executions invalidated by rollback. The combination of these two aims should actually lead to short completion time of Time Warp simulations.We collocate existing scheduling algorithms within the framework, pointing out how they miss previous aims, at least partially. Then we instantiate a Window-based Grain Sensitive (WGS) scheduling algorithm relying on the framework, which pursues the above twofold aim. We also identify the proper conditions, associated with the simulation model execution, under which any algorithm exploiting the framework structure is expected to benefit the performance of the Time Warp mechanism. Empirical evidence from an experimental study of WGS on classical benchmarks and on a mobile communication system simulation fully confirms the theoretical outcomes.

REFERENCES

• 1: Azzedine Boukerche , Sajal K. Das , Alessandro Fabbri , Oktay Yildiz, Exploiting model independence for parallel PCS network simulation, Proceedings of the thirteenth workshop on Parallel and distributed simulation, p.166-173, May 01-04, 1999, Atlanta, Georgia, United States
• 2: Christopher D. Carothers , David Bauer , Shawn Pearce, ROSS: a high-performance, low memory, modular time warp system, Proceedings of the fourteenth workshop on Parallel and distributed simulation, p.53-60, May 28-31, 2000, Bologna, Italy
• 3: Christopher D. Carothers , Richard M. Fujimoto , Yi-Bing Lin, A case study in simulating PCS networks using Time Warp, Proceedings of the ninth workshop on Parallel and distributed simulation, p.87-94, June 13-16, 1995, Lake Placid, New York, United States
• 4: Samir R. Das , Richard M. Fujimoto, An adaptive memory management protocol for Time Warp parallel simulation, Proceedings of the 1994 ACM SIGMETRICS conference on Measurement and modeling of computer systems, p.201-210, May 16-20, 1994, Nashville, Tennessee, United States
• 5: Samir R. Das , Richard M. Fujimoto, An Empirical Evaluation of Performance-Memory Trade-Offs in Time Warp, IEEE Transactions on Parallel and Distributed Systems, v.8 n.2, p.210-224, February 1997 [doi>10.1109/71.577269]
• 6: Alois Ferscha, Probabilistic adaptive direct optimism control in Time Warp, Proceedings of the ninth workshop on Parallel and distributed simulation, p.120-129, June 13-16, 1995, Lake Placid, New York, United States
• 7: A. Ferscha , J. Luthi, Estimating rollback overhead for optimism control in Time Warp, Proceedings of the 28th Annual Simulation Symposium, p.2, April 25-28, 1995
• 8: Richard M. Fujimoto, Parallel discrete event simulation, Communications of the ACM, v.33 n.10, p.30-53, Oct. 1990 [doi>10.1145/84537.84545]
• 9: Fujimoto, R. M. 1990b. Performance of Time Warp under synthetic workloads. In Proceedings of the Multiconference on Distributed Simulation. Society for Computer Simulation, 23--28.
• 10: Richard M. Fujimoto , Maria Hybinette, Computing global virtual time in shared-memory multiprocessors, ACM Transactions on Modeling and Computer Simulation (TOMACS), v.7 n.4, p.425-446, Oct. 1997 [doi>10.1145/268403.268404]
• 11: Gafni, A. 1985. Space management and cancellation mechanisms for Time Warp. Tech. Rep. TR-85-341, University of Southern California, Los Angeles (Ca,USA).
• 12: Hamnes, D. O. and Tripathi, A. 1994. Evaluation of a local adaptive protocol for distributed simulation. In Proceedings of the 1994 International Conference on Parallel Processing. CRC, 127--134.
• 13: David R. Jefferson, Virtual time, ACM Transactions on Programming Languages and Systems (TOPLAS), v.7 n.3, p.404-425, July 1985 [doi>10.1145/3916.3988]
• 14: Lin, Y. B. and Lazowska, E. D. 1991. Processor scheduling for Time Warp parallel simulation. In Advances in Parallel and Distributed Simulation. 11--14.
• 15: Edward Mascarenhas , Felipe Knop , Reuben Pasquini , Vernon Rego, Minimum cost adaptive synchronization: experiments with the ParaSol system, ACM Transactions on Modeling and Computer Simulation (TOMACS), v.8 n.4, p.401-430, Oct. 1998 [doi>10.1145/295251.295257]
• 16: MYRICOM. 1999. Lanai 4. Draft.
• 17: Scott Pakin , Mario Lauria , Andrew Chien, High performance messaging on workstations: Illinois fast messages (FM) for Myrinet, Proceedings of the 1995 ACM/IEEE conference on Supercomputing (CDROM), p.55-es, December 04-08, 1995, San Diego, California, United States [doi>10.1145/224170.224360]
• 18: Avinash C. Palaniswamy , Philip A. Wilsey, Scheduling time warp processes using adaptive control techniques, Proceedings of the 26th conference on Winter simulation, p.731-738, December 11-14, 1994, Orlando, Florida, United States
• 19: Bruno R. Preiss , Wayne M. Loucks , Ian D. Macintyre, Effects of the checkpoint interval on time and space in time warp, ACM Transactions on Modeling and Computer Simulation (TOMACS), v.4 n.3, p.223-253, July 1994 [doi>10.1145/189443.189444]
• 20: Preiss, B. R., MacIntyre, D., and Loucks, W. M. 1992. On the tradeoff between time and space in optimistic parallel discrete-event simulation. In Proceedings of the 6th Workshop on Parallel and Distributed Simulation. Society for Computer Simulation, 33--42.
• 21: Francesco Quaglia, A State-Based Scheduling Algorithm for Time Warp Synchronization, Proceedings of the 33rd Annual Simulation Symposium, p.14, April 16-22, 2000
• 22: Francesco Quaglia, A Cost Model for Selecting Checkpoint Positions in Time Warp Parallel Simulation, IEEE Transactions on Parallel and Distributed Systems, v.12 n.4, p.346-362, April 2001 [doi>10.1109/71.920586]
• 23: Paul F. Reynolds, Jr., A spectrum of options for parallel simulation, Proceedings of the 20th conference on Winter simulation, p.325-332, December 12-14, 1988, San Diego, California, United States [doi>10.1145/318123.318209]
• 24: Robert Rönngren , Rassul Ayani, Adaptive checkpointing in Time Warp, Proceedings of the eighth workshop on Parallel and distributed simulation, p.110-117, July 06-08, 1994, Edinburgh, Scotland, United Kingdom
• 25: Robert Rönngren , Rassul Ayani, Service oriented scheduling in Time Warp, Proceedings of the 26th conference on Winter simulation, p.1340-1346, December 11-14, 1994, Orlando, Florida, United States
• 26: Tapas K. Som , Robert G. Sargent, A probabilistic event scheduling policy for optimistic parallel discrete event simulation, Proceedings of the twelfth workshop on Parallel and distributed simulation, p.56-63, May 26-29, 1998, Banff, Alberta, Canada
• 27: Sudhir Srinivasan, NPSI adaptive synchronization algorithms for parallel discrete event simulation, University of Virginia, Charlottesville, VA, 1996
• 28: Sudhir Srinivasan , Margaret J. Lyell , Paul F. Reynolds, Jr. , Jeff Wehrwein, Implementation of reductions in support of PDES on a network of workstations, Proceedings of the twelfth workshop on Parallel and distributed simulation, p.116-123, May 26-29, 1998, Banff, Alberta, Canada
• 29: Sudhir Srinivasan , Paul F. Reynolds, Jr., Elastic time, ACM Transactions on Modeling and Computer Simulation (TOMACS), v.8 n.2, p.103-139, April 1998 [doi>10.1145/280265.280267]
• 30: Christopher H. Young , Nael B. Abu-Ghazaleh , Philip A. Wilsey, OFC: A Distributed Fossil-Collection Algorithm for Time-Warp, Proceedings of the 12th International Symposium on Distributed Computing, p.408-418, September 24-26, 1998

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Design studies

Additional Classification:
  C. Computer Systems Organization
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Modeling techniques

  D. Software
  D.4 OPERATING SYSTEMS
      D.4.1 Process Management
          Subjects: Scheduling

  I. Computing Methodologies
  I.6 SIMULATION AND MODELING
      I.6.8 Types of Simulation
          Subjects: Discrete event; Parallel

General Terms:
Algorithms, Experimentation, Performance

Keywords:
Optimistic synchronization