Kendo: Efficient Deterministic Multithreading in Software

Although chip-multiprocessors have become the industry standard, developing parallel applications that target them remains a daunting task. Non-determinism, inherent in threaded applications, causes significant challenges for par-allel programmers by hindering their ability to create parallel applications with repeatable results. As a consequence, par-allel applications are significantly harder to debug, test, and maintain than sequential programs. This paper introduces Kendo: a new software-only sys-tem that provides deterministic multithreading of parallel applications. Kendo enforces a deterministic interleaving of lock acquisitions and specially declared non-protected reads through a novel dynamically load-balanced deterministic scheduling algorithm. The algorithm tracks the progress of each thread using performance counters to construct a deterministic logical time that is used to compute an inter-leaving of shared data accesses that is both deterministic and provides good load balancing. Kendo can run on to-day’s commodity hardware while incurring only a modest performance cost. Experimental results on the SPLASH-2 applications yield a geometric mean overhead of only 16% when running on 4 processors. This low overhead makes it possible to benefit from Kendo even after an application is deployed. Programmers can start using Kendo today to pro-gram parallel applications that are easier to develop, debug, and test