CLoF
Open Access
- 26 October 2021
- conference paper
- conference paper
- Published by Association for Computing Machinery (ACM) in Proceedings of the ACM SIGOPS 28th Symposium on Operating Systems Principles CD-ROM
Abstract
Efficient locking mechanisms are extremely important to support large-scale concurrency and exploit the performance promises of many-core servers. Implementing an efficient, generic, and correct lock is very challenging due to the differences between various NUMA architectures. The performance impact of architectural/NUMA hierarchy differences between x86 and Armv8 are not yet fully explored, leading to unexpected performance when simply porting NUMA-aware locks from x86 to Armv8. Moreover, due to the Armv8 Weak Memory Model (WMM), correctly implementing complicated NUMA-aware locks is very difficult. We propose a Compositional Lock Framework (CLoF) for multi-level NUMA systems. CLoF composes NUMA-oblivious locks in a hierarchy matching the target platform, leading to hundreds of correct by construction NUMA-aware locks. CLoF can automatically select the best lock among them. To show the correctness of CLoF on WMMs, we provide an inductive argument with base and induction steps verified with model checkers. In our evaluation, CLoF locks outperform state-of-the-art NUMA-aware locks in most scenarios, e.g., in a highly contended LevelDB benchmark, our best CLoF locks yield twice the throughput achieved with CNA lock and ShflLock on large x86 and Armv8 servers.Keywords
This publication has 14 references indexed in Scilit:
- Model checking for weakly consistent librariesPublished by Association for Computing Machinery (ACM) ,2019
- Compact NUMA-aware LocksPublished by Association for Computing Machinery (ACM) ,2019
- Contention-conscious, locality-preserving locksACM SIGPLAN Notices, 2016
- For a Microkernel, a Big Lock Is FinePublished by Association for Computing Machinery (ACM) ,2015
- High performance locks for multi-level NUMA systemsPublished by Association for Computing Machinery (ACM) ,2015
- Adaptive integration of hardware and software lock elision techniquesPublished by Association for Computing Machinery (ACM) ,2014
- NUMA-aware reader-writer locksPublished by Association for Computing Machinery (ACM) ,2013
- Lock cohortingACM SIGPLAN Notices, 2012
- Algorithms for scalable synchronization on shared-memory multiprocessorsACM Transactions on Computer Systems, 1991
- Adaptive backoff synchronization techniquesACM SIGARCH Computer Architecture News, 1989