Title :
A new cache directory scheme
Author :
Wu, Yuguang ; Muntz, Richard R.
Author_Institution :
AT&T Bell Labs., Holmdel, NJ, USA
Abstract :
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
Keywords :
cache storage; computational complexity; parallel architectures; reconfigurable architectures; shared memory systems; tree data structures; balanced binary-tree; cache addition; cache deletion; cache directory; cache operations; coherence protocols; current data sharing; directory scheme; optimal directory scheme; scalable; scalable architectures; time complexities; tree structure; Broadcasting; Delay; Laboratories; Memory architecture; Microwave integrated circuits; Multiprocessing systems; Multiprocessor interconnection networks; Protocols; Telecommunication traffic; Tree data structures;
Conference_Titel :
Parallel Architectures, Algorithms, and Networks, 1996. Proceedings., Second International Symposium on
Conference_Location :
Beijing
Print_ISBN :
0-8186-7460-1
DOI :
10.1109/ISPAN.1996.509027