Addressing blocking and scalability in critical channel traversing

ABSTRACT

This paper presents two new versions of the Critical Channel Traversing (CCT) algorithm. CCT is a conservative parallel discrete event simulation algorithm that has been shown to achieve very high performance when used in a wide area computer network simulator. The first of the new algorithms called simple sender side CCT is similar to the original, but busy waiting is eliminated. Results presented show that simple sender side CCT avoids performance problems that can be caused by busy waiting.The second new algorithm called receive side CCT employs a different strategy for updating channel clocks and determining which objects should be scheduled on critical channels. Performance results show that this version provides better scaling with respect to the connectivity of the model, at the expense of some added complexity.

REFERENCES

• 1: R. E. Bryant, SIMULATION OF PACKET COMMUNICATION ARCHITECTURE COMPUTER SYSTEMS, Massachusetts Institute of Technology, Cambridge, MA, 1977
• 2: K. M. Chandy and J. Misra. Distributed simulation : A case study in design and verification of distributed simulation. IEEE Transactions on Software Engineering, 5(5):440-452, September 1979.
• 3: John G. Cleary , Jya-Jang Tsai, Performance of a conservative simulator of ATM networks, Proceedings of the eleventh workshop on Parallel and distributed simulation, p.142-145, June 10-13, 1997, Lockenhaus, Austria
• 4: David E. Culler , Anoop Gupta , Jaswinder Pal Singh, Parallel Computer Architecture: A Hardware/Software Approach, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1997
• 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: Bil Lewis , Daniel J. Berg, Multithreaded programming with Pthreads, Prentice-Hall, Inc., Upper Saddle River, NJ, 1998
• 7: Jason Liu , David M. Nicol , King Tan, Lock-free scheduling of logical processes in parallel simulation, Proceedings of the fifteenth workshop on Parallel and distributed simulation, p.22-31, May 15-18, 2001, Lake Arrowhead, California, United States
• 8: 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]
• 9: Rob Simmonds , Cameron Kiddle , Kitty Wong , Brian Unger, Controlling Buffer Usage in Critical Channel Traversing, Proceedings of the 35th Annual Simulation Symposium, p.53, April 14-18, 2002
• 10: Brian W. Unger , Fabian Gomes , Xiao Zhonge , Pawel Gburzynski , Theodore Ono-Tesfaye , Srinivasan Ramaswamy , Carey Williamson , Alan Covington, A high fidelity ATM traffic and network simulator, Proceedings of the 27th conference on Winter simulation, p.996-1003, December 03-06, 1995, Arlington, Virginia, United States [doi>10.1145/224401.224763]
• 11: 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

Keywords:
conservative algorithms, parallel discrete event simulation, performance