A new cache directory scheme

This paper proposes a new directory scheme with a balanced binary-tree structure that dynamically changes with current data sharing. It is scalable in allowing an unlimited number of caches to share the same data block, and can carry out coherence operations quickly, i.e., in logarithmic time. This scheme is especially appropriate for update-oriented coherence protocols where the sharing structure is preserved across writes. We demonstrate how the tree directories handle cache addition (a cache acquiring a data block copy) and cache deletion (a cache surrendering a data block copy due to its local block replacement), and present their respective time complexities. It can be shown that this kind of tree structure is an asymptotically optimal directory scheme for scalable architectures, carrying out all cache operations in minimum possible time