Analysis of critical architectural and programming parameters in a hierarchical

ABSTRACT

Scalable shared-memory multiprocessors are the subject of much current research, but little is known about the performance behavior of these machines. This paper studies the performance effects of two machine characteristics and two program characteristics that seem to be major factors in determining the performance of a hierarchical shared-memory machine. We develop an analytical model of the traffic in a machine loosely based on Stanford's DASH multiprocessor and use program parameters extracted from multiprocessor traces to study its performance. It is shown that both locality in the data reference stream and the amount of data sharing in a program have an important impact on performance. Although less obvious, the bandwidth within each cluster in the hierarchy also has a significant performance effect. Optimizations that improve the intracluster cache coherence protocol or increase the bandwidth within a cluster can be quite effective.

REFERENCES

• 1: 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
• 2: L.M. Censier and E Feautrier. A New Solution to Coherence Problems in Multicache Systems. In IEEE Trans. on Computers, pages 1112- 1118, December 1978.
• 3: S. J. Eggers , R. H. Katz, The effect of sharing on the cache and bus performance of parallel programs, Proceedings of the third international conference on Architectural support for programming languages and operating systems, p.257-270, April 03-06, 1989, Boston, Massachusetts, United States
• 4: 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
• 5: A. Gottlieb, R. Grishman, C. Kruskal, K. MeAuliffe, L. Rudolph, and M. Snir. The NYU Ultracomputer - Designing an MIMD Shared Memory Parallel Computer. In IEEE Trans. on Computers, pages 175- 189, February 1983.
• 6: T. Joe. Simulation Analysis for the Parameter Sensitivity of a Hybrid Interconnect Scheme for a Multiprocessor System. EE390 Report, Stanford University, May 1988.
• 7: Leonard Kleinrock, Theory, Volume 1, Queueing Systems, Wiley-Interscience, 1975
• 8: Edward D. Lazowska , John Zahorjan , G. Scott Graham , Kenneth C. Sevcik, Quantitative system performance: computer system analysis using queueing network models, Prentice-Hall, Inc., Upper Saddle River, NJ, 1984
• 9: D. Lenoski, K. Gharachorloo, J. Laudon, A. Gupta, J. Hennessy, M. Horowitz, and M. Lam. Design of Scalable Shared-Memory Multiprocessors: The DASH Approach. In Procee&'ngs of the 35th IEEE Computer Society International Conference - COMPCON 90, 1990, to appear.
• 10: D. Lenoski, J. Laudon, K. Gharachorloo, A. Gupta, and J. Hennessy. The Directory-Based Cache Coherence Protocol for the DASH Multiprocessor. Technical Report CSL-TR-89-404, Stanford University, December 1989.
• 11: S. T. Leutenegger , M. K. Vernon, A mean-value performance analysis of a new multiprocessor architecture, Proceedings of the 1988 ACM SIGMETRICS conference on Measurement and modeling of computer systems, p.167-176, May 24-27, 1988, Santa Fe, New Mexico, United States
• 12: M. Ajmone Marsan , G. Balbo , G. Conte, Performance models of multiprocessor systems, MIT Press, Cambridge, MA, 1987
• 13: H. E. Mizrahi, J. L. Baer, E. D. Lazowska, andJ. Zahorjan. Extending the Memory Hierarchy into Multiprocessor Interconnection Networks: A Performance Analysis. In Proceedings of the 1989 International Conference on Parallel Processing, volume I, pages 41-50, August 1989.
• 14: A. Norton and G. F. Pfister. A Methodology for Predicting Multiprocessor Performance. In Proceedings of the 1985 International Confer. ence on Parallel Processing, pages 772-781, 1985.
• 15: G. Pfister, W. Brantley, D. George, S. Harvey, W. Kleinfelder, K. McAuliffe, E. Melton, A. Norton, and J. Weiss. The IBM Research Parallel Processor Prototype (RP3): Introduction and Architecture. In Proceedings of the 1985 International Conference on Parallel Processing, pages 764--771, 1985.
• 16: R. Simoni. Implementing a Directory-Based Cache Consistency Protocol. Unpublished report, July 1988.
• 17: J. Torrellas, T. Weil, and J. Hennessy. A Methodology for Modeling Interprocessor Traffic in Shared Memory Multiprocessors. Stanford University Technical Report No. CSL-TR-89-385, July 1989.
• 18: Kishar Shridharbhai Trivedi, Probability and Statistics with Reliability, Queuing and Computer Science Applications, Prentice Hall PTR, Upper Saddle River, NJ, 1982
• 19: W. Whitt. The Queueing Network Analyzer. In The BELL System Technical Journal, volume 62, N.9, November 1983.
• 20: A. W. Wilson, Jr., Hierarchical cache/bus architecture for shared memory multiprocessors, Proceedings of the 14th annual international symposium on Computer architecture, p.244-252, June 02-05, 1987, Pittsburgh, Pennsylvania, United States [doi>10.1145/30350.30378]

INDEX TERMS

Primary Classification:
  B. Hardware
  B.3 MEMORY STRUCTURES
      B.3.2 Design Styles
          Subjects: Shared memory

Additional Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Performance attributes; Modeling techniques

General Terms:
Design, Performance