Scalable synchronization techniques and their applications in large-scale shared memory multiprocessors
Der-Chung Cheng · 1992
Shared memory multiprocessors offer a relatively simple programming model and are suitable for a wide variety of parallel applications. Unfortunately, shared memory multiprocessors cannot be scaled up in size due to memory and switch contentions that can result in the formation of hot spot. Spinning on synchronization variables appears to be the main culprit behind the formation of hot spots. The purpose of this dissertation is to propose a set of efficient synchronization mechanisms that do not promote hot-spot formation, allowing the system to be scaled up easily. We will show that a low-latency barrier synchronizer can be used not only for high-speed barrier synchronization but also, very profitably, for implementing software combining (allowing distributed hot-spot accessing), for data and producer-consumer type synchronization and for the implementation of scan-primitives. A high-speed barrier synchronizer can also be used to implement highly-concurrent data structures and will also allow a MIMD system to be effectively operated in a SIMD-style mode, giving rise to a number of potential advantages. The key idea behind the proposed barrier synchronizer is to use a surprisingly simple hardware (one latch and a few gates per processing element/board) to allow processors to participate dynamically. A variation of this barrier synchronizer also allows, with the assistance of a scheduler, to handle barrier synchronizations with arbitrary and non-predictable branching within the control threads. The compiler can make use of this barrier synchronization to implement producer-consumer type of synchronization within and across the threads and thus allow the inclusion of software controlled caches. We use simulations to confirm that our proposed synchronizers and their applications outperform the existing schemes.