Multithreaded programs are becoming increasingly critical driven by the rise of multicore hardware and the coming storm of cloud computing. Unfortunately, these programs remain difficult to write, test, and debug. A key reason for this difficulty is nondeterminism: different runs of a multithreaded program may show different behaviors depending on how the threads interleave. Nondeterminism complicates almost every development step of multithreaded programs. For instance, it weakens testing because the schedules tested may not be the ones run in the field; it complicates debugging because reproducing a buggy schedule is hard.
In the past three decades, researchers have developed many techniques to address nondeterminism. Despite these efforts, it remains an open challenge to achieve both efficiency and determinism for general multithreaded programs on commodity multiprocessors.
This project aims to address this fundamental challenge. Its key insight is that one can reuse a small number of schedules to process a large number of inputs. Based on this insight, it takes an approach called schedule memoization that memoizes past schedules and, when possible, reuses them for future runs. This approach amortizes the high overhead of making one schedule deterministic over many reuses and makes a program repeat familiar behaviors whenever possible. A real-world analogy to this approach is animals' natural tendencies to follow familiar routes to avoid hazards and discovery overhead of unknown routes.
The greatest impact of this project will be a novel approach and new, effective systems and technologies to improving software reliability, thus benefiting every business, government, and individual.
