Scalable directories and a collective cache invalidation technique for scalable shared memory multiprocessors

Abstract

Scalable shared memory multiprocessor (SSMP) systems achieve both the easy programming model and the scalable performance. The former comes from the provision of a single, coherent view of shared address space; the latter from the scalable interconnection networks (IN) and the distribution of physical memory sections to individual node computers connected with one another by them. For low-latency, high-bandwidth shared memory accesses, per-processor caches should be allowed to cache data from the shared address space. Multiple copies of a shared data object, however, become incoherent if multiple processors are permitted to write to the cached copies simultaneously without coordination. This problem, which is called the {\em cache coherence problem}, is of great significance in the performance of cache coherent SSMP systems. Directory cache coherence schemes keep caches coherent by point-to-point communications only to those processors caching the memory block by using the directory next to memory which stores the locations of cached copies of every memory block. By avoiding costly broadcast, saturation in the IN can be avoided and system scalability increases. Unfortunately, the most straightforward directory scheme, the full map directory scheme, requires directory memory which grows as the square of the system size. Many directory schemes have been proposed to mitigate this directory memory overhead scaling problem, but they usually either require large bandwidth for coherence traffic or exhibit poor system performance. This dissertation explores various design points of the scalable directories: the individual directory element design, the arrangement of such directory elements, and the communication support for cache coherence. First, this dissertation proposes a new directory element called the segment directory, which is a hybrid of the full map vector and the pointer. It can be used in place of the pointer in most pointer-based directory schemes to i...