PPoPP 2016
Sat 12 - Wed 16 March 2016 Barcelona, Spain
Tue 15 Mar 2016 15:10 - 15:35 at Mallorca+Menorca - Locking Chair(s): Michael Scott

We present efficient locking mechanisms for hierarchical data structures. Several applications work on an abstract hierarchy of objects, and a parallel execution on this hierarchy necessitates synchronization across workers operating on different parts of the hierarchy. Existing synchronization mechanisms are either too coarse, too inefficient, or too ad hoc, resulting in reduced or unpredictable amount of concurrency. We propose a new locking approach based on the structural properties of the underlying hierarchy. We show that the developed techniques are efficient even when the hierarchy is an arbitrary graph, and are applicable even when the hierarchy involves mutation. Theoretically, we present our approach as a locking-cost-minimizing instance of a generic algebraic model of synchronization for hierarchical data structures. Using STMBench7, we illustrate considerable reduction in the locking cost, resulting in an average throughput improvement of 42%.

Tue 15 Mar
Times are displayed in time zone: Greenwich Mean Time : Belfast change

14:20 - 15:35: LockingMain conference at Mallorca+Menorca
Chair(s): Michael ScottUniversity of Rochester
14:20 - 14:45
Talk
Be My Guest - MCS Lock Now Welcomes Guests Artifact Evaluation
Main conference
Tianzheng WangUniversity of Toronto, Milind ChabbiRice University, Hideaki KimuraHP Labs
Link to publication DOI
14:45 - 15:10
Talk
Contention-Conscious, Locality-Preserving Locks
Main conference
Milind ChabbiRice University, John Mellor-CrummeyRice University
Link to publication DOI
15:10 - 15:35
Talk
DomLock: A New Multi-Granularity Locking Technique for HierarchiesDistinguished Paper AwardArtifact Evaluation
Main conference
Saurabh Kalikar, Rupesh NasreIIT Madras, India
Link to publication DOI