|Title||:||DomLock: A New Multi-Granularity Locking Technique for Hierarchies|
|Speaker||:||Saurabh Mohanrao Kalikar (IITM)|
|Details||:||Mon, 24 Apr, 2017 10:00 AM @ BSB 361|
|Abstract:||:||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 hierarchies. Using STMBench7, we illustrate considerable reduction in the locking cost, resulting in a better average throughput.
This work is published in Principles and Practice of Parallel Programming (PPoPP) 2016.
The code is publicly available at the PACE Lab website.