Seo Dae Wha

The Transactions of the Korea Information Processing Society (1994 ~ 2000), Vol. 4, No. 3, pp. 821-830, Mar. 1997
10.3745/KIPSTE.1997.4.3.821,   PDF Download:

Abstract

The directory-based cache coherence scheme is an attractive approach to solve the cache coherence problem in a large-scale shred-memory multiprocessor. However, the existing directory-based schemes have some problems such as the enormous storage overhead for a directory, the long invalidation latency, the heavy network congestion, and the low scalability. For resolving these problems, we propose a new directory-based cache coherence scheme which is suitable for building scalable, shared-memory multiprocessors. In this scheme, each directory entry for a given memory block is a number-balanced binary tree(NBBT) structure. The NBBT has several properties to efficiently maintain the directory for the cache consistency such that the shape is unique, the maximum depth is log2n, and the tree has the minimum number of leaf nodes among the binary tree with n nodes. Therefore, this scheme can reduce the storage overhead, the network traffic, and the invalidation latency and can ensure the high scalability in the large-scale shared-memory multiprocessors.

Statistics
Cite this article