DyMeLoR: Dynamic Memory Logger and Restorer Library for Optimistic Simulation Objects with Generic Memory Layout

ABSTRACT

In this article we focus on checkpoint/restore facilities for optimistic simulation objects with generic memory layout. Specifically, we present the design and implementation of a {\tt C} library, named DyMeLoR (Dynamic Memory Logger and Restorer), that, beyond offering traditional services for dynamic memory allocation/release, additionally supports transparent checkpoint/restore of scattered simulation objects' states. DyMeLoR is well suited for being integrated within optimistic simulation platforms relying on kernel processes, each managing one or more simulation objects, as typical in most implementations of general purpose optimistic simulation platforms. From the point of view of efficiency, DyMeLoR has been designed in order to minimize memory consumption for meta-data describing the current layout of the simulation object's state, and to provide good trade-offs between the cost of meta-data manipulation and the cost of memory-to-memory data copies associated with checkpoint/restore tasks. Also, the library exhibits Piece-Wise-Deterministic (PWD) behavior, thus allowing the employment of (optimized) sparse checkpointing strategies each timethe overlying application software complies with the PWD assumption. We also report the results of an experimental study where DyMeLoR is integrated within the ROme OpTimistic Simulator (ROOT-Sim), and is used to support optimistic simulation of a cellular system.

REFERENCES

• 1: A memory allocator. http://g.oswego.edu/dl/html/malloc.html, 1996.
• 2: SPEEDES. http://www.speedes.com, 2005.
• 3: David W. Bauer , Ernest H. Page, An Approach for Incorporating Rollback through Perfectly Reversible Computation in a Stream Simulator, Proceedings of the 21st International Workshop on Principles of Advanced and Distributed Simulation, p.171-178, June 12-15, 2007 [doi>10.1109/PADS.2007.13]
• 4: Azzedine Boukerche , Sajal K. Das , Alessandro Fabbri , Oktay Yildiz, Exploiting model independence for parallel PCS network simulation, Proceedings of the thirteenth workshop on Parallel and distributed simulation, p.166-173, May 01-04, 1999, Atlanta, Georgia, United States
• 5: Christopher D. Carothers , Kalyan S. Perumalla , Richard M. Fujimoto, Efficient optimistic parallel simulations using reverse computation, ACM Transactions on Modeling and Computer Simulation (TOMACS), v.9 n.3, p.224-253, July 1999 [doi>10.1145/347823.347828]
• 6: Diego Cucuzzo , Stefano D'Alessio , Francesco Quaglia , Paolo Romano, A Lightweight Heuristic-based Mechanism for Collecting Committed Consistent Global States in Optimistic Simulation, Proceedings of the 11th IEEE International Symposium on Distributed Simulation and Real-Time Applications, p.227-234, October 22-26, 2007 [doi>10.1109/DS-RT.2007.9]
• 7: 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
• 8: Josef Fleischmann , Philip A. Wilsey, Comparative analysis of periodic state saving techniques in time warp simulators, Proceedings of the ninth workshop on Parallel and distributed simulation, p.50-58, June 13-16, 1995, Lake Placid, New York, United States
• 9: 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]
• 10: S. Kandukuri and S. Boyd. Optimal power control in interference-limited fading wireless channels with outage-probability specifications. IEEE Transactions on Wireless Communications, 1(1):46-55, 2002.
• 11: Dale E. Martin , Timothy J. McBrayer , Philip A. Wilsey, WARPED: A Time Warp Simulation Kernel for Analysis and Application Development, Proceedings of the 29th Hawaii International Conference on System Sciences (HICSS'96) Volume 1: Software Technology and Architecture, p.383, January 03-06, 1996
• 12: Andriy Naborskyy , Richard M. Fujimoto, Using Reversible Computation Techniques in a Parallel Optimistic Simulation of a Multi-Processor Computing System, Proceedings of the 21st International Workshop on Principles of Advanced and Distributed Simulation, p.179-188, June 12-15, 2007 [doi>10.1109/PADS.2007.31]
• 13: Kalyan S. Perumalla, µsik " A Micro-Kernel for Parallel/Distributed Simulation Systems, Proceedings of the 19th Workshop on Principles of Advanced and Distributed Simulation, p.59-68, June 01-03, 2005 [doi>10.1109/PADS.2005.1]
• 14: Bruno R. Preiss , Wayne M. Loucks , Ian D. Macintyre, Effects of the checkpoint interval on time and space in time warp, ACM Transactions on Modeling and Computer Simulation (TOMACS), v.4 n.3, p.223-253, July 1994 [doi>10.1145/189443.189444]
• 15: Francesco Quaglia, A Cost Model for Selecting Checkpoint Positions in Time Warp Parallel Simulation, IEEE Transactions on Parallel and Distributed Systems, v.12 n.4, p.346-362, April 2001 [doi>10.1109/71.920586]
• 16: Francesco Quaglia , Andrea Santoro, Nonblocking Checkpointing for Optimistic Parallel Simulation: Description and an Implementation, IEEE Transactions on Parallel and Distributed Systems, v.14 n.6, p.593-610, June 2003 [doi>10.1109/TPDS.2003.1206506]
• 17: Robert Rönngren , Rassul Ayani, Adaptive checkpointing in Time Warp, Proceedings of the eighth workshop on Parallel and distributed simulation, p.110-117, July 06-08, 1994, Edinburgh, Scotland, United Kingdom
• 18: Robert Rönngren , Michael Liljenstam , Rassul Ayani , Johan Montagnat, Transparent incremental state saving in time warp parallel discrete event simulation, Proceedings of the tenth workshop on Parallel and distributed simulation, p.70-77, May 22-24, 1996, Philadelphia, Pennsylvania, United States
• 19: Andrea Santoro , Francesco Quaglia, Transparent State Management for Optimistic Synchronization in the High Level Architecture, Proceedings of the 19th Workshop on Principles of Advanced and Distributed Simulation, p.171-180, June 01-03, 2005 [doi>10.1109/PADS.2005.34]
• 20: Andrea Santoro , Francesco Quaglia, A Version of MASM Portable Across Different UNIX Systems and Different Hardware Architectures, Proceedings of the 9th IEEE International Symposium on Distributed Simulation and Real-Time Applications, p.35-42, October 10-11, 2005 [doi>10.1109/DISTRA.2005.8]
• 21: Sven Sköld , Robert Rönngren, Event sensitive state saving in time warp parallel discrete event simulations, Proceedings of the 28th conference on Winter simulation, p.653-660, December 08-11, 1996, Coronado, California, United States [doi>10.1145/256562.256779]
• 22: Jeff S. Steinman, Incremental state saving in SPEEDES using C++, Proceedings of the 25th conference on Winter simulation, p.687-696, December 12-15, 1993, Los Angeles, California, United States [doi>10.1145/256563.256816]
• 23: Darrin West , Kiran Panesar, Automatic incremental state saving, Proceedings of the tenth workshop on Parallel and distributed simulation, p.78-85, May 22-24, 1996, Philadelphia, Pennsylvania, United States

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.6 SIMULATION AND MODELING
      I.6.7 Simulation Support Systems

Additional Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
        D.2.11 Software Architectures
            Subjects: Domain-specific architectures

General Terms:
Design, Performance, Reliability