TY - GEN
T1 - InstantCheck
T2 - 43rd Annual IEEE/ACM International Symposium on Microarchitecture, MICRO 2010
AU - Nistor, Adrian
AU - Marinov, Darko
AU - Torrellas, Josep
N1 - Copyright:
Copyright 2011 Elsevier B.V., All rights reserved.
PY - 2010
Y1 - 2010
N2 - Developing multithreaded programs in shared-memory systems is difficult. One key reason is the nondeterminism of thread interaction, which may result in one code input producing different outputs in different runs. Unfortunately, enforcing determinism by construction typically comes at a performance, hardware, or programmability cost. An alternative is to check during testing whether code is deterministic. This paper presents InstantCheck, a novel technique that checks determinism with a very small runtime overhead while requiring only a minor hardware extension. During code testing, Instant-Check can check whether the code under test ends up in a deterministic state in various runs. The idea is to compute a 64-bit hash of the memory state and compare the hashes of different test runs that have the same input. If two runs have different hashes, Instant-Check reports state nondeterminism. For efficient operation, InstantCheck uses on-the-fly incremental hashing in hardware. The hash is kept in a per-core 64-bit register, which trivially supports virtualization, migration, and context switching. We use InstantCheck to understand the determinism properties of 17 popular applications, including Sphinx3, PBZip2, PARSEC, and SPLASH-2. InstantCheck incurs a negligible average runtime overhead of 0.3% over native testing runs. We also show how using InstantCheck programmers can find bugs and discuss other applications of fast memory-state hashing. While using InstantCheck, we found a real bug in the widely used PARSEC benchmark.
AB - Developing multithreaded programs in shared-memory systems is difficult. One key reason is the nondeterminism of thread interaction, which may result in one code input producing different outputs in different runs. Unfortunately, enforcing determinism by construction typically comes at a performance, hardware, or programmability cost. An alternative is to check during testing whether code is deterministic. This paper presents InstantCheck, a novel technique that checks determinism with a very small runtime overhead while requiring only a minor hardware extension. During code testing, Instant-Check can check whether the code under test ends up in a deterministic state in various runs. The idea is to compute a 64-bit hash of the memory state and compare the hashes of different test runs that have the same input. If two runs have different hashes, Instant-Check reports state nondeterminism. For efficient operation, InstantCheck uses on-the-fly incremental hashing in hardware. The hash is kept in a per-core 64-bit register, which trivially supports virtualization, migration, and context switching. We use InstantCheck to understand the determinism properties of 17 popular applications, including Sphinx3, PBZip2, PARSEC, and SPLASH-2. InstantCheck incurs a negligible average runtime overhead of 0.3% over native testing runs. We also show how using InstantCheck programmers can find bugs and discuss other applications of fast memory-state hashing. While using InstantCheck, we found a real bug in the widely used PARSEC benchmark.
UR - http://www.scopus.com/inward/record.url?scp=79951699568&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=79951699568&partnerID=8YFLogxK
U2 - 10.1109/MICRO.2010.55
DO - 10.1109/MICRO.2010.55
M3 - Conference contribution
AN - SCOPUS:79951699568
SN - 9780769542997
T3 - Proceedings of the Annual International Symposium on Microarchitecture, MICRO
SP - 251
EP - 262
BT - Proceedings - 43rd Annual IEEE/ACM International Symposium on Microarchitecture, MICRO 2010
Y2 - 4 December 2010 through 8 December 2010
ER -