Encapsulated Open Nesting for STM: Fine-Grained Higher-Level Conflict Detection
Open nesting allows replacing the automatic detection of conflicting memory accesses used in transactional memory (TM) with programmer-specified higher-level conflict detection. Higher-level conflict detection allows removing conflicts of commuting operations where the automatic conflict detection is too conservative. Different conflict detection schemes are incompatible with each other and thus must operate on separate memory locations to prevent inconsistencies. Using open nesting, a programmer implements this separation manually using source code modifications possibly assisted by static checks.
Encapsulated open nesting extends open nesting by automatically preventing concurrent accesses to the same memory location using different conflict detection schemes unless all accesses are reads. This approach uses an additional synchronization layer with the same granularity as the existing synchronization of TM. This automatism reduces programming effort by allowing fine-grained use of open nesting and extends the scope of open nesting to abstractions with unknown implementation.
We extend the TLRW algorithm to support encapsulated open nesting. An evaluation using an implementation of this algorithm within the Deuce framework shows an average overhead of 21.7% for encapsulated open nesting (compared to regular open nesting) for nine benchmarks while simplifying programming.
Conference DayWed 20 FebDisplayed time zone: Guadalajara, Mexico City, Monterrey change
09:35 - 10:50
|Encapsulated Open Nesting for STM: Fine-Grained Higher-Level Conflict Detection|
|A Specialized B-Tree for Concurrent Datalog Evaluation|
Herbert JordanUniversity of Innsbruck, Pavle SuboticUniversity College London, David ZhaoThe University of Sydney, Bernhard ScholzUniversity of Sydney, AustraliaDOI
|Efficient Race Detection with Futures|
Robert UtterbackMonmouth College, Kunal AgrawalWashington University in St. Louis, Jeremy Fineman, I-Ting Angelina LeeWashington University in St. LouisDOI