Massively parallel simulations of ATM systems

ABSTRACT

We simulate models of ATM communication systems on a massively parallel SIMD computer. Fast simulations of ATM models are needed because the regimes of interest usually involve high volumes of traffic and low failure rates. Unexpected practical and theoretical difficulties, partly due to the massive parallelism and SIMD aspects, were encountered and we show how to cope with them. In a replica-parallel simulation of an ATM system, large variations in computed statistics are caused by small differences in the distribution of employed random number generators. A comparison of these distributions using a secondary statistical measure served to disambiguate the results. It was also found that time-parallel simulations of ATM systems with Markov sources can be efficiently performed using parallel prefix methods only when the sources have a small number of states, while more complex sources require end-state matching for efficient simulation. We discovered that, with the proper choice of initial state distributions and partial regeneration points, the time and memory requirements can be much improved. Our simulations were carried out on the MasPar MP-1216 system with 16,384 processors, which was compared against an SGI workstation. We achieved about 60%-70% efficiency (speed-up of approx 35 compared to the ideal of approx 51).

REFERENCES

• 1: K. M. Chandy and R. Sherman. Spacetime and simulation. Proceedings of the 1989 SCS Multiconference on Distributed Simulation, pages 53-57, March 1989.
• 2: Anwar Elwalid, Debasis Mitra, and Robert H. Wentworth. A new approach for allocating buffers and bandwidth to heterogenous, regulated tramc in an atm node. IEEE Journal on Selected Areas in Communications, 13(6):1115-1127, Aug. 1995.
• 3: 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]
• 4: Richard M. Fujimoto, C. Anthony Cooper, and Ioanis Nikolaidis. Parallel simulation of statistical multiplexers. 32nd IEEE Conference on Decision and Control, 1993.
• 5: Albert G. Greenberg , Boris D. Lubachevsky , Isi Mitrani, Unboundedly parallel simulations via recurrence relations, Proceedings of the 1990 ACM SIGMETRICS conference on Measurement and modeling of computer systems, p.1-12, April 1990, Univ. of Colorado, Boulder, Colorado, United States
• 6: Fred J. Kaudel, A literature survey on distributed discrete event simulation, ACM SIGSIM Simulation Digest, v.18 n.2, p.11-21, June 1987 [doi>10.1145/29497.29499]
• 7: Yi-Bing Lin , Edward D. Lazowska, A time-division algorithm for parallel simulation, ACM Transactions on Modeling and Computer Simulation (TOMACS), v.1 n.1, p.73-83, Jan. 1991 [doi>10.1145/102810.214307]

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

General Terms:
Theory

Keywords:
replica-parallel, time-parallel, parallel prefix, markov sources, order statistics, random sampling