DocumentCode :
2161992
Title :
A new cache directory scheme
Author :
Wu, Yuguang ; Muntz, Richard R.
Author_Institution :
AT&T Bell Labs., Holmdel, NJ, USA
fYear :
1996
fDate :
12-14 Jun 1996
Firstpage :
466
Lastpage :
472
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;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Parallel Architectures, Algorithms, and Networks, 1996. Proceedings., Second International Symposium on
Conference_Location :
Beijing
ISSN :
1087-4089
Print_ISBN :
0-8186-7460-1
Type :
conf
DOI :
10.1109/ISPAN.1996.509027
Filename :
509027
Link To Document :
بازگشت