Technical Report MSC-2012-18

Title: Exploiting Locality and NUMA in Scalable Concurrent Libraries
Authors: Elad Gidron
Supervisors: Idit Keidar
Abstract: Emerging computer architectures pose many new challenges for software development. First, as the number of computing elements constantly increases, the importance of scalability of parallel programs becomes paramount. Second, accessing memory has become the principal bottleneck, while multi-CPU systems are based on NUMA architectures, where memory access from different chips is asymmetric. Therefore, it is instrumental to design software with local data access, cache- friendliness, and reduced contention on shared memory locations, especially across chips. Furthermore, as systems get larger, their behavior becomes less predictable, underscoring the importance of robust programs that can overcome unexpected thread stalls.

In our work we focus on two problems:

1. We design and implement a scalable and highly-efficient non-blocking consumer producer task pool, with lightweight synchronization-free operations in the common case. Its data allocation scheme is cache-friendly and highly suitable for NUMA environments. Moreover, our pool is robust in the face of imbalanced loads and unexpected thread stalls.

2. We consider the case of improving metadata locality in word-based STMs. To this end, we evaluate a locality-conscious approach for maintaining versioned locks in TL2. The speedup of the improved algorithm reaches a hundred percent on STAMP benchmarks. We show that this speedup stems from the following factors: 1) improved spacial and temporal locality, 2) reduced false sharing and 3) less false conflicts.

CopyrightThe above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information

Remark: Any link to this technical report should be to this page (, rather than to the URL of the PDF files directly. The latter URLs may change without notice.

To the list of the MSC technical reports of 2012
To the main CS technical reports page

Computer science department, Technion