Cyrus: unintrusive application-level record-replay for replay parallelism
Authors: 
Nima Honarmand, Nathan Dautenhahn, Josep Torrellas, Samuel T. King, Gilles Pokam, Cristiano PereiraAuthors Info & Claims
Pages 193 - 206
Abstract
Architectures for deterministic record-replay (R&R) of multithreaded code are attractive for program debugging, intrusion analysis, and fault-tolerance uses. However, very few of the proposed designs have focused on maximizing replay speed -- a key enabling property of these systems. The few efforts that focus on replay speed require intrusive hardware or software modifications, or target whole-system R&R rather than the more useful application-level R&R.
This paper presents the first hardware-based scheme for unintrusive, application-level R&R that explicitly targets high replay speed. Our scheme, called Cyrus, requires no modification to commodity snoopy cache coherence. It introduces the concept of an on-the-fly software Backend Pass during recording which, as the log is being generated, transforms it for high replay parallelism. This pass also fixes-up the log, and can flexibly trade-off replay parallelism for log size. We analyze the performance of Cyrus using full system (OS plus hardware) simulation. Our results show that Cyrus has negligible recording overhead. In addition, for 8-processor runs of SPLASH-2, Cyrus attains an average replay parallelism of 5, and a replay speed that is, on average, only about 50% lower than the recording speed.
References
[1]
H. Agrawal et al. An Execution-Backtracking Approach to Debugging. IEEE Software, 8(3), May 1991.
[2]
G. Altekar and I. Stoica. ODR: Output-deterministic replay for multicore debugging. In Symposium on Operating Systems Principles, 2009.
[3]
A. Basu et al. Karma: Scalable deterministic record-replay. In Int. Conference on Supercomputing, 2011.
[4]
B. Bloom. Space/Time Trade-Offs in Hash Coding with Allowable Errors. Communications of the ACM, 11(7), July 1970.
[5]
T. Bressoud and F. Schneider. Hypevisor-based fault-tolerance. ACM Transactions on Computer Systems, 14(1), Feb 1996.
[6]
A. Charlesworth. Starfire: Extending the SMP Envelope. IEEE Micro, 18(1), Jan. 1998.
[7]
Y. Chen et al. LReplay: A pending period based deterministic replay scheme. In Int. Symposium on Computer Architecture, 2010.
[8]
J.-D. Choi and H. Srinivasan. Deterministic replay of Java multithreaded applications. In Symposium on Parallel and Distributed Tools, 1998.
[9]
B. Cully et al. Remus: High availability via asynchronous virtual machine replication. In USENIX Symposium on Networked Systems Design and Implementation, 2008.
[10]
G. W. Dunlap et al. ReVirt: Enabling intrusion analysis through virtual-machine logging and replay. In Symposium on Operating Systems Design and Implementation, 2002.
[11]
G. W. Dunlap et al. Execution replay of multiprocessor virtual machines. In Int. Conference on Virtual Execution Environments, 2008.
[12]
A. Forin. Debugging of heterogeneous parallel systems. In Workshop on Parallel and Distributed Debugging, 1988.
[13]
D. R. Hower and M. D. Hill. Rerun: Exploiting Episodes for Lightweight Memory Race Recording. In Int. Symposium on Computer Architecture, 2008.
[14]
S. T. King and P. M. Chen. Backtracking intrusions. In Symposium on Operating Systems Principles, 2003.
[15]
S. T. King et al. Debugging operating systems with time-traveling virtual machines. In USENIX Annual Technical Conference, 2005.
[16]
O. Laadan et al. Transparent, lightweight application execution replay on commodity multiprocessor operating systems. In SIGMETRICS Int. Conference on Measurement and Modeling of Computer Systems, 2010.
[17]
L. Lamport. Time, clocks, and the ordering of events in a distributed system. Communications of the ACM, 21(7), July 1978.
[18]
T. J. LeBlanc and J. M. Mellor-Crummey. Debugging Parallel Programs with Instant Replay. IEEE Trans. Comput., 36(4), Apr. 1987.
[19]
D. Lee et al. Offline symbolic analysis for multi-processor execution replay. In Int. Symposium on Microarchitecture, 2009.
[20]
D. Lee et al. Respec: Efficient online multiprocessor replayvia speculation and external determinism. In Int. Conference on Architectural Support for Programming Languages and Operating Systems, 2010.
[21]
D. Lee et al. Offline symbolic analysis to infer Total Store Order. In Int. Symposium on High Performance Computer Architecture, 2011.
[22]
P. S. Magnusson et al. Simics: A Full System Simulation Platform. IEEE Computer, 35(2), February 2002.
[23]
P. Montesinos et al. DeLorean: Recording and Deterministically Replaying Shared-Memory Multiprocessor Execution Efficiently. In Int. Symposium on Computer Architecture, 2008.
[24]
P. Montesinos et al. Capo: A software-hardware interface for practical deterministic multiprocessor replay. In Int. Conference on Architectural Support for Programming Languages and Operating Systems, 2009.
[25]
S. Narayanasamy et al. BugNet: Continuously Recording Program Execution for Deterministic Replay Debugging. In Int. Symposium on Computer Architecture, 2005.
[26]
S. Narayanasamy et al. Recording shared memory dependencies using strata. In Int. Conference on Architectural Support for Programming Languages and Operating Systems, 2006.
[27]
D. Z. Pan and M. A. Linton. Supporting reverse execution for parallel programs. In Workshop on Parallel and Distributed Debugging, 1988.
[28]
S. Park et al. PRES: Probabilistic replay with execution sketching on multiprocessors. In Symposium on Operating Systems Principles, 2009.
[29]
H. Patil et al. PinPlay: A framework for deterministic replay and reproducible analysis of parallel programs. In Int. Symposium on Code Generation and Optimization, 2010.
[30]
G. Pokam et al. Architecting a chunk-based memory race recorder in modern CMPs. In Int. Symposium on Microarchitecture, 2009.
[31]
G. Pokam et al. CoreRacer: A practical memory race recorder for multicore x86 TSO processors. In Int. Symposium on Microarchitecture, 2011.
[32]
M. Russinovich and B. Cogswell. Replay for concurrent non-deterministic shared-memory applications. In Programming Language Design and Implementation, 1996.
[33]
S. M. Srinivasan et al. Flashback: a lightweight extension for rollback and deterministic replay for software debugging. In USENIX Annual Technical Conference, 2004.
[34]
K. Veeraraghavan et al. DoublePlay: Parallelizing sequential logging and replay. In Int. Conference on Architectural Support for Programming Languages and Operating Systems, 2011.
[35]
G. Voskuilen et al. Timetraveler: Exploiting acyclic races for optimizing memory race recording. In Int. Symposium on Computer Architecture, 2010.
[36]
M. Xu et al. A "flight data recorder" for enabling full-system multiprocessor deterministic replay. In Int. Symposium on Computer Architecture, 2003.
[37]
M. Xu et al. A regulated transitive reduction (RTR) for longer memory race recording. In Int. Conference on Architectural Support for Programming Languages and Operating Systems, 2006.
[38]
M. Yuffe et al. A fully integrated multi-CPU, GPU and memory controller 32nm processor. In Int. Solid-State Circuits Conference, 2011.
Index Terms
- Cyrus: unintrusive application-level record-replay for replay parallelism
Recommendations
Cyrus: unintrusive application-level record-replay for replay parallelism
ASPLOS '13: Proceedings of the eighteenth international conference on Architectural support for programming languages and operating systemsArchitectures for deterministic record-replay (R&R) of multithreaded code are attractive for program debugging, intrusion analysis, and fault-tolerance uses. However, very few of the proposed designs have focused on maximizing replay speed -- a key ...
Cyrus: unintrusive application-level record-replay for replay parallelism
ASPLOS '13Architectures for deterministic record-replay (R&R) of multithreaded code are attractive for program debugging, intrusion analysis, and fault-tolerance uses. However, very few of the proposed designs have focused on maximizing replay speed -- a key ...
Transparent mutable replay for multicore debugging and patch validation
ASPLOS '13We present Dora, a mutable record-replay system which allows a recorded execution of an application to be replayed with a modified version of the application. This feature, not available in previous record-replay systems, enables powerful new ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
March 2013574 pages
Copyright © 2013 ACM.
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 16 March 2013
Published in SIGARCH Volume 41, Issue 1
Check for updates
Author Tags
Qualifiers
- Research-article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- View Citations36Total Citations
- 405Total Downloads
- Downloads (Last 12 months)7
- Downloads (Last 6 weeks)1
Reflects downloads up to 10 Dec 2024
Other Metrics
Citations
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in