More Web Proxy on the site http://driver.im/

research-article

DomLock: a new multi-granularity locking technique for hierarchies

Authors:

Saurabh Kalikar,

Rupesh NasreAuthors Info & Claims

PPoPP '16: Proceedings of the 21st ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming

Article No.: 23, Pages 1 - 12

https://doi.org/10.1145/2851141.2851164

Published: 27 February 2016 Publication History

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 hierarchical data structures. Using STMBench7, we illustrate considerable reduction in the locking cost, resulting in an average throughput improvement of 42%.

References

[1]

M. J. Carey. Granularity hierarchies in concurrency control. In Proceedings of the 2Nd ACM SIGACT-SIGMOD Symposium on Principles of Database Systems, PODS '83, pages 156--165, New York, NY, USA, 1983. ACM. ISBN 0-89791-097-4. URL http://doi.acm.org/10.1145/588058.588079.

Digital Library

[2]

M. J. Carey, D. J. DeWitt, and J. F. Naughton. The OO7 Benchmark. In Proceedings of the 1993 ACM SIGMOD International Conference on Management of Data, SIGMOD '93, pages 12--21, New York, NY, USA, 1993. ACM. ISBN 0-89791-592-5. URL http://doi.acm.org/10.1145/170035.170041.

Digital Library

[3]

B. Chatterjee, N. Nguyen, and P. Tsigas. Efficient Lock-free Binary Search Trees. In Proceedings of the 2014 ACM Symposium on Principles of Distributed Computing, PODC '14, pages 322--331, New York, NY, USA, 2014. ACM. ISBN 978-1-4503-2944-6. 2611500. URL http://doi.acm.org/10.1145/2611462.2611500.

Digital Library

[4]

V. K. Chaudhri and V. Hadzilacos. Safe locking policies for dynamic databases. In Proceedings of the Fourteenth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, PODS '95, pages 233--244, New York, NY, USA, 1995. ACM. ISBN 0-89791-730-8. URL http://doi.acm.org/10.1145/212433.212464.

Digital Library

[5]

S. Cherem, T. Chilimbi, and S. Gulwani. Inferring locks for atomic sections. In Proceedings of the 2008 ACM SIGPLAN Conference on Programming Language Design and Implementation, PLDI '08, pages 304--315, New York, NY, USA, 2008. ACM. ISBN 978-1-59593-860-2. URL http://doi.acm.org/10.1145/1375581.1375619.

Digital Library

[6]

P. J. Courtois, F. Heymans, and D. L. Parnas. Concurrent Control with "Readers" and "Writers". Commun. ACM, 14(10):667--668, Oct. 1971. ISSN 0001-0782. URL http://doi.acm.org/10.1145/362759.362813.

Digital Library

[7]

K. P. Eswaran, J. N. Gray, R. A. Lorie, and I. L. Traiger. The notions of consistency and predicate locks in a database system. Commun. ACM, 19(11):624--633, Nov. 1976. ISSN 0001-0782. 360369. URL http://doi.acm.org/10.1145/360363.360369.

Digital Library

[8]

G. Golan-Gueta, N. Bronson, A. Aiken, G. Ramalingam, M. Sagiv, and E. Yahav. Automatic Fine-grain Locking Using Shape Properties. In Proceedings of the 2011 ACM International Conference on Object Oriented Programming Systems Languages and Applications, OOPSLA '11, pages 225--242, New York, NY, USA, 2011. ACM. ISBN 978-1-4503-0940-0. URL http://doi.acm.org/10.1145/2048066.2048086.

Digital Library

[9]

J. N. Gray, R. A. Lorie, and G. R. Putzolu. Granularity of locks in a shared data base. In Proceedings of the 1st International Conference on Very Large Data Bases, VLDB '75, pages 428--451, New York, NY, USA, 1975. ACM. ISBN 978-1-4503-3920-9. URL http://doi.acm.org/10.1145/1282480.1282513.

Digital Library

[10]

J. N. Gray, R. A. Lorie, G. R. Putzolu, and I. L. Traiger. Granularity of Locks and Degrees of Consistency in a Shared Data Base. In M. Stonebraker, editor, Readings in Database Systems, pages 94--121. Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 1988. ISBN 0-934613-65-6. URL http://dl.acm.org/citation.cfm?id=48751.48758.

Digital Library

[11]

R. Guerraoui, M. Kapalka, and J. Vitek. STMBench7: A Benchmark for Software Transactional Memory. In Proceedings of the 2Nd ACM SIGOPS/EuroSys European Conference on Computer Systems 2007, EuroSys '07, pages 315--324, New York, NY, USA, 2007. ACM. ISBN 978-1-59593-636-3. URL http://doi.acm.org/10.1145/1272996.1273029.

Digital Library

[12]

P. Hawkins, A. Aiken, K. Fisher, M. Rinard, and M. Sagiv. Reasoning about lock placements. In Proceedings of the 21st European Conference on Programming Languages and Systems, ESOP'12, pages 336--356, Berlin, Heidelberg, 2012. Springer-Verlag. ISBN 978-3-642-28868-5. 17. URL http://dx.doi.org/10.1007/978-3-642-28869-2_17.

