A Universal Construction to implement Concurrent Data Structure for NUMA-muticore
- 9 August 2021
- conference paper
- conference paper
- Published by Association for Computing Machinery (ACM) in 50th International Conference on Parallel Processing
Abstract
Universal constructions are attractive as they can turn a sequential implementation of any data structure into a concurrent implementation. However, existing universal constructions have limitations, such as imposing high copying overhead, or poor scalability on NUMA systems mainly due to their lack of NUMA-aware design principles. To overcome these limitations, this paper introduces CR, a universal construction that provides highly scalable updates on NUMA systems while offering fast read-side performance. CR achieves NUMA-awareness by utilizing delegation within a NUMA node and a global shared log to maintain the consistency of replicas of data structures across nodes. Using CR does not require expertise in concurrent data structure design. Our evaluation shows that CR has up to 11.2 times better performance compared to a state-of-the-art universal construction CX on our tested sequential data structures. To demonstrate the effectiveness and applicability of CR, we have applied CR to an in-memory database system. The database shows up to 18.1 times better performance compared to the original version.Keywords
This publication has 17 references indexed in Scilit:
- Scalable Adaptive NUMA-Aware LockIEEE Transactions on Parallel and Distributed Systems, 2016
- Investigating the Performance of Hardware Transactions on a Multi-Socket MachinePublished by Association for Computing Machinery (ACM) ,2016
- Optimistic concurrency with OPTIKPublished by Association for Computing Machinery (ACM) ,2016
- Read-log-updatePublished by Association for Computing Machinery (ACM) ,2015
- Cache Coherence Protocol and Memory Performance of the Intel Haswell-EP ArchitecturePublished by Institute of Electrical and Electronics Engineers (IEEE) ,2015
- Transactional MemoryPublished by Springer Science and Business Media LLC ,2015
- Highly-Efficient Wait-Free SynchronizationTheory of Computing Systems, 2013
- A Methodology for Implementing Highly Concurrent Data ObjectsACM SIGOPS Operating Systems Review, 1992
- Wait-free synchronizationACM Transactions on Programming Languages and Systems, 1991
- Linearizability: a correctness condition for concurrent objectsACM Transactions on Programming Languages and Systems, 1990