Minimum cost adaptive synchronization: experiments with the ParaSol system

ABSTRACT

We present a novel adaptive synchronization algorithm, called the minimum average cost (MAC) algorithm, in the context of the parasol parallel simulation system. ParaSol is a multithreaded system for parallel simulation on shared- and distributed-memory environments, designed to support domain-specific Simulation Object Libraries. The proposed MAC algorithm is based on minimizing the cost of synchronization delay and rollback at a process, whenever its simulation driver must decide whether to either proceed optimistically or to delay processing. In the former case the risk is rollback cost, in the event of a straggler's arrival. In the latter case the risk is unnecessary delay, in the event a latecomer is not a straggler. In addition to the MAC algorithm and an optimal delay computation model, we report on some early experiments comparing the performance of MAC-based adaptive synchronization to optimistic synchronization.

REFERENCES

• 1: BALL, D. AND HOYT, S. 1990. The adaptive time-warp concurrency control algorithm. In Proceedings of the SCS MultiConference on Distributed Simulation (San Diego, CA, Jan 17-19), 174-177.
• 2: CHANDY, K.M. AND MISRA, J. 1979. Distributed simulation: A case study in design and verification of distributed programs. IEEE Trans. Softw. Eng. 5, 5 (Sept.), 440-452.
• 3: 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
• 4: DICKENS, P. M. AND REYNOLDS, P. F., JR. 1990. SRADS with local rollback. In Proceedings of the SCS Multiconference on Distributed Simulation (San Diego, CA, Jan. 17-19), Vol. 22, 161-164.
• 5: 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
• 6: FERSCHA, A. AND CHIOLA, G. 1994. Self adaptive logical processes: The probabilistic distributed simulation protocol. In Proceedings of the 27th Annual Simulation Symposium (La Jolla, CA, Apr. 11-15), IEEE Computer Society Press, Los Alamitos, CA, 78-88.
• 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: R. L. Gimarco, Distributed simulation using hierarchical rollback, Proceedings of the 21st conference on Winter simulation, p.621-629, December 04-06, 1989, Washington, D.C., United States [doi>10.1145/76738.76818]
• 10: Donald O. Hamnes , Anand Tripathi, Investigations in adaptive distributed simulation, Proceedings of the eighth workshop on Parallel and distributed simulation, p.20-23, July 06-08, 1994, Edinburgh, Scotland, United Kingdom
• 11: Raj Jain , Imrich Chlamtac, The P2 algorithm for dynamic calculation of quantiles and histograms without storing observations, Communications of the ACM, v.28 n.10, p.1076-1085, Oct. 1985 [doi>10.1145/4372.4378]
• 12: D. Jefferson , B. Beckman , F. Wieland , L. Blume , M. Diloreto, Time warp operating system, ACM SIGOPS Operating Systems Review, v.21 n.5, p.77-93, Nov. 1987
• 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: Felipe Knop , Vernon J. Rego, Software architectures for fault-tolerant replications and multithreaded decompositions: experiments with practical parallel simulation, 1996
• 15: Averill M. Law , W. David Kelton, Simulation Modeling and Analysis, McGraw-Hill Higher Education, 1997
• 16: B. Lubachevsky , A. Shwartz , A. Weiss, Rollback sometimes works...if filtered, Proceedings of the 21st conference on Winter simulation, p.630-639, December 04-06, 1989, Washington, D.C., United States [doi>10.1145/76738.76819]
• 17: Vijay Madisetti , Jean Walrand , David Messerschmitt, Wolf: a rollback algorithm for optimistic distributed simulation systems, Proceedings of the 20th conference on Winter simulation, p.296-305, December 12-14, 1988, San Diego, California, United States [doi>10.1145/318123.318205]
• 18: MADISETTI, V. K., HARDAKER, D. A., AND FUJIMOTO, R. 1992. The MIMDIX operating system for parallel simulation. In Proceedings of the Sixth Workshop on Parallel and Distributed Simulation (Newport Beach, CA, Jan. 20-22), Vol. 24, 65-74.
• 19: Edward Mascarenhas , Vernon Rego, A system for multithreaded parallel simulation and computation with migrant threads and objects, 1996
• 20: MASCARENHAS, E. AND REGO, V. 1996. Ariadne: Architecture of a portable threads system supporting thread migration. Softw. Pract. Exper. 26, 3 (March), 327-356.
• 21: PRAKASH, A. AND SUBRAMANIAN, R. 1991. An efficient optimistic distributed simulation scheme based on conditional knowledge. In Proceedings of the 24th Annual Simulation Symposium (New Orleans, LA., Apr.), 85-94.
• 22: P. L. Reiher , F. Wieland , D. Jefferson, Limitation of optimism in the time warp operating system, Proceedings of the 21st conference on Winter simulation, p.765-770, December 04-06, 1989, Washington, D.C., United States [doi>10.1145/76738.76834]
• 23: L. E. Scales, Introduction to non-linear optimization, Springer-Verlag New York, Inc., New York, NY, 1985
• 24: Herb Schwetman, CSIM: a C-based process-oriented simulation language, Proceedings of the 18th conference on Winter simulation, p.387-396, December 08-10, 1986, Washington, D.C., United States [doi>10.1145/318242.318464]
• 25: SOKOL, L. M., BRISCOE, D. P., AND WIELAND, A.P. 1988. MTW: A strategy for scheduling discrete simulation events for concurrent execution. In Proceedings of the SCS Multiconference on Distributed Simulation, Vol. 19 (July), 34-42.
• 26: Sudhir Srinivasan , Paul F. Reynolds, Jr., NPSI adaptive synchronization algorithms for PDES, Proceedings of the 27th conference on Winter simulation, p.658-665, December 03-06, 1995, Arlington, Virginia, United States [doi>10.1145/224401.224705]
• 27: STEINMAN, J.S. 1992. SPEEDES: A unified approach to parallel simulation. In Proceedings of the Sixth Workshop on Parallel and Distributed Simulation (San Diego, CA, Jan. 17-19), 75-84.
• 28: Jeff S. Steinman, Breathing Time Warp, Proceedings of the seventh workshop on Parallel and distributed simulation, p.109-118, May 16-19, 1993, San Diego, California, United States
• 29: V. S. Sunderam, PVM: a framework for parallel distributed computing, Concurrency: Practice and Experience, v.2 n.4, p.315-339, Dec. 1990 [doi>10.1002/cpe.4330020404]
• 30: TURNER, S.J. AND XU, M.Q. 1992. Performance evaluation of the bounded time warp algorithm. In Proceedings of the Sixth Workshop on Parallel and Distributed Simulation (Newport Beach, CA, Jan. 20-22), Vol. 24, 117-126.

INDEX TERMS

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

General Terms:
Algorithms, Experimentation, Performance

Keywords:
ParaSol, adaptive synchronization, optimal delay, optimistic synchronization, parallel and distributed simulation, stochastic simulation, thread