Compiler and hardware support for cache coherence in large-scale multiprocessors: design considerations and performance study

ABSTRACT

In this paper, we study a hardware-supported, compiler directed (HSCD) cache coherence scheme, which can be implemented on a large-scale multiprocessor using off-the-shelf microprocessors, such as the Cray T3D. It can be adapted to various cache organizations, including multi-word cache lines and byte-addressable architectures. Several system related issues, including critical sections, inter-thread communication, and task migration have also been addressed. The cost of the required hardware support is small and proportional to the cache size. The necessary compiler algorithms, including intra- and interprocedural array data-flow analysis, have been implemented on the Polaris compiler [17].From our simulation study using the Perfect Club benchmarks, we found that, in spite of the conservative analysis made by the compiler, the performance of the proposed HSCD scheme can be comparable to that of a full-map hardware directory scheme. With its comparable performance and reduced hardware cost, the scheme can be a viable alternative for large-scale multiprocessors, such as the Cray T3D, that rely on users to maintain data coherence.

REFERENCES

• 1: Sarita V. Adve , Vikram S. Adve , Mark D. Hill , Mary K. Vernon, Comparison of hardware and software cache coherence schemes, Proceedings of the 18th annual international symposium on Computer architecture, p.298-308, May 27-30, 1991, Toronto, Ontario, Canada
• 2: Karl J. Ottenstein , Robert A. Ballance , Arthur B. MacCabe, The program dependence web: a representation supporting control-, data-, and demand-driven interpretation of imperative languages, Proceedings of the ACM SIGPLAN 1990 conference on Programming language design and implementation, p.257-271, June 1990, White Plains, New York, United States
• 3: L. M. Censier and P. Feautrier. A New Solution to Coherence Problems in Multicache Systems. IEEE Transactions on Computers, C-27(12):1112-1118, December, 1978.
• 4: Yung-Chin Chen. Cache Design and Performance in a Large-Scale Shared-Memory Multiprocessor System. Technical report, Univ. of Illinois, Dept. of Elec. Eng., 1993. Ph.D. Thesis.
• 5: Hoichi Cheong, Life span strategy—a compiler-based approach to cache coherence, Proceedings of the 6th international conference on Supercomputing, p.139-148, July 19-24, 1992, Washington, D. C., United States [doi>10.1145/143369.143402]
• 6: 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]
• 7: T. Chiueh. A Generational Approach to Software- Controlled Multiprocessor Cache Coherence. Proceedings of the 1993 International Conference on Parallel Processing, August 1993.
• 8: Lynn Choi , Pen-Chung Yew, Hardware and compiler support for cache coherence in large-scale shared-memory multiprocessors, 1996
• 9: Lynn Choi , Pen-Chung Yew, A compiler-directed cache coherence scheme with improved intertask locality, Proceedings of the 1994 conference on Supercomputing, p.773-782, December 1994, Washington, D.C., United States
• 10: Digital Equipment Corp. Alpha 21164 Microprocessor: Hardware Reference Manual. 1994.
• 11: E. Darnell , K. Kennedy, Cache coherence using local knowledge, Proceedings of the 1993 ACM/IEEE conference on Supercomputing, p.720-729, December 1993, Portland, Oregon, United States [doi>10.1145/169627.169821]
• 12: Czarek Dubnicki , Thomas J. LeBlanc, Adjustable block size coherent caches, Proceedings of the 19th annual international symposium on Computer architecture, p.170-180, May 19-21, 1992, Queensland, Australia
• 13: C. P. Kruskal and M. Snir. The Performance of Multistage Interconnection Networks for Multiprocessors. IEEE Transactions on Computers, C-32(12):1091- 1098, Sept., 1987.
• 14: David J. Lilja, Cache coherence in large-scale shared-memory multiprocessors: issues and comparisons, ACM Computing Surveys (CSUR), v.25 n.3, p.303-338, Sept. 1993 [doi>10.1145/158439.158907]
• 15: S. L. Min , J. L. Baer, Design and Analysis of a Scalable Cache Coherence Scheme Based on Clocks and Timestamps, IEEE Transactions on Parallel and Distributed Systems, v.3 n.1, p.25-44, January 1992 [doi>10.1109/71.113080]
• 16: J. M. Mulder, N. T. Quach, and M. J. Flynn. An area model for on-chip memories and its application. Journal of Solid State Circuits, 26:98-106, Feb. 1991.
• 17: D. A. Padua, R. Eigenmann, J. Hoeflinger, P. Peterson, P. Tu, S. Weatherford, and K. Faign. Polaris: A New-Generation Parallelizing Compiler for MPPs. In CSRD Rept. No. 1306. Univ. of Illinois at Urbana- Champaign., June, 1993.
• 18: D. K. Poulsen , P.-C. Yew, Execution-driven tools for parallel simulation of parallel architectures and applications, Proceedings of the 1993 ACM/IEEE conference on Supercomputing, p.860-869, December 1993, Portland, Oregon, United States [doi>10.1145/169627.169852]
• 19: J. Torrellas , H. S. Lam , J. L. Hennessy, False Sharing and Spatial Locality in Multiprocessor Caches, IEEE Transactions on Computers, v.43 n.6, p.651-663, June 1994 [doi>10.1109/12.286299]
• 20: Dean M. Tullsen , Susan J. Eggers, Limitations of cache prefetching on a bus-based multiprocessor, Proceedings of the 20th annual international symposium on Computer architecture, p.278-288, May 16-19, 1993, San Diego, California, United States
• 21: A. V. Veidenbaum. A Comp~r-Assisted Cache Coherence Solution for Multiprocessors. Proceedings of the 1986 International Conference on Parallel Processing, pages 1029-1035, August 1986.
• 22: Hong Wang , Tong Sun , Qing Yang, CAT—caching address tags: a technique for reducing area cost of on-chip caches, Proceedings of the 22nd annual international symposium on Computer architecture, p.381-390, June 22-24, 1995, S. Margherita Ligure, Italy

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
        I.2.11 Distributed Artificial Intelligence
            Subjects: Coherence and coordination

Additional Classification:
  B. Hardware
  B.2 ARITHMETIC AND LOGIC STRUCTURES
      B.2.2 Performance Analysis and Design Aids**
          Subjects: Simulation**
  B.3 MEMORY STRUCTURES
      B.3.2 Design Styles
          Subjects: Cache memories

  D. Software
  D.4 OPERATING SYSTEMS

  I. Computing Methodologies
  I.6 SIMULATION AND MODELING

General Terms:
Design, Experimentation, Measurement, Performance, Verification