Automatic software cache coherence through vectorization

ABSTRACT

Access latency in large-scale shared-memory multiprocessors is a concern since most (if not all) memory is one or more hops away through an interconnection network. Providing processors with one or more levels of cache is an accepted way to reduce the average access latency; however, in a multiprocessor, cached values must be kept coherent for the multiprocessor to support the abstraction of a shared global memory. There is no generally accepted hardware solution to provde cache coherence for large-scale shared-memory multiprocessors. Software coherence strategies offer scalability with current hardware. In this paper we examine a compiler-based software strategy for maintaining cache coherence that relies on dependence analysis and a vectorization algorithm to insert cache control directives. Experiments on the BBN TC2000 for a pair of numerical problems show that the run-time cost of coherence using our strategy is less than that for previously proposed compiler-based software methods and suggest that it should compare favorably with proposed hardware schemes.

REFERENCES

• 1: Randy Allen , Ken Kennedy, Automatic translation of FORTRAN programs to vector form, ACM Transactions on Programming Languages and Systems (TOPLAS), v.9 n.4, p.491-542, Oct. 1987 [doi>10.1145/29873.29875]
• 2: Robert Alverson , David Callahan , Daniel Cummings , Brian Koblenz , Allan Porterfield , Burton Smith, The Tera computer system, Proceedings of the 4th international conference on Supercomputing, p.1-6, June 11-15, 1990, Amsterdam, The Netherlands
• 3: L. M. Censier and P. Feautrier. A new solution to coherence problems in multicache systems. IEEE Transavtion~ oi~ Computers, C-27(12);1112-1118, Dec. 1978.
• 4: Hoichi Cheong , Alexander V. Viedenbaum, Compiler-Directed Cache Management in Multiprocessors, Computer, v.23 n.6, p.39-47, June 1990 [doi>10.1109/2.55499]
• 5: R. Cytron, S. Karlovsky, and K. McAuliffe. Automatic management of programmable caches. IlL Proc. of the 1988 International Conference on Parallel Processing, pages 229-238, ?, Aug. 1988.
• 6: E. Darnell, J. M. Mellor-Crummcy, and K. Kennedy. Automatic software cache coherence through vectorizat.ion. Technical Report CRPC-TR92197, Computer Science Department, Rice University, Jan. 1992.
• 7: Jack J. Dongarra , Iain S. Duff , Danny C. Sorensen , Henk Van Der Vorst, Solving Linear Systems on Vector and Shared Memory Computers, Society for Industrial and Applied Mathematics, Philadelphia, PA, 1990
• 8: David L. Kuck, Structure of Computers and Computations, John Wiley & Sons, Inc., New York, NY, 1978
• 9: D. J. Kuck , R. H. Kuhn , D. A. Padua , B. Leasure , M. Wolfe, Dependence graphs and compiler optimizations, Proceedings of the 8th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.207-218, January 26-28, 1981, Williamsburg, Virginia [doi>10.1145/567532.567555]
• 10: L. Lamport. How to make a multiprocessor that correctly executes multiprocess programs. IEEE Transactions on Computers, C-28(9), Sept. 1979.
• 11: Daniel Lenoski , James Laudon , Kourosh Gharachorloo , Anoop Gupta , John Hennessy, The directory-based cache coherence protocol for the DASH multiprocessor, ACM SIGARCH Computer Architecture News, v.18 n.3a, p.148-159, June 1990
• 12: S. Min and J. B~er. A timestamp-based c~che coherence scheme. In Proc. of the 1989 International Con- }emnce on Parallel Processing, volume 1, pages 23-32, Aug. 1989.
• 13: Sang Lyul Min , Jean-Loup Baer , Hyoung-Joo Kim, An efficient caching support for critical sections in large-scale shared-memory multiprocessors, Proceedings of the 4th international conference on Supercomputing, p.34-47, June 11-15, 1990, Amsterdam, The Netherlands
• 14: Anita Osterhaug, Guide to parallel programming on Sequent computer systems: 2nd edition, Prentice-Hall, Inc., Upper Saddle River, NJ, 1989
• 15: Par,'dlel Computing Forum. PCF Fortran, Mar. 1990. Working Draft.
• 16: David J. Schanin, The design and development of a very high speed system bus—the encore Mutlimax nanobus, Proceedings of 1986 ACM Fall joint computer conference, p.410-418, November 1986, Dallas, Texas, United States
• 17: John C. Willis , Arthur C. Sanderson , Charles R. Hill, Cache coherence in systems with parallel communication channels & many processors, Proceedings of the 1990 conference on Supercomputing, p.554-563, October 1990, New York, New York, United States

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.5 COMPUTER SYSTEM IMPLEMENTATION
      C.5.1 Large and Medium ("Mainframe") Computers
          Subjects: Super (very large) computers

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)

  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Compilers

General Terms:
Design, Experimentation, Performance