Digital Library

[13]

M. Herlihy and N. Shavit. The Art of Multiprocessor Programming. Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 2008. ISBN 0123705916, 9780123705914.

Digital Library

[14]

C. Lameter. Effective Synchronization on Linux/NUMA Systems, 2005. URL https://www.kernel.org/pub/linux/kernel/people/christoph/gelato/gelato2005-paper.pdf.

[15]

P. Liu and C. Zhang. Unleashing Concurrency for Irregular Data Structures. In Proceedings of the 36th International Conference on Software Engineering, ICSE 2014, pages 480--490, New York, NY, USA, 2014. ACM. ISBN 978-1-4503-2756-5. URL http://doi.acm.org/10.1145/2568225.2568277.

Digital Library

[16]

X. Liu and J. Mellor-Crummey. A Data-centric Profiler for Parallel Programs. In Proceedings of the International Conference on High Performance Computing, Networking, Storage and Analysis, SC '13, pages 28:1--28:12, New York, NY, USA, 2013. ACM. ISBN 978-1-4503-2378-9. URL http://doi.acm.org/10.1145/2503210.2503297.

Digital Library

[17]

D. Lomet and M. F. Mokbel. Locking key ranges with unbundled transaction services. Proc. VLDB Endow., 2(1):265--276, Aug. 2009. ISSN 2150-8097. URL http://dx.doi.org/10.14778/1687627.1687658.

Digital Library

[18]

D. B. Lomet. Key range locking strategies for improved concurrency. In Proceedings of the 19th International Conference on Very Large Data Bases, VLDB '93, pages 655--664, San Francisco, CA, USA, 1993. Morgan Kaufmann Publishers Inc. ISBN 1-55860-152-X. URL http://dl.acm.org/citation.cfm?id=645919.672802.

Digital Library

[19]

J. M. Mellor-Crummey and M. L. Scott. Scalable Reader-writer Synchronization for Shared-memory Multiprocessors. In Proceedings of the Third ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, PPOPP '91, pages 106--113, New York, NY, USA, 1991. ACM. ISBN 0-89791-390-6. URL http://doi.acm.org/10.1145/109625.109637.

Digital Library

[20]

MSDN. Sql server 2016 database engine, 2015. URL https://msdn.microsoft.com/en-us/library/ms187875.aspx.

[21]

A. Natarajan, L. Savoie, and N. Mittal. Concurrent Wait-Free Red Black Trees. In T. Higashino, Y. Katayama, T. Masuzawa, M. Potop-Butucaru, and M. Yamashita, editors, Stabilization, Safety, and Security of Distributed Systems, volume 8255 of Lecture Notes in Computer Science, pages 45--60. Springer International Publishing, 2013. ISBN 978-3-319-03088-3. 4. URL http://dx.doi.org/10.1007/978-3-319-03089-0_4.

Digital Library

[22]

Oracle. Oracle database 10g r2, 2015. URL http://docs.oracle.com/cd/B19306_01/index.htm.

[23]

H. Sundell and P. Tsigas. Fast and lock-free concurrent priority queues for multi-thread systems. In Parallel and Distributed Processing Symposium, 2003. Proceedings. International, pages 11 pp.-, April 2003.

Digital Library

[24]

H. Sundell and P. Tsigas. Fast and Lock-free Concurrent Priority Queues for Multi-thread Systems. J. Parallel Distrib. Comput., 65(5):609--627, May 2005. ISSN 0743-7315. URL http://dx.doi.org/10.1016/j.jpdc.2004.12.005.

Digital Library

[25]

Sybase. Adaptive server enterprise: Performance tuning and locking, 2003. URL http://infocenter.sybase.com/help/topic/com.sybase.help.ase_12.5.1/title.htm.

Cited By

Hu JCurtis-Maury MDevadas V(2023)Dynamic Data Partitioning in the WAFL File System2023 IEEE High Performance Extreme Computing Conference (HPEC)10.1109/HPEC58863.2023.10363474(1-7)Online publication date: 25-Sep-2023
https://doi.org/10.1109/HPEC58863.2023.10363474
Bang JKim CKim SChen QLee CByun ELee JEom H(2021)Finer-LRU: A Scalable Page Management Scheme for HPC Manycore Architectures2021 IEEE International Parallel and Distributed Processing Symposium (IPDPS)10.1109/IPDPS49936.2021.00065(567-576)Online publication date: May-2021
https://doi.org/10.1109/IPDPS49936.2021.00065
Devadas VCurtis-Maury M(2020)Scalable Coordination of Hierarchical ParallelismProceedings of the 49th International Conference on Parallel Processing10.1145/3404397.3404398(1-11)Online publication date: 17-Aug-2020
https://dl.acm.org/doi/10.1145/3404397.3404398
Show More Cited By

Index Terms

