BulkCompactor: Optimized deterministic execution via conflict-aware commit of atomic blocks

Yuelu Duan, Xing Zhou, Wonsun Ahn, Josep Torrellas

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

Recent proposals for determinism-enforcement architectures are able to honor the dependences between threads through a commit step that often becomes a performance bottleneck. As they commit code blocks (or chunks) in a round-robin order, if one chunk gets squashed due to a conflict, its successors also observe a stall. We call this effect transitive squash delay. This paper proposes a novel, high-performance approach to deterministic execution based on Conflict-Aware commit. Rather than committing chunks in strict round-robin order, the idea is to skip those chunks with conflicts and deterministically execute them slightly later. The scheme, called BulkCompactor, largely eliminates transitive squash delay, "compacts" the chunk commits, and substantially speeds-up execution. With BulkCompactor, the squash overhead is O(N) rather than O(N 2) as in round-robin. We describe BulkCompactor designs for machines with centralized or distributed commit. Finally, a simulation-based evaluation shows that BulkCompactor delivers performance comparable to nondeter-ministic systems. For example, for 32 processors, BulkCompactor incurs an average execution overhead of 22% over a nondetermin-istic system. The round-robin scheme's average overhead is 133%.

Original languageEnglish (US)
Title of host publicationProceedings - 18th IEEE International Symposium on High Performance Computer Architecture, HPCA - 18 2012
Pages361-372
Number of pages12
DOIs
StatePublished - 2012
Event18th IEEE International Symposium on High Performance Computer Architecture, HPCA - 18 2012 - New Orleans, LA, United States
Duration: Feb 25 2012Feb 29 2012

Publication series

NameProceedings - International Symposium on High-Performance Computer Architecture
ISSN (Print)1530-0897

Other

Other18th IEEE International Symposium on High Performance Computer Architecture, HPCA - 18 2012
Country/TerritoryUnited States
CityNew Orleans, LA
Period2/25/122/29/12

ASJC Scopus subject areas

  • Hardware and Architecture

Fingerprint

Dive into the research topics of 'BulkCompactor: Optimized deterministic execution via conflict-aware commit of atomic blocks'. Together they form a unique fingerprint.

Cite this