C2MP: a cache-coherent, distributed memory multiprocessor-system

ABSTRACT

Current research into the problems of cache coherency in multiprocessor (MP) systems, has primarily focused on bus based memory interconnection networks (M-ICN) and the use of various types of “snooping” cache coherency protocols. Bus bandwidth limitations can be alleviated through the use of wider bandwidth general interconnection structures, such as a crossbar switch. However, if private caches are used, the cache coherency problem becomes multiply compounded. Little work has been done to address this problem. A new distributed shared-memory multiprocessor system with private caches and for use with general memory interconnection networks (M-ICNs) is presented. A new distributed cache coherency-controller ($-K) unit is employed to manage coherency invalidation/updating over a dedicated bus based coherency interconnection network (C-ICN). This allows for cache-to-cache coherency updating to reduce the M-ICN traffic to only that of instruction/data transactions. This architecture incorporates a unique hierarchical, preemptive cache coherency protocol, simple enough to be implemented in hardware. A feasible implementation of a fully asynchronous crossbar switch is also presented as a possible general memory interconnection network (M-ICN).

REFERENCES

• Agar88a: A. Agarwal , R. Simoni , J. Hennessy , M. Horowitz, An evaluation of directory schemes for cache coherence, Proceedings of the 15th Annual International Symposium on Computer architecture, p.280-298, May 30-June 02, 1988, Honolulu, Hawaii, United States
• Agar88b: A. Agawal , A. Gupta, Memory-reference characteristics of multiprocessor applications under MACH, Proceedings of the 1988 ACM SIGMETRICS conference on Measurement and modeling of computer systems, p.215-225, May 24-27, 1988, Santa Fe, New Mexico, United States
• Arch84: James Archibald , Jean Loup Baer, An economical solution to the cache coherence problem, Proceedings of the 11th annual international symposium on Computer architecture, p.355-362, January 1984
• Arch86: James Archibald , Jean-Loup Baer, Cache coherence protocols: evaluation using a multiprocessor simulation model, ACM Transactions on Computer Systems (TOCS), v.4 n.4, p.273-298, Nov. 1986 [doi>10.1145/6513.6514]
• Arch87: J. K. Archibald, The cache coherence problem in shared-memory multiprocessors, University of Washington, Seattle, WA, 1987
• Atki87: Russell R. Atkinson , Edward M. McCreight, The dragon processor, Proceedings of the second international conference on Architectual support for programming languages and operating systems, p.65-69, October 1987, Palo Alto, California, United States
• BBN85: "The Butterfly Switch," Technical Report, BBN Laboratories Inc., 10 Fawcett Str., Cambridge, Ma., 02238, Rpt. No. 5874, October 1985.
• Baer87: Baer, Jean-Loup and Claude Girault, "Cache Coherence in MIMD Systems: A Petri Net Model for a Minimal State Solution," Dept. of C.S.,Univ. of Washington, Seattle, Technical Report 87-04-01, April 4, 1987, pp. 1-31.
• Chat86: Claude Girault , C. Chatelain , Serge Haddad, Specification and properties of a cache coherence protocol model, Advances in Petri Nets 1987, covers the 7th European Workshop on Applications and Theory of Petri Nets, p.1-20, June 01, 1986
• Chong88: H. Cheong , A. V. Vaidenbaum, A cache coherence scheme with fast selective invalidation, Proceedings of the 15th Annual International Symposium on Computer architecture, p.299-307, May 30-June 02, 1988, Honolulu, Hawaii, United States
• Died88: Tom Diede , Carl F. Hagenmaier , Glen S. Miranker , Jonathan J. Rubinstein , William S. Worley, Jr., The Titan Graphics Supercomputer Architecture, Computer, v.21 n.9, p.13-28, 30, September 1988 [doi>10.1109/2.14344]
• Dub82: Dubois, M. and F. Briggs, "Effects of Cache Coherency in Mulliprocessors," IEEE Transactions on Computers, Vol. C-31, No.ll, November 1982, pp. 1083-1099.
• Dub88a: Michel Dubois , Christoph Scheurich, Memory Access Dependencies in Shared-Memory Multiprocessors, IEEE Transactions on Software Engineering, v.16 n.6, p.660-673, June 1990 [doi>10.1109/32.55094]
• Dub88b: Michel, Dubois , Christoph Scheurich , Fayé A. Briggs, Synchronization, Coherence, and Event Ordering in Multiprocessors, Computer, v.21 n.2, p.9-21, February 1988 [doi>10.1109/2.15]
• Eggr88: S. J. Eggers , R. H. Katz, A characterization of sharing in parallel programs and its application to coherency protocol evaluation, Proceedings of the 15th Annual International Symposium on Computer architecture, p.373-382, May 30-June 02, 1988, Honolulu, Hawaii, United States
• Good88: J. R. Goodman , P. J. Woest, The Wisconsin multicube: a new large-scale cache-coherent multiprocessor, Proceedings of the 15th Annual International Symposium on Computer architecture, p.422-431, May 30-June 02, 1988, Honolulu, Hawaii, United States
• Hill88: Mark D. Hill, A Case for Direct-Mapped Caches, Computer, v.21 n.12, p.25-40, December 1988 [doi>10.1109/2.16187]
• Holl86: Holliday, Mark A., and Mary K. Vernon, "The GTPN Analyzer: Numerical Me~hods and User interface," Computer Science Dept., Univ. of Wisconsin, Madison, Teeh. Rpt. #639, April 1986, pp. 1-19.
• Holl87a: Mark A. Holliday , Mary K. Vernon, Exact performance estimates for multiprocessor memory and bus interference, IEEE Transactions on Computers, v.36 n.1, p.76-85, Jan. 1987 [doi>10.1109/TC.1987.5009450]
• Holl87b: Mark A. Holliday , Mary K. Vernon, A generalized timed petri net model for performance analysis, IEEE Transactions on Software Engineering, v.13 n.12, p.1297-1310, December 1, 1987 [doi>10.1109/TSE.1987.233141]
• Hsu85: Hsu, F. H., H. T. Kung, T. Nishizawa, and A. Sussman, "Architecture of the Link and Interconnected Chip," Chapel Hill Conf. on VLSI, 1985, pp. 439-461.
• Katz85: R. H. Katz , S. J. Eggers , D. A. Wood , C. L. Perkins , R. G. Sheldon, Implementing a cache consistency protocol, ACM SIGARCH Computer Architecture News, v.13 n.3, p.276-283, June 1985
• Marq87: Marquardt, Douglas E., "6g-Bit Digital Crossbar Switch," Gould Electronics Semiconductor Div., (Data Sheet), 2300 Buckskin Rd., Pocatello, Id., 83201, August 1987.
• Marq88: Marquardt, Douglas E., "Asynchronous Digital Arbiter," Patent Application, Gould Semiconductors Division, 2300 Buckskin Rd., Pocatello, Id., 83201, .August 1988.
• McC84: McCreight, Edward M., "The Dragon Computer System: An Early Overview," Technical Report, Xerox Corporation, Polo Alto Research Center, Palo Alto, Ca., 94304, December 7, 1984.
• Moni85: Monier, Louis, Pradeep Sindhu, "The Architecture of the Dragon," 13th IEEE International Conference, IEEE, February 1985, pp. 118-I21.
• Mura88: Kazuaki Murakami , Akira Fukuda , Toshinori Sueyoshi , Shinji Tomita, An overview of the Kyushu University reconfigurable parallel processor, ACM SIGARCH Computer Architecture News, v.16 n.4, p.130-137, Sept. 1988 [doi>10.1145/54331.54341]
• Nguy88: T. M. Nguyen , V. P. Srini , A. M. Despain, A two-tier memory architecture for high-performance multiprocessor systems, Proceedings of the 2nd international conference on Supercomputing, p.326-336, June 1988, St. Malo, France [doi>10.1145/55364.55396]
• Rett86: Randall Rettberg , Robert Thomas, Contention is no obstacle to shared-memory multiprocessing, Communications of the ACM, v.29 n.12, p.1202-1212, Dec. 1986 [doi>10.1145/7902.7905]
• Sch87: C. Scheurich , M. Dubois, Correct memory operation of cache-based multiprocessors, Proceedings of the 14th annual international symposium on Computer architecture, p.234-243, June 02-05, 1987, Pittsburgh, Pennsylvania, United States [doi>10.1145/30350.30377]
• Site88: R. L. Sites , A. Agarwal, Multiprocessor cache analysis using ATUM, Proceedings of the 15th Annual International Symposium on Computer architecture, p.186-195, May 30-June 02, 1988, Honolulu, Hawaii, United States
• Smi85: Smith, A.J., "CPU Cache Consistency with Software Support and Using 'One Time 1dentifiers'," Proc. of the Pacific Computer Communications Symposium, October 1985, pp. 142-150.
• Thck88: Charles P. Thacker , Lawrence C. Stewart , Edwin H. Satterthwaite, Jr., Firefly: A Multiprocessor Workstation, IEEE Transactions on Computers, v.37 n.8, p.909-920, August 1988 [doi>10.1109/12.2243]
• Tukr86: Tucker, S.G.,"The H~M 3090 System: An Overview," IBM Sy,~tems Journal, Vol.25, No.l, 1986, pp. 4-19.
• Veid86: Veidenbaum, Alexander V., "A Compiler- Assisted Cache Coherence Solution for Multiprocessors," Proc. of the 1986 Intl. Conf. on Parallel Processing, August 1986, pp. 1029-1036.
• Vern86: Mary K. Vernon , Mark A. Holliday, Performance analysis of multiprocessor cache consistency protocols using generalized timed Petri nets, Proceedings of the 1986 ACM SIGMETRICS joint international conference on Computer performance modelling, measurement and evaluation, p.9-17, May 1986, Raleigh, North Carolina, United States
• Webr89: W. Weber , A. Gupta, Analysis of cache invalidation patterns in multiprocessors, Proceedings of the third international conference on Architectural support for programming languages and operating systems, p.243-256, April 03-06, 1989, Boston, Massachusetts, United States
• Wins87: Winsor, Donald C., Trevor N. Mudge, "Crosspoint Cache Architectures," Proc. of the 1987 intl. Conf. on Parallel Processing, August 1987, pp. 266-269.
• Yenw85: Yen, W.C., D.W.L. Yen, and K.S. Fu, "Data Coherence Problem in a Multicache System," IEEE Transactions on Computers, Vol. C- 34, No.l, January 1985, pp. 56-65.

INDEX TERMS

Primary Classification:
  B. Hardware
  B.3 MEMORY STRUCTURES
      B.3.2 Design Styles
          Subjects: Cache memories

Additional Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.2 Multiple Data Stream Architectures (Multiprocessors)
          Subjects: Interconnection architectures (e.g., common bus, multiport memory, crossbar switch)
  C.2 COMPUTER-COMMUNICATION NETWORKS

  D. Software
  D.4 OPERATING SYSTEMS
      D.4.2 Storage Management
          Subjects: Distributed memories

General Terms:
Algorithms, Design, Performance