Kendo: efficient deterministic multithreading in software
By Marek Olszewski, Jason Ansel, Saman P. Amarasinghe. International Conference on Architectural Support for Programming Languages and Operating Systems, 2009
410 citations recorded by the source corpus.
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 parallel programmers by hindering their ability to create parallel applications with repeatable results. As a consequence, parallel applications are significantly harder to debug, test, and maintain than sequential programs. This paper introduces Kendo: a new software-only system 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 interleaving of shared data accesses that is both deterministic and provides good load balancing. Kendo can run on today'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 program parallel applications that are easier to develop, debug, and test.
Subfields: Computer Networks and Communications, Hardware and Architecture
View Paper: https://www.semanticscholar.org/paper/8a0af8ae748210ef571d074362b552af571e6d33
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Computer Networks and Communications
In Hardware and Architecture
Citations in the corpus
- SherLog: error diagnosis by connecting clues from run-time logs (2010, methodology): “Much effort has been conducted in system and hardware support for reproducing software failures on uni-processor and multi-processors, including TTVM [30], R2 [24], DMP [17], Kendo [ 38 ], FDR [46], BugNet [36], VMWare [43] , just to name a few.”