DomLock: a new multi-granularity locking technique for hierarchies
1. Computing methodologies
  1. Parallel computing methodologies
    1. Parallel programming languages
2. Software and its engineering
  1. Software notations and tools
    1. General programming languages
      1. Language types
        Parallel programming languages

Recommendations

DomLock: a new multi-granularity locking technique for hierarchies
PPoPP '16

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 ...
DomLock: A New Multi-Granularity Locking Technique for Hierarchies
Special Issue: Invited papers from PPoPP 2016, Part 2

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 ...
NumLock: Towards Optimal Multi-Granularity Locking in Hierarchies
ICPP '18: Proceedings of the 47th International Conference on Parallel Processing

We study multi-granularity locking in hierarchies. Existing popular mechanisms for multi-granularity locking work on two extremes: fine-grained locking which maximizes concurrency, and coarsegrained locking which minimizes the locking cost. Between the ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

PPoPP '16: Proceedings of the 21st ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming

February 2016

420 pages

ISBN:9781450340922

DOI:10.1145/2851141

General Chair:
Rafael Asenjo
University of Málaga, Spain
,
Program Chair:
Tim Harris
Oracle Labs, Cambridge, UK

ACM SIGPLAN Notices Volume 51, Issue 8
PPoPP '16
August 2016
405 pages
ISSN:0362-1340
EISSN:1558-1160
DOI:10.1145/3016078
Editor:
Matthew Fluet
Issue’s Table of Contents

Copyright © 2016 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 27 February 2016

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Badges

Distinguished Paper

Author Tags

Qualifiers

Research-article

Funding Sources

IIT Madras

Conference

PPoPP '16

Sponsor:

PPoPP '16: 21st ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming

March 12 - 16, 2016

Barcelona, Spain

Acceptance Rates

Overall Acceptance Rate 230 of 1,014 submissions, 23%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

15
Total Citations
View Citations
750
Total Downloads

Downloads (Last 12 months)32
Downloads (Last 6 weeks)3

Reflects downloads up to 24 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Hu JCurtis-Maury MDevadas V(2023)Dynamic Data Partitioning in the WAFL File System2023 IEEE High Performance Extreme Computing Conference (HPEC)10.1109/HPEC58863.2023.10363474(1-7)Online publication date: 25-Sep-2023
https://doi.org/10.1109/HPEC58863.2023.10363474
Bang JKim CKim SChen QLee CByun ELee JEom H(2021)Finer-LRU: A Scalable Page Management Scheme for HPC Manycore Architectures2021 IEEE International Parallel and Distributed Processing Symposium (IPDPS)10.1109/IPDPS49936.2021.00065(567-576)Online publication date: May-2021
https://doi.org/10.1109/IPDPS49936.2021.00065
Devadas VCurtis-Maury M(2020)Scalable Coordination of Hierarchical ParallelismProceedings of the 49th International Conference on Parallel Processing10.1145/3404397.3404398(1-11)Online publication date: 17-Aug-2020
https://dl.acm.org/doi/10.1145/3404397.3404398
Amer ALu HBalaji PChabbi MWei YHammond JMatsuoka S(2019)Lock Contention Management in Multithreaded MPIACM Transactions on Parallel Computing (TOPC)10.1145/32754435:3(1-21)Online publication date: 8-Jan-2019
https://dl.acm.org/doi/10.1145/3275443
Kalikar SNasre R(2019)Toggle: Contention-Aware Task Scheduler for Concurrent Hierarchical OperationsEuro-Par 2019: Parallel Processing10.1007/978-3-030-29400-7_11(142-155)Online publication date: 13-Aug-2019
https://doi.org/10.1007/978-3-030-29400-7_11
Kalikar SNasre R(2018)NumLockProceedings of the 47th International Conference on Parallel Processing10.1145/3225058.3225141(1-10)Online publication date: 13-Aug-2018
https://dl.acm.org/doi/10.1145/3225058.3225141
Wang XLiu WXue WWu L(2018)swSpTRSVACM SIGPLAN Notices10.1145/3200691.317851353:1(338-353)Online publication date: 10-Feb-2018
https://dl.acm.org/doi/10.1145/3200691.3178513
Drachsler-Cohen DVechev MYahav E(2018)Practical concurrent traversals in search treesACM SIGPLAN Notices10.1145/3200691.317850353:1(207-218)Online publication date: 10-Feb-2018
https://dl.acm.org/doi/10.1145/3200691.3178503
Wang XLiu WXue WWu LKrall AGross T(2018)swSpTRSVProceedings of the 23rd ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming10.1145/3178487.3178513(338-353)Online publication date: 10-Feb-2018
https://dl.acm.org/doi/10.1145/3178487.3178513
Drachsler-Cohen DVechev MYahav EKrall AGross T(2018)Practical concurrent traversals in search treesProceedings of the 23rd ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming10.1145/3178487.3178503(207-218)Online publication date: 10-Feb-2018
https://dl.acm.org/doi/10.1145/3178487.3178503
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents