On the inclusion properties for multi-level cache hierarchies

Abstract

The inclusion property is essential in reducing the cache coherence complexity for multiprocessors with multilevel cache hierarchies. We give some necessary and sufficient conditions for imposing the inclusion property for fully- and set-associative caches which allow different block sizes at different levels of the hierarchy. Three multiprocessor structures with a two-level cache hierarchy (single cache extension, multiport second-level cache, bus-based) are examined. The feasibility of imposing the inclusion property in these structures is discussed. This leads us to propose a new inclusion-coherence mechanism for two-level bus-based architectures.

References

1. 1 Archibald,J. and J.-L. Baer. An economical solution to the cache coherence problem. In Proc. 11th Symposium on Computer Architecture, pages 355-362, 1984.
2. 2 Archibald,J. and J.-L. Baer. Cache coherence protocols: Evaluation using a multiprocessor simulation model. ACll4 TOCS, 4(4):273-298, November 1986
3. 3 Baer, J.-L. and W.-H. Wang. Architectural choices for multi-level cache hierarchies. In Proc. 16th International Conference on Parallel Processing, pages 258-261, 1987.
4. 4 Baer,J.-L. and W.-H.Wang. Architectural choices for multi-level cache hierarchies. Technical Report TR 87- 01-04, University of Washington, January 1987.
5. 5 Censier,M. and P.Feautrier. A new solution to coherence .problems in multicache systems. IEEE TC, C- 27(12):1112-1118, December 1978.
6. 6 Chang, J.H., H. Chao and K. So. Cache design of a submicron cmos system/370. In Proc. 14th Symposium on Computer Architecture, pages 208-213, 1987.
7. 7 Enslow Jr., P.H. Multiprocessor organizations - a survey. Computing Surveys, 9(1):103-129, March 1977.
8. 8 Goodman, J. Coherency for multiprocessor virtual address caches. In Proc. Architectuml Support for Programming Languages and Operating Systems(ASPOLS-II), pages 72- 81, 1987.
9. 9 Hattori,A., Koshino,M. and S.Kamimoto. Three-level hierarchical storage system for FACOM M-380/382. In Proc. Information Processing IFIP, pages 693-697, 1983.
10. 10 Katz, R., Eggers, S., Wood, D., Perkins, C. and R.G. Sheldon. Implementing a cache coherence protocol. In Proc. 18th Symposium on Computer Architecture, pages 276- 283, 1985.
11. 11 Lam,C-Y. and S.Mudnick. Properties of storage hierarchy systems with multiple page sizes and redundant data. ACM TODS, 4(3):345-367, September 1979.
12. 12 Liptay, J. S. Structural aspects of the System/360 model 85 part II - the cache. IBM System Journal, 7(1):15-21, 1968,
13. 13 Short, R. T. A Study of Multilevel Cache Memories. Master's Thesis, University of Washington, 1987.
14. 14 Sweazey, P. and A.J. Smith. A class of compatible cache consistency protocols and their support by the IEEE futurebus. In Proc. 13th Symposium on Computer Amhitecture, pages 414-423, 1986.
15. 15 Wilson Jr., A.W. Hierarchical cache/bus architecture for shared memory multiprocessors. In Proc. 14th Symposium on Computer Architecture, pages 244-252, 1987.
16. 16 Winsor, D.C. and T.N. Mudge. Crosspoint cache architectures. In Proc. 16th International Conference on Parallel Processing, pages 266-269, 1987.

Index Terms

• Computer systems organization

  • Architectures

    • Parallel architectures

      • Multiple instruction, multiple data

• Hardware

  • Integrated circuits

    • Semiconductor memory

      • Dynamic memory