Take a look at the new version of this page: [ beta version ]. Tell us what you think.

ABSTRACT

A performance comparison between an optimistic and a conservative parallel simulation kernel is presented. Performance of the parallel kernels is also compared to a central-event-list sequential kernel. A spectrum of ATM network and traffic scenarios representative of those used by ATM networking researchers are used for the comparison. Experiments are conducted with a cell-level ATM network simulator and an 18-processor SGI PowerChallenge shared-memory multiprocessor. The results show the performance advantages of parallel simulation ove r sequential simulation for ATM networks. Speedups of 4-5 relative to a fast sequential kernel are achieved on 16 processors for several large irregular ATM benchmark scenarios and the optimistic kernel achieves 2 to 5 times speedup on all 7 benchmarks. However, the relative performance of the two parallel simulation kernels is dependent on the size of the ATM network, the number of traffic sources, and the traffic source types used in the simulation. For some benchmarks the best single point performance is provided by the conservative kernel even on a single processor. Unfortunately, the conservative kernel performance is susceptible to small changes in the modeling code and is outperformed by the optimistic kernel on 5 of the 7 benchmarks. The optimistic parallel simulation kernel thus provides most robust performance, but its speedup is limited by the overheads of its implementation, which make it approximately half the speed of the sequential kernel on one processor.

REFERENCES

