Capo: a software-hardware interface for practical deterministic multiprocessor replay

ABSTRACT

While deterministic replay of parallel programs is a powerful technique, current proposals have shortcomings. Specifically, software-based replay systems have high overheads on multiprocessors, while hardware-based proposals focus only on basic hardware-level mechanisms, ignoring the overall replay system. To be practical, hardware-based replay systems need to support an environment with multiple parallel jobs running concurrently -- some being recorded, others being replayed and even others running without recording or replay. Moreover, they need to manage limited-size log buffers.

This paper addresses these shortcomings by introducing, for the first time, a set of abstractions and a software-hardware interface for practical hardware-assisted replay of multiprocessor systems. The approach, called Capo, introduces the novel abstraction of the Replay Sphere to separate the responsibilities of the hardware and software components of the replay system. In this paper, we also design and build CapoOne, a prototype of a deterministic multiprocessor replay system that implements Capo using Linux and simulated DeLorean hardware. Our evaluation of 4-processor executions shows that CapoOne largely records with the efficiency of hardware-based schemes and the flexibility of software-based schemes.

REFERENCES

• 1: Hiralal Agrawal , Richard A. DeMillo , Eugene H. Spafford, An Execution-Backtracking Approach to Debugging, IEEE Software, v.8 n.3, p.21-26, May 1991 [doi>10.1109/52.88940]
• 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: Bob Boothe, Efficient algorithms for bidirectional debugging, Proceedings of the ACM SIGPLAN 2000 conference on Programming language design and implementation, p.299-310, June 18-21, 2000, Vancouver, British Columbia, Canada
• 4: T. C. Bressoud , F. B. Schneider, Hypervisor-based fault tolerance, Proceedings of the fifteenth ACM symposium on Operating systems principles, p.1-11, December 03-06, 1995, Copper Mountain, Colorado, United States
• 5: 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
• 6: Shyh-Kwei Chen , W. Kent Fuchs , Jen-Yao Chung, Reversible Debugging Using Program Instrumentation, IEEE Transactions on Software Engineering, v.27 n.8, p.715-727, August 2001 [doi>10.1109/32.940726]
• 7: George W. Dunlap , Samuel T. King , Sukru Cinar , Murtaza A. Basrai , Peter M. Chen, ReVirt: enabling intrusion analysis through virtual-machine logging and replay, Proceedings of the 5th symposium on Operating systems design and implementation

  Due to copyright restrictions we are not able to make the PDFs for this conference available for downloading

  , December 09-11, 2002, Boston, Massachusetts [doi>10.1145/1060289.1060309]
• 8: 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]
• 9: Stuart I. Feldman , Channing B. Brown, IGOR: a system for program debugging via reversible execution, Proceedings of the 1988 ACM SIGPLAN and SIGOPS workshop on Parallel and distributed debugging, p.112-123, May 05-06, 1988, Madison, Wisconsin, United States
• 10: Alessandro Forin, Debugging of heterogeneous parallel systems, Proceedings of the 1988 ACM SIGPLAN and SIGOPS workshop on Parallel and distributed debugging, p.130-140, May 05-06, 1988, Madison, Wisconsin, United States
• 11: Dave Hitz , James Lau , Michael Malcolm, File system design for an NFS file server appliance, Proceedings of the USENIX Winter 1994 Technical Conference on USENIX Winter 1994 Technical Conference, p.19-19, January 17-21, 1994, San Francisco, California
• 12: 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
• 13: Jong-Deok Choi , Harini Srinivasan, Deterministic replay of Java multithreaded applications, Proceedings of the SIGMETRICS symposium on Parallel and distributed tools, p.48-59, August 03-04, 1998, Welches, Oregon, United States [doi>10.1145/281035.281041]
• 14: Ashlesha Joshi , Samuel T. King , George W. Dunlap , Peter M. Chen, Detecting past and present intrusions through vulnerability-specific predicates, Proceedings of the twentieth ACM symposium on Operating systems principles, October 23-26, 2005, Brighton, United Kingdom
• 15: Samuel T. King , Peter M. Chen, Backtracking intrusions, Proceedings of the nineteenth ACM symposium on Operating systems principles, October 19-22, 2003, Bolton Landing, NY, USA
• 16: Samuel T. King , George W. Dunlap , Peter M. Chen, Debugging operating systems with time-traveling virtual machines, Proceedings of the annual conference on USENIX Annual Technical Conference, p.1-1, April 10-15, 2005, Anaheim, CA
• 17: 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]
• 18: Peter S. Magnusson , Magnus Christensson , Jesper Eskilson , Daniel Forsgren , Gustav Hållberg , Johan Högberg , Fredrik Larsson , Andreas Moestedt , Bengt Werner, Simics: A Full System Simulation Platform, Computer, v.35 n.2, p.50-58, February 2002 [doi>10.1109/2.982916]
• 19: 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
• 20: 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
• 21: Satish Narayanasamy , Gilles Pokam , Brad Calder, BugNet: Continuously Recording Program Execution for Deterministic Replay Debugging, Proceedings of the 32nd annual international symposium on Computer Architecture, p.284-295, June 04-08, 2005
• 22: 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
• 23: Douglas Z. Pan , Mark A. Linton, Supporting reverse execution for parallel programs, Proceedings of the 1988 ACM SIGPLAN and SIGOPS workshop on Parallel and distributed debugging, p.124-129, May 05-06, 1988, Madison, Wisconsin, United States
• 24: Mark Russinovich , Bryce Cogswell, Replay for concurrent non-deterministic shared-memory applications, Proceedings of the ACM SIGPLAN 1996 conference on Programming language design and implementation, p.258-266, May 21-24, 1996, Philadelphia, Pennsylvania, United States
• 25: Douglas S. Santry , Michael J. Feeley , Norman C. Hutchinson , Alistair C. Veitch , Ross W. Carton , Jacob Ofir, Deciding when to forget in the Elephant file system, Proceedings of the seventeenth ACM symposium on Operating systems principles, p.110-123, December 12-15, 1999, Charleston, South Carolina, United States
• 26: Sudarshan M. Srinivasan , Srikanth Kandula , Christopher R. Andrews , Yuanyuan Zhou, Flashback: a lightweight extension for rollback and deterministic replay for software debugging, Proceedings of the annual conference on USENIX Annual Technical Conference, p.3-3, June 27-July 02, 2004, Boston, MA
• 27: 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
• 28: 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
• 29: M. V. Zelkowitz, Reversible execution, Communications of the ACM, v.16 n.9, p.566, Sept. 1973 [doi>10.1145/362342.362360]

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.0 GENERAL
      Subjects: Hardware/software interfaces

Additional Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.4 Parallel Architectures

General Terms:
Design, Measurement, Performance

Keywords:
capo, capoone, deterministic replay, replay sphere