Drinking from Both Glasses: Combining Pessimistic and Optimistic Tracking of Cross-Thread Dependences
It is notoriously challenging to develop parallel software systems that are both scalable and correct. Runtime support for parallelism—such as multithreaded record & replay, data race detectors, transactional memory, and enforcement of stronger memory models—helps achieve these goals, but existing commodity solutions slow programs substantially in order to track (i.e., detect or control) an execution’s cross-thread dependences accurately. Prior work tracks cross-thread dependences either “pessimistically,” slowing every program access, or “optimistically,” allowing for lightweight instrumentation of most accesses but dramatically slowing accesses involved in cross-thread dependences.
This paper seeks to hybridize pessimistic and optimistic tracking, which is challenging because there exists a fundamental mismatch between pessimistic and optimistic tracking. We address this challenge based on insights about how dependence tracking and program synchronization interact, and introduce a novel approach called hybrid tracking. Hybrid tracking is suitable for building efficient runtime support, which we demonstrate by building hybrid-tracking-based versions of a dependence recorder and a region serializability enforcer. An adaptive, profile-based policy makes runtime decisions about switching between pessimistic and optimistic tracking. Our evaluation shows that hybrid tracking enables runtime support to overcome the performance limitations of both pessimistic and optimistic tracking alone.
Tue 15 Mar
11:35 - 12:50: Main conference - Optimistic concurrency at Mallorca+Menorca Chair(s): Milind ChabbiRice University | ||||||||||||||||||||||||||||||||||||||||||
11:35 - 12:00 Talk | Link to publication DOI | |||||||||||||||||||||||||||||||||||||||||
12:00 - 12:25 Talk | Link to publication DOI | |||||||||||||||||||||||||||||||||||||||||
12:25 - 12:50 Talk | Man CaoOhio State University, USA, Minjia ZhangOhio State University, USA, Aritra SenguptaOhio State University, Michael BondOhio State University Link to publication DOI |