A hybrid directory-based cache coherence protocol for large-scale shared-memory multiprocessors and its performance evaluation
Kwo-Yuan Greg Shieh · 1998
Directory schemes offer good solutions to the cache coherence problem for large-scale multiprocessors. However, various directory schemes have different problems. Examples are that a full-map directory is not scalable with respect to memory overhead; the limited-directory schemes reduce the size of directory memory but increase the amount of invalidation traffic. Among the directory schemes, hierarchical directories offer a good solution to the hot-spot problem. A hot-spot is a common variable that is accessed by a large number of processors simultaneously. These variables could be synchronization variables, loop index variables for parallel programs, etc. The hierarchical directory schemes have a natural form of concurrent read combining and parallel invalidation. The hierarchical directory, however, increases the request latency because the hierarchy has to be traversed for every request and does not scale with directory memory required. The directory overhead scales as O(N2) with the number of processors, N. In this dissertation, a hybrid directory scheme combining a limited directory scheme and a hierarchical directory scheme is presented for large-scale sharedmemory multiprocessors. For parallel applications, hot-spots are exceptional cases. Use of an hierarchical directory can alleviate such hot-spots and avoid memory contention problem. For the normal (non hot-spot) reference, pattern, simulations show that the performance of the limited directory approaches that of the full- mapped directory [Chaiken90][Weber93]. Trace driven simulation, using traces collected from several applications, is used to compare the performance of the hybrid directory, the limited directory and the full map directory. Among them, the Weather data has a widely shared variable, which provides a typical example of hot spot contention. Simulation results show that the limited directory is very sensitive to this type of access, because it causes “pointer thrashing” problem and degrades the performance. However, the hybrid directory used the hierarchical directory to process this hot spot variable and reduces the total traffic of the limited directory with 2 pointers by 56.01%. Simulation shows that the performance of the hybrid directory is very close to that of the full map directory. For the other traces, the results show that the hybrid directory consistently improves the performance over that of the limited directory and is competitive with the full map directory. The storage requirement of the limited directory, the full map directory, the hierarchical directory and the hybrid directory is compared. The results show that the storage required for the hybrid directory is O(NlogN), which is scalable. Thus it can be concluded that this integrated approach—handling the common case in a limited directory and hot-spot cases in a hierarchical directory—is scalable with directory memory overhead and offers a good solution for large-scale multiprocessors with hot-spots.