Lock-free scheduling of logical processes in parallel simulation

ABSTRACT

With fixed lookahead information in a simulation model, the overhead of asynchronous conservative parallel simulation lies in the mechanism used for propagating time updates in order for logical processes to safely advance their local simulation clocks. Studies have shown that a good scheduling algorithm should preferentially schedule processes containing events on the critical path. This paper introduces a lock-free algorithm for scheduling logical processes in conservative parallel discrete-event simulation on shred-memory multiprocessor machines. The algorithm uses fetch & add operations that help avoid inefficiencies associated with using locks. The lock-free algorithm is robust. Experiments show that, compared with the scheduling algorithm using locks, the lock-free algorithm exhibits better performance when the number of logical processes assigned to each processor is small or when the workload becomes significant. In models with large number of logical processes, our algorithm shows only modest increase in execution time due to the overhead in the algorithm for extra bookkeeping.

REFERENCES

• 1: K. M. Chandy and J. Misra. Distributed simulation: a case study in design and verification of distributed programs. 1EEE Transactions on Software Engineering, SE-5(5):440- 52, 1979.
• 2: 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]
• 3: Maurice Herlihy, Wait-free synchronization, ACM Transactions on Programming Languages and Systems (TOPLAS), v.13 n.1, p.124-149, Jan. 1991 [doi>10.1145/114005.102808]
• 4: David Jefferson , Peter Reiher, Supercritical speedup, Proceedings of the 24th annual symposium on Simulation, p.159-168, April 1991, New Orleans, Louisiana, United States
• 5: 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]
• 6: Jason Liu , David Nicol , Brian J. Premore , Anna L. Poplawski, Performance prediction of a parallel simulator, Proceedings of the thirteenth workshop on Parallel and distributed simulation, p.156-164, May 01-04, 1999, Atlanta, Georgia, United States
• 7: Xiaowen Liu , David M. Nicol , King Tan, Lock-free Scheduling of Logical Processes in Parallel Simulation, Dartmouth College, Hanover, NH, 2001
• 8: John M. Mellor-Crummey , Michael L. Scott, Algorithms for scalable synchronization on shared-memory multiprocessors, ACM Transactions on Computer Systems (TOCS), v.9 n.1, p.21-65, Feb. 1991 [doi>10.1145/103727.103729]
• 9: Edwin Naroska , Uwe Schwiegelshohn, A New Scheduling Method for Parallel Discrete-Event Simulation, Proceedings of the Second International Euro-Par Conference on Parallel Processing-Volume II, p.582-593, August 26-29, 1996
• 10: David Nicol , Jason Liu , James Cowie, Safe timestamps and large-scale modeling, Proceedings of the fourteenth workshop on Parallel and distributed simulation, p.71-78, May 28-31, 2000, Bologna, Italy
• 11: David M. Nicol, Principles of conservative parallel simulation, Proceedings of the 28th conference on Winter simulation, p.128-135, December 08-11, 1996, Coronado, California, United States [doi>10.1145/256562.256591]
• 12: Ha Yoon Song , Richard A. Meyer , Rajive Bagrodia, An empirical study of conservative scheduling, Proceedings of the fourteenth workshop on Parallel and distributed simulation, p.165-172, May 28-31, 2000, Bologna, Italy
• 13: John David Valois, Lock-free data structures, Rensselaer Polytechnic Institute, Troy, NY, 1996
• 14: Z. Xiao , B. Unger , R. Simmonds , J. Cleary, Scheduling critical channels in conservative parallel discrete event simulation, Proceedings of the thirteenth workshop on Parallel and distributed simulation, p.20-28, May 01-04, 1999, Atlanta, Georgia, United States

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Scheduling

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Sequencing and scheduling

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

General Terms:
Algorithms, Design, Experimentation, Measurement, Performance, Reliability, Theory, Verification