Multiprocessor cache design considerations

ABSTRACT

In this paper, cache design is explored for large high-performance multiprocessors with hundreds or thousands of processors and memory modules interconnected by a pipe-lined multi-stage network. The majority of the multiprocessor cache studies in the literature exclusively focus on the issue of cache coherence enforcement. However, there are other characteristics unique to such multiprocessors which create an environment for cache performance that is very different from that of many uniprocessors. Multiprocessor conditions are identified and modeled, including, 1) the cost of a cache coherence enforcement scheme, 2) the effect of a high degree of overlap between cache miss services, 3) the cost of a pin limited data path between shared memory and caches, 4) the effect of a high degree of data prefetching, 5) the program behavior of a scientific workload as represented by 23 numerical subroutines, and 6) the parallel execution of programs. This model is used to show that the cache miss ratio is not a suitable performance measure in the multiprocessors of interest and to show that the optimal cache block size in such multiprocessors is much smaller than in many uniprocessors.

REFERENCES

• AbKL79: W. Abu-Sufah, D. J. Kuck, and D. H. Lawrie, "Automatic Program Transformations for Virtual Memory Computers," Proc. of the 1979 National Computer Conf., pp. 989-974, June 1979
• AbLM84: W. Abu-Sufah, R. L. Lee, and M. Malkawi, "Identifying Two Program Categories for Memory Management Purposes," Proc. of the 8th International Computer Software and Applicationt Conference, November 1984.
• ArBa84: 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
• CeFe78: L. M. Censier and P. Feautrier, "A New Solution to Coherence Problems in Multicache Systems," IEEE Trans. on Computers, Vol. C-27, No. 12, pp. 1112- 1118, December 1978.
• Clar83: Douglas W. Clark, Cache Performance in the VAX-11/780, ACM Transactions on Computer Systems (TOCS), v.1 n.1, p.24-37, Feb. 1983 [doi>10.1145/357353.357356]
• DuBr82: M. Dubols and F. A. Briggs, "Effects of Cache Coherency in Multlproeessors," IEEE Trans. on Computers, Vol. C-31, No. 11, pp. 1083-1099, November 1982.
• Elsf74: J. L. Elshoff, "Some Programming Techniques for Processing Multi-Dimensional Matrices in a Paging Environment," Proceedings of the National Computer Conference, pp. 185-193, 1974.
• FrWT82: M. A. Franklin, D. F. Wann, and W. J. Thomas, "Pin Limitations and Partitioning of VLSI Interconnection Networks," IEEE Trans. on Computers, Vol. C-31, No. 11, pp. 1109-1116, November 1982.
• GGKM83: A. Gottlieb, R. Grishman, C. Kruskal, K. McAuliffe, L. Rudolph, and M. Snir, "The NYU Ultracomputer - Designing a MIMD, Shared Memory Parallel Machine," IEEE Trans. on Computers, Vol. C-32, No. 2, pp. 175-189, February 1983.
• GKLS83: D. Gajski, D. Kuck, D. Lawrie, and A. Sameh, "CEDAR - A Large Scale Multiproeessor," Pros. of the 1983 International Conf. on Parallel Processing, pp. 524-529, August 1983.
• Good83: James R. Goodman, Using cache memory to reduce processor-memory traffic, Proceedings of the 10th annual international symposium on Computer architecture, p.124-131, June 13-17, 1983, Stockholm, Sweden
• HiSm84: Mark D. Hill , Alan Jay Smith, Experimental evaluation of on-chip microprocessor cache memories, Proceedings of the 11th annual international symposium on Computer architecture, p.158-166, January 1984
• Husm86: Harlan Edward Husmann, Compiler memory management and compound function definition for multiprocessors, 1986
• KaWi73: K. R. Kaplan and R. O. Winder, "Cache-based Computer Systems," Computer, Vol. 6, No. 3, pp. 30-36, March 1973.
• KDLS86: D. J. Kuck, E. S. Davidson, D. H. Lawrie, and A. H. Sameh, "Parallel Supercomputlng Today and the Cedar Approach," Selenee, Vol. 231, pp. 967-974, February 28, 1986.
• Krof81: David Kroft, Lockup-free instruction fetch/prefetch cache organization, Proceedings of the 8th annual symposium on Computer Architecture, p.81-87, May 12-14, 1981, Minneapolis, Minnesota, United States
• Lawr75: D. H. Lawrie, "Access and Alignment of Data in an Array Processor," IEEE Trans. on Computers, Vol. C-24, No. 12, pp. 1145-1155, December 1975.
• Lee87: R. L. Lee, Ph.D. Thesis in preparation. Center for Supercomputing Research and Development, University of Illinois at Urbana-Champaign, 1987.
• LeYL87: R. L. Lee, P-C Yew and D. H. Lawrie, "Data Prefetching in Shared Memory Multiprocessors," to appear in, Proc. of the 1987 International Conf. on Parallel Processing, 1987.
• NoAb82: R. L. Norton and J. A. Abraham, "Using Write Back Cache to Improve Performance of Multiuser Multiprocessors," Proc. of the 1982 International Conf. on Parallel Processing, pp. 326-331, 1982.
• PaPa84: Mark S. Papamarcos , Janak H. Patel, A low-overhead coherence solution for multiprocessors with private cache memories, Proceedings of the 11th annual international symposium on Computer architecture, p.348-354, January 1984
• PBGH85: Samson Abramsky, Introduction, Proceedings of the Tutorial and Workshop on Category Theory and Computer Programming, p.3-6, September 16-20, 1985
• RuSe84: Larry Rudolph , Zary Segall, Dynamic decentralized cache schemes for mimd parallel processors, Proceedings of the 11th annual international symposium on Computer architecture, p.340-347, January 1984
• SmGo83: James E. Smith , James R. Goodman, A study of instruction cache organizations and replacement policies, Proceedings of the 10th annual international symposium on Computer architecture, p.132-137, June 13-17, 1983, Stockholm, Sweden
• Smit82: Alan Jay Smith, Cache Memories, ACM Computing Surveys (CSUR), v.14 n.3, p.473-530, Sept. 1982 [doi>10.1145/356887.356892]
• Smit85: Alan Jay Smith, Cache evaluation and the impact of workload choice, Proceedings of the 12th annual international symposium on Computer architecture, p.64-73, June 17-19, 1985, Boston, Massachusetts, United States
• Tang76: C. K. Tang, "Cache System Design in the Tightly Coupled Multiprocessor System," AFIPS Proc., National Computer Conference, Vol. 45, pp. 749- 753, 1976.
• Widd80: L. C. Widdoes, "The S-1 Project: Development of High-Performance Digital Computers," IEEE COMPCON 1980 pp. 282-291, 1980.
• Wolf78: M. J. Wolfe, "Techniques for Improving the Inherent Parallelism in Programs," M.S. Thesis, Tech. Rep. UIUCDCS-R-78-929, Dept. of Computer Science, University of Illinois at Urbana-Champaign, July 1978.
• YePD83: P. C. Yeh, J. H. Patel and E. S. Davidson, "Shared Cache for Multiple-Stream Computer Systems," IEEE Trans. on Computers, Vol. C-32, No. 1, pp. 38-47, January 1983.
• YeYF85: W. C. Yen, D. W. L Yen, and K. S. Fu, "Data Coherence Problem in a Multi,ache System," IEEE Trans. on Computers, Vol. C-34, No. 1, pp. 56-65, January 1985.

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

General Terms:
Design, Measurement, Performance