Optimizing GenMC's consistency checker
Making the generated consistency checker at the core of the GenMC stateless model checker faster.
A project at the Department of Computer Science, ETH Zurich, again advised by Prof. Dr. Michalis Kokologiannakis, following on from my Bachelor’s thesis.
GenMC is a stateless model checker for concurrent programs that is parametric in the weak memory model it assumes. Every time it extends an execution graph with a new event, it has to check that the graph is still consistent under the chosen memory model, so the performance of that check has a large effect on the performance of the tool as a whole. The consistency checker is not written by hand: Kater takes a memory-model specification and generates the C++ code that GenMC then uses to decide consistency at runtime. The goal of this work is to improve the performance of that generated code.
My contributions target both the acyclicity checks and the inclusion (view) checks that the generated consistency checker is built from. On the acyclicity side this includes reworking how the graph traversal is carried out so that it also handles cases that previously pushed the consistency checker past its limits and caused overflows, reducing the bookkeeping the traversal has to redo on every check, and recognising when an expensive check can be replaced by a much cheaper argument based on simple counting of events. On the inclusion side it includes better handling of recursively defined relations and automatic sound transformations to reduce the required computation. These changes have translated into a noticeable speed-up for GenMC.
A full paper with the details of each optimization and the accompanying evaluation is submitted. I will expand this page with more specifics once it is published.