• 1: ARLITT, M., CHEN, Y., GURSKI, R., AND WILLIAMSON, C. 1995. Traffic modeling in the ATM-TN telesim project: Design, implementation, and performance evaluation. In Proceedings of the 1995 Summer Conference on Computer Simulation (SCSC'95, Ottawa, Ont.). 847-851.
• 2: ARLITT, M. AND WILLIAMSON, C. 1995. A synthetic workload model for internet mosaic traffic. In Proceedings of the 1995 Summer Conference on Computer Simulation (SCSC'95, Ottawa, Ont.). 852-857.
• 3: Martin F. Arlitt , Carey L. Williamson, Internet Web servers: workload characterization and performance implications, IEEE/ACM Transactions on Networking (TON), v.5 n.5, p.631-645, Oct. 1997 [doi>10.1109/90.649565]
• 4: ATM FORUM. 1996. Traffic management 4.0 specification. ATM Forum Technical Committee.
• 5: Hervé Avril , Carl Tropper, Clustered time warp and logic simulation, Proceedings of the ninth workshop on Parallel and distributed simulation, p.112-119, June 13-16, 1995, Lake Placid, New York, United States [doi>10.1145/214282.214317]
• 6: R. L. Bagrodia , Wen-Toh Liao, Maisie: A Language for the Design of Efficient Discrete-Event Simulations, IEEE Transactions on Software Engineering, v.20 n.4, p.225-238, April 1994 [doi>10.1109/32.277572]
• 7: T. D. Blanchard , T. W. Lake , S. J. Turner, Cooperative acceleration: robust conservative distributed discrete event simulation, ACM SIGSIM Simulation Digest, v.24 n.1, p.58-64, July 1994 [doi>10.1145/195291.182494]
• 8: R. Brown, Calendar queues: a fast 0(1) priority queue implementation for the simulation event set problem, Communications of the ACM, v.31 n.10, p.1220-1227, Oct. 1988 [doi>10.1145/63039.63045]
• 9: Wentong Cai , Emmanuelle Letertre , Stephen J. Turner, Dag consistent parallel simulation: a predictable and robust conservative algorithm, ACM SIGSIM Simulation Digest, v.27 n.1, p.178-181, July 1997 [doi>10.1145/268823.268918]
• 10: Christopher D. Carothers , Richard M. Fujimoto , Yi-Bing Lin, A case study in simulating PCS networks using Time Warp, ACM SIGSIM Simulation Digest, v.25 n.1, p.87-94, July 1995 [doi>10.1145/214283.214309]
• 11: 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.
• 12: Yu-an Chen , Rajive Bagrodia, Shared memory implementation of a parallel switch-level circuit simulator, ACM SIGSIM Simulation Digest, v.28 n.1, p.134-141, July 1998 [doi>10.1145/278009.278025]
• 13: CHEN, Y., DENG, Z., AND WILLIAMSON, C. 1995. A model for self-similar Ethernet lan traffic: Design, implementation, and performance implications. In Proceedings of the 1995 Summer Conference on Computer Simulation (SCSC'95, Ottawa, Ont.). 831-837.
• 14: John G. Cleary , Jya-Jang Tsai, Conservative parallel simulation of ATM networks, ACM SIGSIM Simulation Digest, v.26 n.1, p.30-38, July 1996 [doi>10.1145/238793.238807]
• 15: Mark E. Crovella , Azer Bestavros, Self-similarity in World Wide Web traffic: evidence and possible causes, ACM SIGMETRICS Performance Evaluation Review, v.24 n.1, p.160-169, May 1996 [doi>10.1145/233008.233038]
• 16: Samir R. Das , Richard M. Fujimoto, A performance study of the cancelback protocol for Time Warp, ACM SIGSIM Simulation Digest, v.23 n.1, p.135-142, July 1993 [doi>10.1145/174134.158476]
• 17: Samir Das , Richard Fujimoto , Kiran Panesar , Don Allison , Maria Hybinette, GTW: a time warp system for shared memory multiprocessors, Proceedings of the 26th conference on Winter simulation, p.1332-1339, December 11-14, 1994, Orlando, Florida, United States
• 18: FUJIMOTO, R. M. 1989. Time warp on a shared memory multiprocessor. In Proceedings of the International Conference on Parallel Processing (ICPP '89, Aug.). Pennsylvania State University, University Park, PA, 242-249.
• 19: 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]
• 20: Mark W. Garrett , Walter Willinger, Analysis, modeling and generation of self-similar VBR video traffic, ACM SIGCOMM Computer Communication Review, v.24 n.4, p.269-280, Oct. 1994 [doi>10.1145/190809.190339]
• 21: Fabian Anthony Francis Bosco Gomes , Brian Unger, Optimizing incremental state-saving and restoration, 1996
• 22: Fabian Gomes , John Cleary , Alan Covington , Steve Franks , Brian Unger , Zhong-e Ziao, SimKit: a high performance logical process simulation class library in C++, Proceedings of the 27th conference on Winter simulation, p.706-713, December 03-06, 1995, Arlington, Virginia, United States [doi>10.1145/224401.224714]
• 23: GURSKI, R. AND WILLIAMSON, C. 1996. TCP over ATM: Simulation model and performance results. In Proceedings of the 1996 IEEE International Conference on Computers and Communications (Phoenix, AZ, Mar.). IEEE Computer Society Press, Los Alamitos, CA, 328-335.
• 24: 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]
• 25: D. Jefferson , B. Beckman , F. Wieland , L. Blume , M. Diloreto, Time warp operating system, Proceedings of the eleventh ACM Symposium on Operating systems principles, p.77-93, November 08-11, 1987, Austin, Texas, United States [doi>10.1145/41457.37508]
• 26: Didier Le Gall, MPEG: a video compression standard for multimedia applications, Communications of the ACM, v.34 n.4, p.46-58, April 1991 [doi>10.1145/103085.103090]
• 27: Will E. Leland , Murad S. Taqqu , Walter Willinger , Daniel V. Wilson, On the self-similar nature of Ethernet traffic (extended version), IEEE/ACM Transactions on Networking (TON), v.2 n.1, p.1-15, Feb. 1994 [doi>10.1109/90.282603]
• 28: MARTINE, D., WILSEY, P., AND MCBRAYER, T. 1995. WARPED (version 0.5). University of Cincinnati, Cincinnati, OH.
• 29: William M. McCormack , Robert G. Sargent, Analysis of future event set algorithms for discrete event simulation, Communications of the ACM, v.24 n.12, p.801-812, Dec. 1981 [doi>10.1145/358800.358803]
• 30: MELAMED, B. 1992. TES modeling of video traffic. IEICE Trans. Fundam. Electron. Commun. Comput. Sci. E75-B, 1292-1300.
• 31: Richard A. Meyer , Rajive L. Bagrodia, Improving Lookahead in Parallel Wireless Network Simulation, Proceedings of the 6th International Symposium on Modeling, Analysis and Simulation of Computer and Telecommunication Systems, p.262, July 19-24, 1998
• 32: Steven E. Minzer, Broadband ISDN and asynchronous transfer mode (ATM), Broadband switching: architectures, protocols, design, and analysis, IEEE Computer Society Press, Los Alamitos, CA, 1991
• 33: 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]
• 34: David Nicol , Philip Heidelberger, On extending more parallelism to serial simulators, ACM SIGSIM Simulation Digest, v.26 n.1, p.202-205, July 1996 [doi>10.1145/238793.238849]
• 35: PATEL, A. AND WILLIAMSON, C. 1997. Effective bandwidth of self-similar traffic sources: Theoretical and simulation results. In Proceedings of the IASTED Conference on Applied Modeling and Simulation (Banff, AB, Canada, July). 298-302.
• 36: Vern Paxson , Sally Floyd, Wide area traffic: the failure of Poisson modeling, IEEE/ACM Transactions on Networking (TON), v.3 n.3, p.226-244, June 1995 [doi>10.1109/90.392383]
• 37: C. D. Pham , H. Brunst , S. Fdida, Conservative simulation of load-balanced routing in a large ATM network model, ACM SIGSIM Simulation Digest, v.28 n.1, p.142-149, July 1998 [doi>10.1145/278009.278026]
• 38: STEINMAN, J. 1992. SPEEDES: A unified approach to parallel simulation. In Proceedings of the 6th Workshop on Parallel and Distributed Simulation (PADS '92). ACM Press, New York, NY.
• 39: W. Richard Stevens, TCP/IP illustrated (vol. 1): the protocols, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1993
• 40: SU, W. AND SEITZ, C. 1989. Variants of the Chandy-Misra-Bryant distributed discrete-event simulation algorithm. In Proceedings of the Conference on Distributed Simulation (Miami, FL).
• 41: Andrew S. Tanenbaum, Computer networks (3rd ed.), Prentice-Hall, Inc., Upper Saddle River, NJ, 1996
• 42: Seng Chuan Tay , Yong Meng Teo , Rassul Ayani, Performance analysis of time warp simulation with cascading rollbacks, ACM SIGSIM Simulation Digest, v.28 n.1, p.30-37, July 1998 [doi>10.1145/278009.278013]
• 43: 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]
• 44: Gregory K. Wallace, The JPEG still picture compression standard, Communications of the ACM, v.34 n.4, p.30-44, April 1991 [doi>10.1145/103085.103089]
• 45: Yanping Wang , Carey Williamson , Julie Doerksen, CAC Performance with Self-Similar Traffic: Simulation Study and Performance Results, Proceedings of the 7th International Symposium on Modeling, Analysis and Simulation of Computer and Telecommunication Systems, p.102, March 24-28, 1999
• 46: Frederick Wieland , Eric Blair , Tony Zukas, Parallel Discrete-Event Simulation (PDES): a case study in design, development, and performance using SPEEDES, ACM SIGSIM Simulation Digest, v.25 n.1, p.103-110, July 1995 [doi>10.1145/214283.214315]
• 47: WILLIAMSON, C., UNGER, B., AND XIAO, Z. 1998. Parallel simulation of ATM networks: Case study and lessons learned. In Proceedings of the Second Canadian Conference on Broadband Research (CCBR '98, Ottawa, Ont., June). 78-88.
• 48: Z. Xiao F. Gomes , B. Unger , J. Cleary, A fast asynchronous GVT algorithm for shared memory multiprocessor architectures, Proceedings of the ninth workshop on Parallel and distributed simulation, p.203-208, June 13-16, 1995, Lake Placid, New York, United States [doi>10.1145/214282.214350]
• 49: XIAO, Z. AND UNGER, B. 1995a. Notes on parallelizing ATM-TN cell-level simulation models. Tech. rep. 98-629-20. University of Calgary, Calgary, Canada.
• 50: XIAO, Z. AND UNGER, B. 1995b. Report on WarpKit: Performance study and improvement. Tech. rep. 98-628-19. University of Calgary, Calgary, Canada.
• 51: 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
• 52: Xiang Zeng , Rajive Bagrodia , Mario Gerla, GloMoSim: a library for parallel simulation of large-scale wireless networks, ACM SIGSIM Simulation Digest, v.28 n.1, p.154-161, July 1998 [doi>10.1145/278009.278027]
• 53: Milan Zoranovic , Carey Williamson, Performance and Robustness Testing of Explicit-Rate ABR Flow Control Schemes, Proceedings of the 7th International Symposium on Modeling, Analysis and Simulation of Computer and Telecommunication Systems, p.10, March 24-28, 1999

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.1 PROCESSOR ARCHITECTURES
      C.1.2 Multiple Data Stream Architectures (Multiprocessors)
          Subjects: Single-instruction-stream, multiple-data-stream processors (SIMD); Multiple-instruction-stream, multiple-data-stream processors (MIMD)
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Asynchronous Transfer Mode (ATM)

General Terms:
Experimentation, Performance

Keywords:
ATM network modeling, conservative synchronization, optimistic synchronization, parallel discrete event simulation, time warp