Di-DyMeLoR: Logging only Dirty Chunks for Efficient Management of Dynamic Memory Based Optimistic Simulation Objects

ABSTRACT

A recent work has presented the design and implementation of a software library, named DyMeLoR, supporting transparent log/restore facilities for optimistic simulation objects with generic memory layout. This library offers the possibility to allocate/deallocate memory chunks via standard API, and performs log/restore of the object state via pack/unpack techniques,exploiting ad-hoc meta-data concisely identifying the object state layout at each point in simulation time. In this paper we complement such a library with a software architecture offering the following additional advantages: (i) run-time identification of chunk updates within the dynamic memory map,(ii) reduced checkpoint latency and increased effectiveness in memory usage thanks to log/restore facilities based on (periodic) snapshots of the whole simulation object state, taken via the incremental copy of the modified (dirty) chunks only.Our approach is based on software instrumentation techniques (suited for LINUX and the ELF format), targeting memory update references performed by the application level software, and on a lightweight run-time monitoring mechanism providing minimal overhead while tracking the exact memory addresses and the size of memory areas dirtied by the execution of each event. Also,our design has been oriented to portability across 32-bit and64-bit Intel compliant architectures, thus covering a wide spectrum of off-the-shelf machines.

REFERENCES

• 1: GDB: The GNU Project Debugger. http://www.gnu.org/software/gdb/.
• 2: A memory allocator. http://g.oswego.edu/dl/html/malloc.html, 1996.
• 3: SPEEDES. http://www.speedes.com, 2005.
• 4: Vasanth Bala , Evelyn Duesterwald , Sanjeev Banerjia, Dynamo: a transparent dynamic optimization system, Proceedings of the ACM SIGPLAN 2000 conference on Programming language design and implementation, p.1-12, June 18-21, 2000, Vancouver, British Columbia, Canada
• 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: Steve Franks , Fabian Gomes , Brian Unger , John Cleary, State saving for interactive optimistic simulation, Proceedings of the eleventh workshop on Parallel and distributed simulation, p.72-79, June 10-13, 1997, Lockenhaus, Austria
• 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: 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]
• 12: Feng Qin , Cheng Wang , Zhenmin Li , Ho-seop Kim , Yuanyuan Zhou , Youfeng Wu, LIFT: A Low-Overhead Practical Information Flow Tracking System for Detecting Security Attacks, Proceedings of the 39th Annual IEEE/ACM International Symposium on Microarchitecture, p.135-148, December 09-13, 2006 [doi>10.1109/MICRO.2006.29]
• 13: 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]
• 14: 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
• 15: 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
• 16: 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]
• 17: 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]
• 18: Hussam M. Soliman , Adel Said Elmaghraby, An Analytical Model for Hybrid Checkpointing in Time Warp Distributed Simulation, IEEE Transactions on Parallel and Distributed Systems, v.9 n.10, p.947-951, October 1998 [doi>10.1109/71.730524]
• 19: 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]
• 20: Roberto Toccaceli , Francesco Quaglia, DyMeLoR: Dynamic Memory Logger and Restorer Library for Optimistic Simulation Objects with Generic Memory Layout, Proceedings of the 22nd Workshop on Principles of Advanced and Distributed Simulation, p.163-172, June 03-06, 2008 [doi>10.1109/PADS.2008.23]
• 21: Robert Wahbe , Steven Lucco , Susan L. Graham, Practical data breakpoints: design and implementation, Proceedings of the ACM SIGPLAN 1993 conference on Programming language design and implementation, p.1-12, June 21-25, 1993, Albuquerque, New Mexico, United States
• 22: 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
• 23: Q. Zhao, R. M. Rabbah, S. P. Amarasinghe, L. Rudolph, and W.-F. Wong. How to do a million watchpoints: Efficient debugging using dynamic instrumentation. In L. J. Hendren, editor, CC, volume 4959 of Lecture Notes in Computer Science, pages 147-162. Springer, 2008.

INDEX TERMS

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

Additional Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
        D.2.11 Software Architectures
        D.2.13 Reusable Software
            Subjects: Reusable libraries
  D.4 OPERATING SYSTEMS
      D.4.2 Storage Management
          Subjects: Allocation/deallocation strategies

  I. Computing Methodologies
  I.6 SIMULATION AND MODELING
      I.6.5 Model Development
          Subjects: Modeling methodologies

General Terms:
Algorithms, Design, Performance, Theory

Keywords:
Optimistic simulation, Incremental checkpointing, Performance optimization