research-article

Scalable adaptive NUMA-aware lock: combining local locking and remote locking for efficient concurrency

Authors:

Haibo ChenAuthors Info & Claims

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

Article No.: 50, Pages 1 - 2

https://doi.org/10.1145/2851141.2851176

Published: 27 February 2016 Publication History

Get Access

Abstract

Scalable locking is a key building block for scalable multi-threaded software. Its performance is especially critical in multi-socket, multi-core machines with non-uniform memory access (NUMA). Previous schemes such as local locking and remote locking only perform well under a certain level of contention, and often require non-trivial tuning for a particular configuration. Besides, for large NUMA systems, because of unmanaged lock server's nomination, current distance-first NUMA policies cannot perform satisfactorily.

In this work, we propose SANL, a locking scheme that can deliver high performance under various contention levels by adaptively switching between the local and the remote lock scheme. Furthermore, we introduce a new NUMA policy for the remote lock that jointly considers node distances and server utilization when choosing lock servers. A comparison with seven representative locking schemes shows that SANL outperforms the others in most contention situations. In one group test, SANL is 3.7 times faster than RCL lock and 17 times faster than POSIX mutex.

References

[1]

S. Boyd-Wickizer, M. F. Kaashoek, R. Morris, and N. Zeldovich. Non-scalable locks are dangerous. In Proc. Linux Symposium, 2012.

Google Scholar

[2]

A. T. Clements, M. F. Kaashoek, and N. Zeldovich. Scalable address spaces using RCU balanced trees. In Proc. ASPLOS, 2012.

Digital Library

Google Scholar

[3]

D. Dice, V. J. Marathe, and N. Shavit. Lock cohorting: A general technique for designing NUMA locks. In Proc. PPoPP, 2012.

Digital Library

Google Scholar

[4]

K. Fatourou, Panagiota and Nikolaos. Revisiting the combining synchronization technique. In Proc. PPoPP, 2012.

Digital Library

Google Scholar

[5]

D. Hendler, I. Incze, N. Shavit, and M. Tzafrir. Flat combining and the synchronization-parallelism tradeoff. In Proc. SPAA, 2010.

Digital Library

Google Scholar

[6]

J.-P. Lozi, F. David, G. Thomas, J. Lawall, G. Muller, et al. Remote Core Locking: migrating critical-section execution to improve the performance of multithreaded applications. In Proc. USENIX ATC, 2012.

Digital Library

Google Scholar

[7]

V. Luchangco, D. Nussbaum, and N. Shavit. A hierarchical CLH queue lock. In Proc. ICPP, 2006.

Digital Library

Google Scholar

[8]

P. E. McKenney, J. Appavoo, A. Kleen, O. Krieger, R. Russell, D. Sarma, and M. Soni. Read-copy update. In Proc. AUUG, 2001.

Google Scholar

[9]

J. M. Mellor-Crummey and M. L. Scott. Algorithms for scalable synchronization on shared-memory multiprocessors. ACM Trans. Comput. Syst., 9(1):21--65, Feb. 1991.

Digital Library

Google Scholar

[10]

Y. Oyama, K. Taura, and A. Yonezawa. Executing parallel programs with synchronization bottlenecks efficiently. In Proc. PDSIA, 1999.

Google Scholar

[11]

Z. Radovic and E. Hagersten. Hierarchical backoff locks for nonuniform communication architectures. In Proc. HPCA, 2003.

Digital Library

Google Scholar

[12]

N. Vasudevan, K. S. Namjoshi, and S. A. Edwards. Simple and fast biased locks. In Proc. PACT, 2010.

Digital Library

Google Scholar

Cited By

View all

Chabbi MAmer ALiu X(2020)Efficient Abortable-locking Protocol for Multi-level NUMA SystemsACM Transactions on Parallel Computing10.1145/33997287:3(1-32)Online publication date: 10-Jul-2020
https://dl.acm.org/doi/10.1145/3399728
Liu NZang BChen HGupta RShen X(2020)No barrier in the roadProceedings of the 25th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming10.1145/3332466.3374535(348-361)Online publication date: 19-Feb-2020
https://dl.acm.org/doi/10.1145/3332466.3374535
Xue DHuang LLi CWu C(2019)Dapper: An Adaptive Manager for Large-Capacity Persistent MemoryIEEE Transactions on Computers10.1109/TC.2019.289983668:7(1019-1034)Online publication date: 1-Jul-2019
https://doi.org/10.1109/TC.2019.2899836
Show More Cited By

Recommendations

Scalable adaptive NUMA-aware lock: combining local locking and remote locking for efficient concurrency
PPoPP '16

Scalable locking is a key building block for scalable multi-threaded software. Its performance is especially critical in multi-socket, multi-core machines with non-uniform memory access (NUMA). Previous schemes such as local locking and remote locking ...
Scalable Adaptive NUMA-Aware Lock

Scalable locking is a key building block for scalable multi-threaded software. Its performance is especially critical in multi-socket, multi-core machines with non-uniform memory access (NUMA). Previous schemes such as in-place locks and delegation ...
An efficient lock-aware transactional memory implementation
ICOOOLPS '09: Proceedings of the 4th workshop on the Implementation, Compilation, Optimization of Object-Oriented Languages and Programming Systems

Transactional memory (TM) is an emerging concurrency control mechanism that provides a simple and composable programming model. Unfortunately, transactions violate the semantics of mutual exclusion locks when they execute concurrently. Due to the ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

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

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]

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

Qualifiers

Research-article

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

5
Total Citations
View Citations
378
Total Downloads

Downloads (Last 12 months)15
Downloads (Last 6 weeks)1

Reflects downloads up to 13 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Chabbi MAmer ALiu X(2020)Efficient Abortable-locking Protocol for Multi-level NUMA SystemsACM Transactions on Parallel Computing10.1145/33997287:3(1-32)Online publication date: 10-Jul-2020
https://dl.acm.org/doi/10.1145/3399728
Liu NZang BChen HGupta RShen X(2020)No barrier in the roadProceedings of the 25th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming10.1145/3332466.3374535(348-361)Online publication date: 19-Feb-2020
https://dl.acm.org/doi/10.1145/3332466.3374535
Xue DHuang LLi CWu C(2019)Dapper: An Adaptive Manager for Large-Capacity Persistent MemoryIEEE Transactions on Computers10.1109/TC.2019.289983668:7(1019-1034)Online publication date: 1-Jul-2019
https://doi.org/10.1109/TC.2019.2899836
Calciu ISen SBalakrishnan MAguilera M(2017)How to implement any concurrent data structure for modern serversACM SIGOPS Operating Systems Review10.1145/3139645.313965051:1(24-32)Online publication date: 11-Sep-2017
https://dl.acm.org/doi/10.1145/3139645.3139650
Antić JChatzopoulos GGuerraoui RTrigonakis V(2016)Locking Made EasyProceedings of the 17th International Middleware Conference10.1145/2988336.2988357(1-14)Online publication date: 28-Nov-2016
https://dl.acm.org/doi/10.1145/2988336.2988357

View Options

Login options

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

Cited By

Recommendations

Scalable adaptive NUMA-aware lock: combining local locking and remote locking for efficient concurrency

Scalable Adaptive NUMA-Aware Lock

An efficient lock-aware transactional memory implementation