Evaluating Synchronization Overhead for Emerging Pointer Chasing Workloads

Modern computing applications are growing in both complexity and data consumption. At the heart of these applications is the concurrent search data structure, which stores the data by linking together a series of nodes using pointers. To process such a dataset is to traverse these linked structures in a process called pointer chasing. These types of workloads are common in a variety of domains such as graph processing and databases, and are characterized by poor memory locality, lock contention and pose significant challenges for modern multi-core systems. In this thesis titled "Evaluating Synchronization Overhead for Emerging Pointer Chasing Workloads" I investigate the synchronization overhead incurred by pointer chasing workloads in a modern multi-core system. Using the gem5 computer architecture simulator, as well as the ASCYLIB library of pointer chasing workloads, the research evaluates the impact on synchronization by varying core count as well as the workload size. The study focuses on four different performance metrics, namely lock acquisition time variance, memory operations per second (MOPS), simulation statistics and lock contention statistics. An evaluation of these four metrics highlighted the significant impact of the memory hierarchy and lock contention on the system's performance. Though this thesis was able to contribute with optimization suggestions that mitigate synchronization overhead when running pointer chasing workloads, further research is needed to gain a comprehensive understanding.