Scalability of Atomic Primitives on Distributed Shared Memory Multiprocessors

Many hardware primitives have been proposed for synchronization and atomic memory update on shared-memory multiprocessors. In this paper, we focus on general-purpose primitives that have proven popular on small-scale bus-based machines, but have yet to become widely available on large-scale, distributed-memory machines. Specifically, we propose several alternative implementations of fetch_and_Φ, compare_and_swap, and load_linked/store_conditional. We then analyze the performance of these implementations for various data sharing patterns, in both real and synthetic applications. Our results indicate that good overall performance can be obtained by implementing compare_and_swap in a multiprocessor's cache controllers, and by providing an additional instruction to load an exclusive copy of a line