An efficient tree cache coherence protocol for distributed shared memory multiprocessors

Directory schemes have long been used to solve the cache coherence problem for large scale shared memory multiprocessors. In addition, tree-based prot ocols have been employed to reduce the directory size and the invalidation latency for a large degree of data sharing in the system. However, the exis ting tree-based protocols involve a very high communication overhead for ma intaining a balanced tree, especially when the degree of data sharing is lo w. This paper presents a new tree-based cache coherence protocol which is a hybrid of the limited directory and the linked list schemes. By utilizing a limited number of pointers in the directory, the proposed protocol connec ts the nodes caching a shared block in a tree fashion without incurring any communication overhead. In addition to the low communication overhead. the proposed scheme also possesses the advantages of the existing bit-map and tree-based linked list protocols, namely, scalable memory requirement and l ogarithmic invalidation latency. We evaluate the performance of our protoco l by running four applications on the Proteus execution-driven simulator. O ur simulation results show that the performance of the proposed protocol is very close to that of the full-map protocol.