טכניון מכון טכנולוגי לישראל
הטכניון מכון טכנולוגי לישראל - בית הספר ללימודי מוסמכים  
M.Sc Thesis
M.Sc StudentGidron Elad
SubjectExploiting Locality and NUMA in Scalable Conncurrent
Libraries
DepartmentDepartment of Computer Science
Supervisor Professor Idit Keidar
Full Thesis textFull thesis text - English Version


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.