The APOSTLE simulation language: granularity control and performance data

ABSTRACT

A simulation-oriented language can significantly enhance the usability of Parallel Discrete Event Simulation (PDES) by hiding the complexities of the synchronization protocol used to ensure that events are processed in the correct order. The higher-level interface presented to the user by such a language also allows optimizations to be performed that are difficult and cumbersome with current parallel simulators, such as granularity control. APOSTLE is a new high-level simulation-oriented language for PDES, and in this paper we report that the APOSTLE granularity control mechanism reduced simulation run-times by as much as 80%. We also report that APOSTLE achieved a parallel speed-up of around 9 on 16 processors relative to its optimized sequential implementation and a parallel speed-up of around 6 on 16 processors relative to MODSIM II. Overall, we believe that the widespread success of PDES can only be achieved using a simulation-oriented language, and that APOSTLE has made a significant contribution towards this goal.

REFERENCES

• 1: Sten Andler, Predicate path expressions, Proceedings of the 6th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.226-236, January 29-31, 1979, San Antonio, Texas [doi>10.1145/567752.567774]
• 2: Baezner, D.; et al. "Sim++TM: The Transition to Distributed Simulation". In Proc. SCS Multiconf. on Distributed Simulation (San Diego, California, 17-19 January 1990). 211-218.
• 3: R. Bagrodia , K. M. Chandy , Wen Toh Liao, A unifying framework for distributed simulation, ACM Transactions on Modeling and Computer Simulation (TOMACS), v.1 n.4, p.348-385, Oct. 1991 [doi>10.1145/130611.130614]
• 4: 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]
• 5: Mary L. Bailey , Jack V. Briner, Jr. , Roger D. Chamberlain, Parallel logic simulation of VLSI systems, ACM Computing Surveys (CSUR), v.26 n.3, p.255-294, Sept. 1994 [doi>10.1145/185403.185424]
• 6: Edwin Blake , Steve Cook, On including part hierarchies in object-oriented languages, with an implementation in Smalltalk, European conference on object-oriented programming on ECOOP '87, p.41-50, October 1987, Paris, France
• 7: T. D. Blanchard , T. W. Lake, Distributed simulation with locality, Proceedings of the ninth workshop on Parallel and distributed simulation, p.195-198, June 13-16, 1995, Lake Placid, New York, United States
• 8: Booth, C. J. M.; et al. "Experiences in Implementing the Breathing Time Buckets Algorithm on a Transputer Array". In Proc. IASTED International Conference on Modelling and Simulation, (Pittsburgh, Pennsylvania, 10-12 May 1993). 274-277.
• 9: David Bruce, The treatment of state in optimistic systems, Proceedings of the ninth workshop on Parallel and distributed simulation, p.40-49, June 13-16, 1995, Lake Placid, New York, United States
• 10: Buhr, P. A. 1995. "Are Safe Concurrency Libraries Possible?". Communications of the ACM, vol. 38, no. 2, 117-120.
• 11: CACI. 1991. "MODSIM IITM Reference Manual", CACI Products Company, La Jolla, California.
• 12: Damitio, M.; et al. "Comparing the Breathing Time Buckets Algorithm and the Time Warp Operating System on a Transputer Architecture". In Proc. of the European Simulation MultiConf. (Barcelona, Spain, 1-3 June 1994). 141-145.
• 13: John B. Evans, Structures of discrete event simulation: an introduction to the engagement strategy, Halsted Press, New York, NY, 1988
• 14: Fujimoto, R. M. 1993. "Parallel Discrete Event Simulation: Will the Field Survive?". ORSA Journal on Computing, vol. 5, no. 3 (Summer), 213-230.
• 15: Hoare, E; et al. "The Application of High Performance Parallel Computing to Military Simulation". In Proc. 1995 Simulation Multiconf. (Military, Government and Aerospace Simulation) (Phoenix, Arizona, 9-13 April 1995). 115-119.
• 16: Henry Lieberman, Using prototypical objects to implement shared behavior in object-oriented systems, Conference proceedings on Object-oriented programming systems, languages and applications, p.214-223, September 29-October 02, 1986, Portland, Oregon, United States
• 17: B. Liskov , L. Shrira, Promises: linguistic support for efficient asynchronous procedure calls in distributed systems, Proceedings of the ACM SIGPLAN 1988 conference on Programming Language design and Implementation, p.260-267, June 20-24, 1988, Atlanta, Georgia, United States
• 18: J. Eliot B. Moss, Working with Persistent Objects: To Swizzle or Not to Swizzle, IEEE Transactions on Software Engineering, v.18 n.8, p.657-673, August 1992 [doi>10.1109/32.153378]
• 19: Richard E. Nance, A history of discrete event simulation programming languages, The second ACM SIGPLAN conference on History of programming languages, p.149-175, April 20-23, 1993, Cambridge, Massachusetts, United States
• 20: Rich, D. O. and R. E. Michelsen. 1989. Writing Parallel Discrete- Event Simulations in ModSim: Insight and Experience. Technical Report LA-UR-89-3104, Los Alamos National Laboratory, Los Alamos, New Mexico 87545.
• 21: David O. Rich , Randy E. Michelsen, An assessment of the ModSim/TWOS parallel simulation environment, Proceedings of the 23rd conference on Winter simulation, p.509-518, December 08-11, 1991, Phoenix, Arizona, United States
• 22: Steinman, J. S. 1992. "SPEEDES: A Multiple-Synchronization Environment for Parallel Discrete-Event Simulation". International Journal of Computer Simulation, vol. 2, no. 3, 251-286.
• 23: Jean G. Vaucher, A “WAIT UNTIL” algorithm for general purpose simulation languages, Proceedings of the 6th conference on Winter simulation, p.77-83, January 17-19, 1973, San Francisco, CA [doi>10.1145/800293.811565]
• 24: Waldorf, J. and R. Bagrodia. 1994. "MOOSE: A Concurrent Object-Oriented Language for Simulation". International Journal in Computer simulation, vol. 4, no. 2, 235-257.
• 25: Peter Wegner, Desgin Issues for Object-Based Concurrency, Proceedings of the Workshop on Object-Based Concurrent Computing, p.245-256, July 15-16, 1991
• 26: Wonnacott, P. and D. Bruce. "The design of ,4POST/_E- a highlevel, object-oriented language for parallel and distributed discrete event simulation", in Proc. 1995 Western Multiconf. on Computer Simulation (Object Oriented Simulation) (Las Vegas, Nevada, 16-18 January 1995). 101-106.
• 27: Wonnacott, P. and D. Bruce. "A prototype implementation of AlaOSrLE, and its performance". In Proc. 1995 Summer Computer Simulation Conf. (Ottawa, Canada, 24-26 July 1995). 197-205.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.6 SIMULATION AND MODELING

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES

General Terms:
Measurement, Performance, Theory

Keywords:
Parallel discrete event simulation, discrete event simulation languages, granularity control