Conservative simulation using distributed-shared memory

ABSTRACT

This paper focuses on conservative simulation using distributed-shared memory for inter-processor communication. JavaSpaces, a special service of Java Jini, provides a shared persistent memory for simulation message communication among processors. Two benchmark programs written using our SPaDES/Java parallel simulation library are used. The first program is a linear pipeline system representing a loosely-coupled open system. The PHOLD program represents a strongly-connected closed system. Experiments are carried out using a cluster of Pentium II PCs. We used a combination of Wood Turner carrier null, flushing and demand-driven algorithms for null message synchronization. To optimize message communication, we replace SPaDES/Java inter-processor communication implemented using Java's Remote Method Invocation (RMI) with one JavaSpace. For PHOLD (16x16, 16) running on eight processors, this change reduces simulation runtime by more than half, null message overhead reduces by a further 15%, and event rate more than doubled. Based on our memory analysis methodology, the memory cost of null message synchronization for PHOLD is less than 9% of the total memory needed by the simulation.

REFERENCES

• 1: Rassul Ayani , Hassan Rajaei, Parallel simulation using conservative time windows, Proceedings of the 24th conference on Winter simulation, p.709-717, December 13-16, 1992, Arlington, Virginia, United States [doi>10.1145/167293.167684]
• 2: Rajive L. Bagrodia, Perils and pitfalls of parallel discrete-event simulation, Proceedings of the 28th conference on Winter simulation, p.136-143, December 08-11, 1996, Coronado, California, United States [doi>10.1145/256562.256592]
• 3: W. L. Bain, and D. S. Scott, "An Algorithm for Time Synchronization in Distributed Discrete Event Simulation", Proceedings of the SCS Multiconference on Distributed Simulation, 19, 3 (February), pp. 30-33, 1988.
• 4: Lokesh Bajaj , Rajive Bargrodia , Richard Meyer, Case study: parallelizing a sequential simulation model, Proceedings of the thirteenth workshop on Parallel and distributed simulation, p.29-36, May 01-04, 1999, Atlanta, Georgia, United States
• 5: P. Bizarro, L. M. Silva and J. G. Silva, "JWarp: A Java Library For Parallel Discrete-Event Simulations", Proceedings of the ACM Workshop on Java for High-Performance Network Computing, 1998.
• 6: W. T. Cai, and S. J. Turner, "An Algorithm for Distributed Discrete Event Simulation - The Carrier Null Message Approach", Proceedings of the SCS Multiconference on Distributed Simulation, pp. 3-8, 1990.
• 7: K. M. Chandy and J. Misra, "Distributed Simulation: A case study in design and verification of distributed programs", IEEE Transactions on Software Engineering, SE-5:5, pp. 440-452, 1979.
• 8: Thomas T. Cormen , Charles E. Leiserson , Ronald L. Rivest, Introduction to algorithms, MIT Press, Cambridge, MA, 1990
• 9: A. Ferscha, Parallel and distributed simulation of discrete event systems, a chapter in the Handbook of Parallel and Distributed Computing, McGraw-Hill, 1995.
• 10: 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]
• 11: R. M. Fujimoto, "Performance of Time Warp under Synthetic Workload", Proceedings of the SCS Multiconference on Distributed Simulation, 22, 1, 1990.
• 12: R. M. Fujimoto, Parallel and Distributed Simulation Systems, Wiley Series on Parallel and Distributed Computing, Wiley-Interscience, pg. 51-95, 2000.
• 13: F. W. Howell, P. E. Heywood, and R. N. Ibbett, "Hase: A flexible toolset for computer architects", Computer Journal, vol. 38, pp. 755-764, 1995.
• 14: S. Hupfer, The Nuts and Bolts of Compiling and Running JavaSpaces Programs, Java Developer Connection, Sun Microsystems, Inc., 2000.
• 15: 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]
• 16: D. R. Jefferson and H. Sowizral, "Fast concurrent simulation using the Time Warp mechanism". Tech. Rep. N-1906-AF, RAND Corporation, 1982.
• 17: Leslie Lamport, Time, clocks, and the ordering of events in a distributed system, Communications of the ACM, v.21 n.7, p.558-565, July 1978 [doi>10.1145/359545.359563]
• 18: Jayadev Misra, Distributed discrete-event simulation, ACM Computing Surveys (CSUR), v.18 n.1, p.39-65, March 1986 [doi>10.1145/6462.6485]
• 19: David M. Nicol, Parallel discrete-event simulation of FCFS stochastic queueing networks, ACM SIGPLAN Notices, v.23 n.9, p.124-137, Sept. 1988
• 20: S. C. Tay, Parallel Simulation Algorithm and Performance Analysis, PhD Thesis, Department of Computer Science, National University of Singapore, 1998.
• 21: Yong Meng Teo , Seng Chuan Tay , Siew Theng Kong, Structured Parallel Simulation Modeling and Programming, Proceedings of the The 31st Annual Simulation Symposium, p.135, April 05-09, 1998
• 22: Y. M. Teo , B. S. S. Onggo , S. C. Tay, Effect of Event Orderings on Memory Requirement in Parallel Simulation, Proceedings of the Ninth International Symposium in Modeling, Analysis and Simulation of Computer and Telecommunication Systems (MASCOTS'01), p.41, August 15-18, 2001
• 23: Yong Meng Teo , Yew Kwong Ng, SPaDES/Java: Object-Oriented Parallel Discrete-Event Simulation, Proceedings of the 35th Annual Simulation Symposium, p.245, April 14-18, 2002
• 24: Kenneth R. Wood , Stephen J. Turner, A generalized carrier-null method for conservative parallel simulation, Proceedings of the eighth workshop on Parallel and distributed simulation, p.50-57, July 06-08, 1994, Edinburgh, Scotland, United Kingdom