CACHE-BASED SYNCHRONIZATION IN SHARED-MEMORY MULTIPROCESSORS

In shared memory multiprocessors, efficient synchronization is imperat ive to assure good performance. There are two aspects to the ''cost'' of a synchronization operation: the first is the waiting time at synch ronization points, and the second is the intrinsic overhead in perform ing the operation. The overhead has two components. The first componen t deals with contention resolution for synchronization operation among competing processors. The second component deals with the shared data accesses that the processor has to perform once it enters a synchroni zation region. We present a mechanism to reduce the overhead of perfor ming synchronization operations in a cache-based shared memory multipr ocessor. The mechanism is based on the intuitive notion that parallel programs invariably use synchronization operations to govern the acces s to shared data. Traditional multiprocessor cache protocols treat syn chronization accesses the same way as normal read/write memory accesse s, leading to inefficiencies in performing synchronization operations which ultimately limit the scalability of such systems. The key idea i n our approach is to combine synchronization with the coherence mainte nance for the cached data. Each cache line maintains states for synchr onization as well as for cache coherence, and the cache protocol ensur es the correctness of the synchronization operations and the coherence of the data at these synchronization points. To assess the performanc e gain due to the proposed mechanism, simulation studies are performed using a workload model that represents a dynamic scheduling paradigm which forms the core of several parallel programs. Results from simula tion studies show that the proposed cache-based synchronization perfor ms significantly better than traditional cache coherence approaches. ( C) 1996 Academic Press, Inc.