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: (GMT+01:00) Greenwich Mean Time : Belfast change

14:20 - 15:35: Main conference - Locking at Mallorca+Menorca
Chair(s): Michael ScottUniversity of Rochester
PPoPP-2016-papers14:20 - 14:45
Tianzheng WangUniversity of Toronto, Milind ChabbiRice University, Hideaki KimuraHP Labs
Link to publication DOI
PPoPP-2016-papers14:45 - 15:10
Milind ChabbiRice University, John Mellor-CrummeyRice University
Link to publication DOI
PPoPP-2016-papers15:10 - 15:35
Saurabh Kalikar, Rupesh NasreIIT Madras, India
Link to publication DOI