Two hardware-based approaches for deterministic multiprocessor replay

ABSTRACT

Modern computer systems are inherently nondeterministic due to a variety of events that occur during an execution, including I/O, interrupts, and DMA fills. The lack of repeatability that arises from this nondeterminism can make it difficult to develop and maintain correct software. Furthermore, it is likely that the impact of nondeterminism will only increase in the coming years, as commodity systems are now shared-memory multiprocessors. Such systems are not only impacted by the sources of nondeterminism in uniprocessors, but also by the outcome of memory races among concurrent threads.

In an effort to help ease the pain of developing software in a nondeterministic environment, researchers have proposed adding deterministic replay capabilities to computer systems. A system with a deterministic replay capability can record sufficient information during an execution to enable a replayer to (later) create an equivalent execution despite the inherent sources of nondeterminism that exist. With the ability to replay an execution verbatim, many new applications may be possible:

Debugging: Deterministic replay could be used to provide the illusion of a time-travel debugger that has the ability to selectively execute both forward and backward in time.

Security: Deterministic replay could also be used to enhance the security of software by providing the means for an in-depth analysis of an attack, hopefully leading to rapid patch deployment and a reduction in the economic impact of new threats.

Fault Tolerance: With the ability to replay an execution, it may also be possible to develop hot-standby systems for critical service providers using commodity hardware. A virtual machine (VM) could, for example, be fed, in real time, the replay log of a primary server running on a physically separate machine. The standby VM could use the replay log to mimic the primary's execution, so that in the event that the primary fails, the backup can take over operation with almost zero downtime.

REFERENCES

• 1: Alameldeen, A.R., Mauer, C.J., Xu, M., Harper, P.J., Martin, M.M.K., Sorin, D.J., Hill, M.D., Wood, D.A. Evaluating non-deterrninistic multithreaded commercial workloads. In Proceedings of the 5th Workshop on Computer Architecture Evaluation Using Commercial Workloads (February 2002), 30--38
• 2: David F. Bacon , Seth Copen Goldstein, Hardware-assisted replay of multiprocessor programs, Proceedings of the 1991 ACM/ONR workshop on Parallel and distributed debugging, p.194-206, May 20-21, 1991, Santa Cruz, California, United States
• 3: Luis Ceze , James Tuck , Pablo Montesinos , Josep Torrellas, BulkSC: bulk enforcement of sequential consistency, Proceedings of the 34th annual international symposium on Computer architecture, June 09-13, 2007, San Diego, California, USA
• 4: George W. Dunlap , Dominic G. Lucchetti , Michael A. Fetterman , Peter M. Chen, Execution replay of multiprocessor virtual machines, Proceedings of the fourth ACM SIGPLAN/SIGOPS international conference on Virtual execution environments, March 05-07, 2008, Seattle, WA, USA [doi>10.1145/1346256.1346273]
• 5: Lance Hammond , Vicky Wong , Mike Chen , Brian D. Carlstrom , John D. Davis , Ben Hertzberg , Manohar K. Prabhu , Honggo Wijaya , Christos Kozyrakis , Kunle Olukotun, Transactional Memory Coherence and Consistency, Proceedings of the 31st annual international symposium on Computer architecture, p.102, June 19-23, 2004, München, Germany
• 6: Derek R. Hower , Mark D. Hill, Rerun: Exploiting Episodes for Lightweight Memory Race Recording, Proceedings of the 35th International Symposium on Computer Architecture, p.265-276, June 21-25, 2008
• 7: 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]
• 8: T. J. LeBlanc , J. M. Mellor-Crummey, Debugging Parallel Programs with Instant Replay, IEEE Transactions on Computers, v.36 n.4, p.471-482, April 1987 [doi>10.1109/TC.1987.1676929]
• 9: Brandon Lucia , Joseph Devietti , Karin Strauss , Luis Ceze, Atom-Aid: Detecting and Surviving Atomicity Violations, Proceedings of the 35th International Symposium on Computer Architecture, p.277-288, June 21-25, 2008
• 10: Milo M. K. Martin , Daniel J. Sorin , Bradford M. Beckmann , Michael R. Marty , Min Xu , Alaa R. Alameldeen , Kevin E. Moore , Mark D. Hill , David A. Wood, Multifacet's general execution-driven multiprocessor simulator (GEMS) toolset, ACM SIGARCH Computer Architecture News, v.33 n.4, November 2005 [doi>10.1145/1105734.1105747]
• 11: Pablo Montesinos , Luis Ceze , Josep Torrellas, DeLorean: Recording and Deterministically Replaying Shared-Memory Multiprocessor Execution Ef?ciently, Proceedings of the 35th International Symposium on Computer Architecture, p.289-300, June 21-25, 2008
• 12: Satish Narayanasamy , Cristiano Pereira , Brad Calder, Recording shared memory dependencies using strata, Proceedings of the 12th international conference on Architectural support for programming languages and operating systems, October 21-25, 2006, San Jose, California, USA
• 13: Robert H. B. Netzer, Optimal tracing and replay for debugging shared-memory parallel programs, Proceedings of the 1993 ACM/ONR workshop on Parallel and distributed debugging, p.1-11, May 17-18, 1993, San Diego, California, United States
• 14: Renau, J., Fraguela, B., Tuck, J., Liu, W., Prvulovic, M., Ceze, L., Sarangi, S., Sack, P., Strauss, K., Montesinos, P. SESC Simulator (January 2005), http://sesc.sourceforge.net.
• 15: Vallejo, E., Galluzzi, M., Cristal, A., Vallejo, F., Beivide, R., Stenstrom, P., Smith, J.E., Valero, M. Implementing kilo-instruction multiprocessors. In Proceedings of the 2005 International Conference on Pervasive Systems (July 2005).
• 16: Min Xu , Rastislav Bodik , Mark D. Hill, A "flight data recorder" for enabling full-system multiprocessor deterministic replay, Proceedings of the 30th annual international symposium on Computer architecture, June 09-11, 2003, San Diego, California
• 17: Min Xu , Mark D. Hill , Rastislav Bodik, A regulated transitive reduction (RTR) for longer memory race recording, Proceedings of the 12th international conference on Architectural support for programming languages and operating systems, October 21-25, 2006, San Jose, California, USA
• 18: Xu, M., Malyugin, V., Sheldon, J., Venkitachalam, G., Weissman, B. Retrace: Collecting execution trace with virtual machine deterministic replay. In Proceedings of the 3rd Annual Workshop on Modeling, Benchmarking and Simulation (June 2007).

INDEX TERMS

Primary Classification:
  B. Hardware
  B.3 MEMORY STRUCTURES
      B.3.m Miscellaneous

Additional Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.1 Types and Design Styles
  B.8 Performance and Reliability
      B.8.2 Performance Analysis and Design Aids