Chimera: Hybrid Program Analysis for Determinism

Abstract

Chimera uses a new hybrid program analysis to provide deterministic replay for commodity multiprocessor systems. Chimera leverages the insight that it is easy to provide deterministic multiprocessor replay for data-race-free programs (one can just record nondeterministic inputs and the order of synchronization operations), so if we can somehow transform an arbitrary program to be datarace-free, then we can provide deterministic replay cheaply for that program. To perform this transformation, Chimera uses a sound static data-race detector to find all potential data-races. It then instruments pairs of potentially racing instructions with a weak-lock, which provides suf cient guarantees to allow deterministic replay but does not guarantee mutual exclusion. Unsurprisingly, a large fraction of data-races found by the static tool are false data-races, and instrumenting them each of them with a weak-lock results in prohibitively high overhead. Chimera drastically reduces this cost from 53x to 1.39x by increasing the granularity of weak-locks without signi cantly compromising on parallelism. This is achieved by employing a combination of profi ling and symbolic analysis techniques that target the sources of imprecision in the static data-race detector.We fi nd that performance overhead for deterministic recording is 2.4% on average for Apache and desktop applications and about 86% for scienti c applications.

Short bio

Dongyoon Lee is a PhD candidate in Computer Science and Engineering (CSE) at the University of Michigan, Ann Arbor, MI. He received the B.S. degree in Electrical Engineering from Seoul National University, Seoul, Korea, in 2004 and the M.S degree in CSE from University of Michigan, in 2009. He is interested in improving the programmability of parallel computer systems and his research has produced ultra-low overhead software and hardware deterministic replay systems by leveraging complementary strengths of static program analysis, the operating system, and computer architecture. He works with Prof. Satish Narayanasamy as a member of the Advanced Computer Architecture Laboratory (ACAL) and Software Systems Laboratory (SSL) research groups.