An efficient tree cache coherence protocol for distributed shared memory multiprocessors

Yeimkuan Chang, Laxmi N. Bhuyan

Research output: Contribution to journalArticlepeer-review

9 Citations (Scopus)


Directory schemes have long been used to solve the cache coherence problem for large scale shared memory multiprocessors. In addition, tree-based protocols have been employed to reduce the directory size and the invalidation latency for a large degree of data sharing in the system. However, the existing tree-based protocols involve a very high communication overhead for maintaining a balanced tree, especially when the degree of data sharing is low. 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 connects 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 logarithmic invalidation latency. We evaluate the performance of our protocol by running four applications on the Proteus execution-driven simulator. Our simulation results show that the performance of the proposed protocol is very close to that of the full-map protocol.

Original languageEnglish
Pages (from-to)352-360
Number of pages9
JournalIEEE Transactions on Computers
Issue number3
Publication statusPublished - 1999

All Science Journal Classification (ASJC) codes

  • Software
  • Theoretical Computer Science
  • Hardware and Architecture
  • Computational Theory and Mathematics


Dive into the research topics of 'An efficient tree cache coherence protocol for distributed shared memory multiprocessors'. Together they form a unique fingerprint.

Cite this