On extending more parallelism to serial simulators

ABSTRACT

The Utilitarian Parallel Simulator (U.P.S.) extends parallelism to the CSIM sequential simulation tool by providing several new modeling constructs. Using conservative synchronization techniques, these constructs automatically support time-synchronized communications between CSIM submodels running on different processors. This paper describes extensions to U.P.S. that allow the user to assist U.P.S. by providing additional "process lookahead," thereby reducing the frequency of synchronizations. The use and effect on performance of process lookahead is described for several models. In a mobile cellular communications model, the use of process lookahead results in up to a 60% improvement in speedup on 32 nodes of the IBM SP2. A factor of 3 improvement is obtained on a closed queueing network simulation running on 32 nodes of the Intel Paragon.

REFERENCES

• 1: 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]
• 2: Christopher D. Carothers , Richard M. Fujimoto , Yi-Bing Lin, A case study in simulating PCS networks using Time Warp, Proceedings of the ninth workshop on Parallel and distributed simulation, p.87-94, June 13-16, 1995, Lake Placid, New York, United States
• 3: Phillip M. Dickens , Philip Heidelberger , David M. Nicol, A distributed memory LAPSE: parallel simulation of message-passing programs, Proceedings of the eighth workshop on Parallel and distributed simulation, p.32-38, July 06-08, 1994, Edinburgh, Scotland, United Kingdom
• 4: P. Heidelberger , D. M. Nicol, Conservative Parallel Simulation of Continuous Time Markov Chains Using Uniformization, IEEE Transactions on Parallel and Distributed Systems, v.4 n.8, p.906-921, August 1993 [doi>10.1109/71.238625]
• 5: David M. Nicol, Parallel discrete-event simulation of FCFS stochastic queueing networks, Proceedings of the ACM/SIGPLAN conference on Parallel programming: experience with applications, languages and systems, p.124-137, July 19-21, 1988, New Haven, Connecticut, United States
• 6: GTU, Inc., Arlington, VA. CPSi~ i.O User's Guide and Reference Manual, June 1994.
• 7: Vikas Jha , Rajive L. Bagrodia, Transparent implementation of conservative algorithms in parallel simulation languages, Proceedings of the 25th conference on Winter simulation, p.677-686, December 12-15, 1993, Los Angeles, California, United States [doi>10.1145/256563.256814]
• 8: David Nicol , Philip Heidelberger, On extending parallelism to serial simulators, Proceedings of the ninth workshop on Parallel and distributed simulation, p.60-67, June 13-16, 1995, Lake Placid, New York, United States
• 9: D.M. Nicol and P. Heidelberger. Parallel execution for serial simulators. IBM Research Report RC-20205, Yorktown Heights, New York, 1995.
• 10: D. M. Nicol , C. C. Michael , P. Inouye, Efficient aggregation of multiple PLs in distributed memory parallel simulations, Proceedings of the 21st conference on Winter simulation, p.680-685, December 04-06, 1989, Washington, D.C., United States [doi>10.1145/76738.76825]
• 11: 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]
• 12: 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]

INDEX TERMS

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

General Terms:
Measurement, Performance, Theory

Keywords:
parallel simulation, queueing system, communications network