Kendo swMATH ID: 24074 Software Authors: Olszewski, M.; Ansel, J.; Amarasinghe, S. Description: 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 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 Homepage: https://dl.acm.org/citation.cfm?doid=1508284.1508256 Source Code: https://github.com/greeshmaswaminathan/Kendo-On-RoadRunner Related Software: CapoOne; MIPLIB2003; CHiPPS; ParaSCIP; MIPLIB; SCIP; GAMS; ParaLEX; CPLEX; PICO; FATCOP; UG; PARSEC; SPLASH-2; LLVM; StreamIt; Grace; PEBBL; SCIP-Jack; ParSSSE Cited in: 4 Publications all top 5 Cited by 11 Authors 2 Heinz, Stefan 2 Shinano, Yuji 1 Berthold, Timo 1 Farmer, James Doyne 1 Koch, Thorsten 1 Lu, Li 1 Perregaard, Michael 1 Ralphs, Ted K. 1 Scott, Michael L. 1 Vigerske, Stefan 1 Winkler, Michael Cited in 3 Serials 1 INFORMS Journal on Computing 1 Optimization Methods & Software 1 Mathematical Methods of Operations Research Cited in 2 Fields 3 Operations research, mathematical programming (90-XX) 2 Computer science (68-XX) Citations by Year