NDLI: Timetraveler:exploiting acyclic races for optimizing memory race recording

Content Provider	ACM Digital Library
Author	Vijaykumar, T. N. Ahmad, Faraz Voskuilen, Gwendolyn
Abstract	As chip multiprocessors emerge as the prevalent microprocessor architecture, support for debugging shared-memory parallel programs becomes important. A key difficulty is the programs' nondeterministic semantics due to which replay runs of a buggy program may not reproduce the bug. The non-determinism stems from memory races where accesses from two threads, at least one of which is a write, go to the same memory location. Previous hardware schemes for memory race recording log the predecessor-successor thread ordering at memory races and enforce the same orderings in the replay run to achieve deterministic replay. To reduce the log size, the schemes exploit transitivity in the orderings to avoid recording redundant orderings. To reduce the log size further while requiring minimal hardware, we propose Timetraveler which for the first time exploits acyclicity of races based on the key observation that an acyclic race need not be recorded even if the race is not covered already by transitivity. Timetraveler employs a novel and elegant mechanism called post-dating which both ensures that acyclic races, including those through the L2, are eventually ordered correctly, and identifies cyclic races. To address false cycles through the L2, Timetraveler employs another novel mechanism called time-delay buffer which delays the advancement of the L2 banks' timestamps and thereby reduces the false cycles. Using simulations, we show that Timetraveler reduces the log size for commercial workloads by 88% over the best previous approach while using only a 696-byte time-delay buffer.
Starting Page	198
Ending Page	209
Page Count	12
File Format	PDF
ISSN	01635964
DOI	10.1145/1816038.1815986
Journal	ACM SIGARCH Computer Architecture News (CARN)
Volume Number	38
Issue Number	3
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	1981-04-01
Publisher Place	New York
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Determinism Race recording Replay Debugging
Content Type	Text
Resource Type	Article

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Timetraveler: exploiting acyclic races for optimizing memory race recording

Rerun:Exploiting Episodes for Lightweight Memory Race Recording

A Hardware Memory Race Recorder for Deterministic Replay

A regulated transitive reduction (RTR) for longer memory race recording (CARN, Vol. 34, Issue. 5)

BugNet:Continuously Recording Program Execution for Deterministic Replay Debugging

RelaxReplay:record and replay for relaxed-consistency multiprocessors (CARN, Vol. 42, Issue. 1)

Recording shared memory dependencies using strata (CARN, Vol. 34, Issue. 5)

A regulated transitive reduction (RTR) for longer memory race recording (SIGP, Vol. 41, Issue. 11)

Light: replay via tightly bounded recording

Timetraveler:exploiting acyclic races for optimizing memory race recording

Similar Documents

Timetraveler: exploiting acyclic races for optimizing memory race recording

Rerun:Exploiting Episodes for Lightweight Memory Race Recording

A Hardware Memory Race Recorder for Deterministic Replay

A regulated transitive reduction (RTR) for longer memory race recording (CARN, Vol. 34, Issue. 5)

BugNet:Continuously Recording Program Execution for Deterministic Replay Debugging

RelaxReplay:record and replay for relaxed-consistency multiprocessors (CARN, Vol. 42, Issue. 1)

Recording shared memory dependencies using strata (CARN, Vol. 34, Issue. 5)

A regulated transitive reduction (RTR) for longer memory race recording (SIGP, Vol. 41, Issue. 11)

Light: replay via tightly bounded recording

Timetraveler:exploiting acyclic races for optimizing memory race recording