Drinking from Both Glasses: Adaptively Combining Pessimistic and Optimistic Synchronization for Efficient Parallel Runtime Support

It is notoriously challenging to achieve parallel software systems that are both scalable and reliable. Parallel runtime support—such as multithreaded record & replay, data race and atomicity violation detectors, transactional memory, and support for stronger memory models—helps achieve these goals, but existing commodity solu-tions slow programs substantially in order to capture (track or con-trol) the program’s cross-thread dependences accurately. Captur-ing cross-thread dependences using “pessimistic ” synchronization slows every program access, while “optimistic ” synchronization al-lows for lightweight instrumentation of most accesses but dramati-cally slows accesses involved in cross-thread dependences. This paper introduces (1) a hybrid of pessimistic and opti-mistic synchronization and (2) an adaptive policy that enables fine-grained switching between pessimistic and optimistic synchroniza-tion based on program behavior. The adaptive policy uses online profiling and a cost–benefit model to inform its decisions. We de-sign a dependence recorder on top of our approach to demonstrate its feasibility as a framework for efficient parallel runtime support. We have implemented our approach in a high-performance Java virtual machine and show that it outperforms parallel runtime sup-port based solely on pessimistic or optimistic synchronization. These results show the potential for adaptive, hybrid synchroniza-tion for efficient parallel runtime support in commodity systems. 1