Mithridates: Peering into the Future with Idle Cores
Earl Barr, Mark Gabel, David Hamilton, and Zhendong Su
The presence of multicore machines, and the likely explosion in the number of cores in future CPUs brings with it the challenge and prospect of many idle cores: How can we utilize the additional, necessarily parallel cycles they provide? We propose Mithridates, a technique that uses idle cores to speed up programs that use dynamic checks to ensure a program’s execution does not violate certain program invariants. Our insight is to take a program with invariants and transform it into a worker, shorn of the program's invariant checking, and one or more scouts that do the minimum work necessary to perform those checks. Then we run the worker and scouts in parallel. Ideally, the scouts run far enough ahead to complete invariant checks before the worker queries them. In other words, the scouts peer into the set of future states of their progenitor, and act as “short-sighted oracles.”
We have evaluated Mithridates on an ordered list, as a motivating example, and on Lucene, a widely used document indexer from the Apache project. We systematically transformed these examples to extract the worker and the scouts. In both examples, we successfully utilized idle cores to reclaim much of the performance lost to invariant checking. With seven scouts, the Mithridates version of Lucene reduces the time spent checking the invariant by 92%. We believe Mithridates will bring invariants that are normally discarded after development into reach for production use.