Runtime validation of memory ordering using constraint graph checking

Kaiyu Chen, Sharad Malik, Priyadarsan Patra

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

31 Scopus citations

Abstract

An important correctness issue for emerging multi/many-core shared memory systems is to ensure that the inter-processor communication through shared memory conforms to the memory ordering rules, as specified by the architecture's memory consistency model [1]. This presents a significant validation challenge. Growing system complexity makes it increasingly hard to identify all deep-state logic bugs in pre-silicon verification. Further, aggressive technology scaling makes hardware more vulnerable to dynamic errors that can only be detected at runtime. In this paper, we propose an approach for runtime validation of memory ordering. This allows us to survive bugs that escape pre-silicon verification, as well as deal with emerging dynamic errors. Our solution consists of two parts: 1) at the microarchitecture level, we add efficient hardware support to capture the observed ordering among shared-memory operations; 2) we perform online verification of the observed memory ordering by checking for cycles in the constraint graph [11, 12]. We combine these to achieve end-to-end correctness validation of the system execution with respect to the memory ordering specification. There are several challenges that need to be addressed to make this approach practical. We describe these, as well as optimization techniques for reducing the hardware overhead. Estimates obtained from preliminary chip multiprocessor simulation experiments show that the proposed techniques are very effective in achieving acceptable hardware overhead and minimal performance impact.

Original languageEnglish (US)
Title of host publicationProceedings - International Symposium on High-Performance Computer Architecture
Pages415-426
Number of pages12
DOIs
StatePublished - 2008
Event2008 IEEE 14th International Symposium on High Performance Computer Architecture, HPCA 2008 - Salt Lake City, UT, United States
Duration: Feb 16 2008Feb 20 2008

Publication series

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

Other

Other2008 IEEE 14th International Symposium on High Performance Computer Architecture, HPCA 2008
Country/TerritoryUnited States
CitySalt Lake City, UT
Period2/16/082/20/08

All Science Journal Classification (ASJC) codes

  • Hardware and Architecture

Fingerprint

Dive into the research topics of 'Runtime validation of memory ordering using constraint graph checking'. Together they form a unique fingerprint.

Cite this