language: en

Scalable Atomic Primitives for Distributed Shared Memory Multiprocessors

Maged M. Michael Michael L. Scott
Computer Science Department University of Rochester
Rochester, NY 14627-0226
{michael,scott}@cs.rochester.edu July 1994

Abstract Our research addresses the general topic of atomic update of shared data structures on large-scale shared-memory multiprocessors. In this paper we consider alternative implementations of the general-purpose single-address atomic primitives fetch and , compare and swap, load linked, and store conditional. These primitives have proven popular on small-scale bus-based machines, but have yet to become widely available on large-scale, distributed shared memory machines. We propose several alternative hardware implementations of these primitives, and then analyze the performance of these implementations for various data sharing patterns. Our results indicate that good overall performance can be obtained by implementing compare and swap in the cache controllers, and by pro viding an additional instruction to load an exclusive copy of a cache line.

1 INTRODUCTION