A class of compatible cache consistency protocols and their support by the IEEE futurebus

ABSTRACT

Standardization of a high performance blackplane bus, so that it can accommodate boards developed by different vendors, implies the need for a standardized cache consistency protocol. In this paper we define a class of compatible consistency protocols supported by the current IEEE Futurebus design. We refer to this class as the MOESI class of protocols; the term “MOESI” is derived from the names of the states. This class of protocols has the property that any system component can select (dynamically) any action permitted by any protocol in the class, and be assured that consistency is maintained throughout the system. Included in this class are actions suitable for copyback caches, write through caches and non-caching processors. We show that the Berkeley protocol and the Dragon protocol fall within this class, and can be extended to be compatible with other members of the class. The Illinois, Firefly and Write-Once protocols can be adapted to be compatible with this class; the facilities of he Futurebus currently do not support those protocols without adaptation. We discuss very briefly performance choices among protocols, and also other issues relating to a standard bus consistency protocol.

References

1. ANSI86.ANSI/IEEE Standard 960 - 1986 Fastbus Modular High Speed Data Acquisition and Control System
2. Arch84.James Archibald and Jean-Loup Baer, "An Economical Solution to the Cache Coherency Problem", Proc. 11'th Ann. Syrup. on Comp. Arch., June, 1984, Ann Arbor, Michigan, pp. 355-362.
3. Arch85.James Archibald and Jean-Loup Baer, "An Evaluation of Cache Coherence Solutions in Sharod-Bus Multiprocessors", Tech. Rpt. 85-10-05, October, 1985, Computer Science Dept., University of Washington, Seattle, Wash.
4. Bala84.R. V. Balakrishnan, "The Proposed IEEE 896 Futurebus - A Solution to the Bus Driving Problem", IEEE Micro, August, 1984, pp. 23-27.
5. Borr84.Paul Borrill and John Theus, "An Advanced Communication Protocol for the Proposed IEEE 896 Futurebus", IEEE Micro, August, 1984, pp. 42-56.
6. Borr85.Paul L. Borrill, "Microstandards Special Feature: A Comparison of 32-Bit Buses", IEEE MICRO, December, 1985, pp. 71-79.
7. Cens78.Lucien Censier and Paul Feautrier, "A New Solution to Coherence Problems in Multicache Systems", IEEETC, C-27, 12, December, 1978, pp. 1112-1118.
8. Cho86.James Cho, Alan Jay Smith and Howard Sachs, "The Memory Architecture and Cache and Memory Management Unit for the Fairchild CLIPPER Processor", February, 1986, submitted for publication. (Available from Fairchild Advanced Processor Division, 4001 Miranda Ave., Palo Alto, Ca., or from Alan Smith, UC Berkeley.)
9. Coop83.Steve Cooper, "Multibus Continues to Evolve to Meet the Challenges of the VLSI Revolution", Proe. NCC 1983, pp. 497-501.
10. Dubo82.M. Dubois and F. Briggs, "Effects of Cache Coherency in Multiproeessors", IEEETC C-31, 11, November, 1982, pp. 1083-1099
11. Elay85.Khaled A. EI-Ayat and Rakesh Agarwal, "The Intel 80386 - Architecture and Implementation'", IEEE MICRO, December, 1985, pp. 4-22.
12. Emer41.Ralph Waldo Emerson, Essays: First Series, 1841, "Self Reliance".
13. Fair85.Fairchild, "CLIPPER Module Product Description", Fairchild Camera and Instrument Corporation, October, 1985.
14. Fish84.Wayne Fischer, "The VMEbus Project", Proc. IEEE. Compcon, February, 1984, pp. 376-378.
15. Fran84.Steven J. Frank, "Tightly Coupled Multiprocessor System Speeds Memory Access Times", Electronics, January 12, 1984, pp. 164-169.
16. Good83.James R. Goodman, "Using Cache Memory to Reduce Processor-Memory Traffic", Proc. 10'th Ann. Int. Symp. on Comp. Arch., June, 1983, Stockholm, Sweden, pp. 124-131.
17. Gust84.David B. Gustavson, "Computer Buses- A Tutorial", IEEE MICRO, August, 1984, pp. 7-22.
18. Gust83.David B. Gustavson and John Theus, "Wire Or Logic on Transmission Lines", IEEE MICRO, 3, 3, June, 1983, pp. 51-55.
19. Hill84.Mark Hill and Alan Jay Smith, "Experimental Evaluation of On-Chip Microprocessor Cache Memories", Proc. 11'th Ann. Symp. on Computer Architecture, June, 1984, Ann Arbor, Michigan, pp. 158-166.
20. Katz85.R. H. Katz, S. J. Eggers, D. A. Wood, C. L. Perkins, and R. G. Sheldon, "Implementing a Cache Consistency Protocol", Proc. 12'th Ann. Int. Symp. on Comp. Arch., June, 1985, Boston, Mass, pp. 276-283.
21. Mate85.Richard Mateosian, "National's NS32332 CPU: A Graceful Extension of the Series 32000", Profession Program Session Record, Wescon/85, November, 1985, San Francisco, Ca., Session 1: 32-Bit Microprocessors - Part I.
22. McCr84.Edward M. McCreight, "The Dragon Computer System: An Early Overview", June, 1984, Technical Report, Xerox PARC.
23. Moto84.Motorola Corporation, "MC68020 Technical Summary", 1984.
24. Mous86.J. Moussouris, L. Crudele, D. Freitas, C. Hansen, E. Hudson, R. March, S. Przybylski, T. Riordan, C. Rowen, and D. Van't Hof, "A CMOS RISC Processor with Integrated System Functions", Proc. IEEE Compcon, March, 1986, pp. 126-132.
25. P896.IEEE P896 Draft Standard, Backplane Bus (Futurebus)
26. P1014.IEEEP1014 Versatile Backplane Bus (VME Bus)
27. Papa84.Mark Papamarcos and Janak Patel, "A Low- Overhead Coherence Solution for Multiprocessors with Private Cache Memories", Proc. l l ' t h Ann. Int. Symp. on Comp. Arch., June, 1984, Ann Arbor, Michigan, pp. 348- 354.
28. Phil85.David Phillips, "The Z80000 Microprocessor", IEEE MICRO, December, 1985, pp. 23-36.
29. Puza83.T. R. Puzak, R. N. Rechtschaffen and K. So, "Managing Targets of Multiprocessor Cross Interrogates", IBM Tech. Disc. Bull., 25, 12, May, 1983, p. 6462.
30. Rudo84.Larry Rudolph and Zary Segall, "Dynamic Decentralized Cache Schemes for MIMD Parallel Architectures", Proc. 11'th Ann. Int. Symp. on Comp. Arch., June, 1984, Ann Arbor, Michigan, pp. 340-347.
31. Smit79.Alan Jay Smith, "Characterizing the Storage Process and its Effect on the Update of Main Memory by Write-Through", JACM, 26, 1, January, 1979, pp. 6-27.
32. Smit82.Alan Jay Smith, "Cache Memories", Computing Surveys, 14, 3, September, 1982, pp. 473-530.
33. Smit84a.Alan Jay Smith, "CPU Cache Memories", to appear in Handbook for Computer Designers, ed. Flynn and Rossman.
34. Smit84b.Alan Jay Smith, "Trends and Prospects in Computer System Design", part of proceedings of a Seminar on High Technology, at the Korea Institute for Industrial Economics and Technology, Seoul, Korea, June 21-22, 1984. Available as UC Berkeley CS Report UCB/CSD84/219. Verbatim transcript of speech published in "Challenges to High Technology Industries", Korea Institute for Economics and Technology, pp. 79-152.
35. Smit85a.Alan Jay Smith, "Problems, Directions and Issues in Memory Hierarchies", Proc. 18'th Annual Hawaii International Conference on System Sciences, January 2-4, 1985, Honolulu, Hawaii, pp. 468-476. Also available as UC Berkeley CS Report UCB/CSD84/220.
36. Smit85b.Alan Jay Smith, "Cache Evaluation and the Impact of Workload Choice", Report UCB/CSD85/229, March, 1985, Proc. 12'th International Symposium on Computer Architecture, June 17-19, 1985, Boston, Mass, pp. 64- 75.
37. Smit85c.Alan Jay Smith, "Line (Block) Size Selection in CPU Cache Memories", June, 1985. To appear, IEEETC. Available as UC Berkeley CS Report UCB/CSD85/239.
38. Smit85d."CPU Cache Consistency with Software Support and Using "One Time Identifiers'"', Proc. Pacific Computer Communication Symposium, Seoul, Republic of Korea, October 22-24, 1985, pp. 142-150.
39. Smit86."Bibliography and Readings on CPU Cache Memories", February, 1986, to appear, Computer Architecture News.
40. Tang76.C. K. Tang, "Cache System Design in the Tightly Coupled Multiprocessor System", Proc. NCC, 1976, pp. 749- 753.
41. Texa83.Texas Instruments, "NuBus Specification", 1983, TI-2242825-0001.
42. Vern85.Mary K. Vernon and Mark A. Holliday, "Performance Analysis of Multiprocessor Cache Consistency Protocols Using Generalized Timed Petri Nets", Tech. Rpt., University of Wisconsin, Computer Science Dept., 1985. To appear, Proc. Sigmetrics '86.

Index Terms

• Computer systems organization

  • Architectures

    • Parallel architectures

      • Interconnection architectures

  • Dependable and fault-tolerant systems and networks

• General and reference

  • Cross-computing tools and techniques

    • Performance

  • Document types

    • Computing standards, RFCs and guidelines

• Hardware

  • Integrated circuits

    • Interconnect

      • Metallic interconnect

    • Semiconductor memory

      • Dynamic memory

• Networks

  • Network performance evaluation

• Social and professional topics

  • Professional topics

    • Computing industry

• Software and its engineering

  • Software creation and management

    • Designing software

  • Software organization and properties

    • Contextual software domains

      • Operating systems