A quantitative architectural evaluation of synchronization algorithms and disciplines on ccNUMA systems
Dimitrios S. Nikolopoulos, Theodore S. Papatheodorou · 1999
This paper assesses the performance and scalability of several software synchronization algorithms, as well as the interrelationship between synchronization, multiprogramming and parallel job scheduling, on ccNUMA systems.Using the SGl Origin2000, we evaluate synchronization algorithms for spin locks, lock-free concurrent queues, and barriers.We analyze the sensitivity of synchronization algorithms to the hardware implementation of elementary synchronization primitives and investigate in-depth the architectural implications and particularly the tradeoffs between implementing synchronization primitives with cacheable synchronization variables or at-memory.The architectural study enables us to contribute scalable, customized implementations of synchronization algorithms, including a hybrid scheduler-conscious queue lock and a lock-free queue.We also evaluate different combinations of synchronization algorithms, synchronization disciplines that cope with the effects of multiprogramming and different parallel job scheduling strategies, using the Cellular IEUX operating system as a case study. introductionCache Coherent Non Uniform Memory Access (ccNUMA) architectures have recently attracted considerable research and commercial interest, as they present strong advantages in the direction of achieving high performance.At the same time, synchronization is still an intrusive source of bottlenecks in parallel programs for shared memory.The importance of synchronization has motivated a vast amount of research efforts, which contributed several efficient algorithms for tightly-coupled small-scale symmetric multiprocessors (SMPs), as well as scalable algorithms for distributed memory multiprocessors.Whether these solutions are still sufficient for modern ccNUMA systems remains an open and important question.This paper addresses some significant issues of synchronization on ccNUMA systems.In this direction, we conduct a thorough architectural evaluation of software synchronization algorithms both standalone and in conjunction with spinning and scheduler-conscious disciplines, embedded in synchronization algorithms to cope with the interferences of multiprogramming and the operating sys-Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distribuled for profit or commercial advantage and that copies hear this notice and the I'ull citation on the tirst page.To copy otherwise, to republish, to post WI xrvcrs or to wdistrihutc to lists.requires prior specific permission andior a fee.