Micro-Synchronization in Conservative Parallel Network Simulation

ABSTRACT

Lookahead is a critical factor in conservative parallel simulation. Greater lookahead usually brings better performance. However, in the simulation of computer networks, lookahead is usually determined by the minimal delay of the border links between any two subnets that simulated by different sequential logical processes (LPs), which is too small to get good performance. Traditionally, the lookahead exploitation usually only reflects the parallelism among LPs, which possibly wastes the potential parallelism inside each LP, especially, in the case that each LP simulates thousands of entities. Here we present a simple method called micro-synchronization to exploit the parallelism inside each LP. Different from the previous work, such as lookahead accumulation and local time warp, we keep the traditional usage of lookahead among LPs unchanged, and however, we impose the relaxed sequential event scheduling inside each LP, which can indirectly improve the lookahead. We also present a state causality model to prove the correctness of our method, which means that there is no risk in the relaxed sequential execution. Finally, the experiment evaluates our method and shows that it can improve the performance of conservative parallel simulation of computer networks to some extent.

REFERENCES

• 1: 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]
• 2: George F. Riley , Richard M. Fujimoto , Mostafa H. Ammar, A Generic Framework for Parallelization of Network Simulations, Proceedings of the 7th International Symposium on Modeling, Analysis and Simulation of Computer and Telecommunication Systems, p.128, March 24-28, 1999
• 3: R. M. Fujimoto, K. Perumalla, A. Park, H. Wu, M. H. Ammar, Large-Scale Network Simulation: How Big? How Fast? Proceedings of MASCOTS'03, 2003.
• 4: L. Bajaj, M. Takai, R. Ahuja, K. Tang, R. Bagrodia, and M. Gerla, GloMoSim: A Scalable Network Simulation Environment, Technical Report 990027, UCLA Computer Science Department, 1999.
• 5: Viliam Solcany , Jiri Safarik, The lookahead in a user-transparent conservative parallel simulator, Proceedings of the sixteenth workshop on Parallel and distributed simulation, May 12-15, 2002, Washington, D.C.
• 6: J. Lemeire, E. Dirkx, Lookahead Accumulation in Conservative Parallel Discrete Event Simulation, Proceedings 18th European Simulation Multiconference, SCS Europe, 2004.
• 7: Hassan Rajaei , Rassul Ayani , Lars-Erik Thorelli, The local Time Warp approach to parallel simulation, ACM SIGSIM Simulation Digest, v.23 n.1, p.119-126, July 1993
• 8: David M. Nicol, The cost of conservative synchronization in parallel discrete event simulations, Journal of the ACM (JACM), v.40 n.2, p.304-333, April 1993 [doi>10.1145/151261.151266]
• 9: Alfred Park , Richard M. Fujimoto , Kalyan S. Perumalla, Conservative synchronization of large-scale network simulations, Proceedings of the eighteenth workshop on Parallel and distributed simulation, May 16-19, 2004, Kufstein, Austria [doi>10.1145/1013329.1013355]
• 10: K. M. Chandy , J. Misra, Asynchronous distributed simulation via a sequence of parallel computations, Communications of the ACM, v.24 n.4, p.198-206, April 1981 [doi>10.1145/358598.358613]
• 11: Rassul Ayani , Hassan Rajaei, Parallel simulation using conservative time windows, Proceedings of the 24th conference on Winter simulation, p.709-717, December 13-16, 1992, Arlington, Virginia, United States [doi>10.1145/167293.167684]
• 12: 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]
• 13: David N. Nicol, High performance parallelized discrete event simulation of stochastic queueing networks, Proceedings of the 20th conference on Winter simulation, p.306-314, December 12-14, 1988, San Diego, California, United States [doi>10.1145/318123.318206]
• 14: Y. B. Lin , E. D. Lazowska, Exploiting Lookahead in Parallel Simulation, IEEE Transactions on Parallel and Distributed Systems, v.1 n.4, p.457-469, October 1990 [doi>10.1109/71.80174]
• 15: Ewa Deelman , Rajive Bagrodia , Rizos Sakellariou , Vikram Adve, Improving lookahead in parallel discrete event simulations of large-scale applications using compiler analysis, Proceedings of the fifteenth workshop on Parallel and distributed simulation, p.5-13, May 15-18, 2001, Lake Arrowhead, California, United States
• 16: Moo-Kyoung Chung , Chong-Min Kyung, Improving Lookahead in Parallel Multiprocessor Simulation Using Dynamic Execution Path Prediction, Proceedings of the 20th Workshop on Principles of Advanced and Distributed Simulation, p.11-18, May 24-26, 2006 [doi>10.1109/PADS.2006.20]
• 17: Francesco Quaglia , Roberto Baldoni, Exploiting intra-object dependencies in parallel simulation, Information Processing Letters, v.70 n.3, p.119-125, May 14, 1999 [doi>10.1016/S0020-0190(99)00056-3]
• 18: Boleslaw K. Szymanski , Yu Liu , Rashim Gupta, Parallel Network Simulation under Distributed Genesis, Proceedings of the seventeenth workshop on Parallel and distributed simulation, p.61, June 10-13, 2003
• 19: Song Luo , Gerald A. Marin, Simulating application level self-similar network traffic using hybrid heavy-tailed distributions, Proceedings of the 43rd annual Southeast regional conference, March 18-20, 2005, Kennesaw, Georgia [doi>10.1145/1167253.1167267]
• 20: G. Karypis. METIS: Family of Multilevel Partitioning Algorithms. http://glaros.dtc.umn.edu/gkhome/views/metis

INDEX TERMS

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

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Network communications

General Terms:
Design, Experimentation, Performance

Keywords:
parallel network simulation, conservative synchronization, lookahead, logical process