Evaluating the communication performance of MPPs using synthetic sparse matrix multiplication workloads

ABSTRACT

Communication has a dominant impact on the performance of massively parallel processors (MPPs). We propose a methodology to evaluate the internode communication performance of MPPs using a controlled set of synthetic workloads. By generating a range of sparse matrices and measuring the performance of a simple parallel algorithm that repeatedly multiplies a sparse matrix by a dense vector, we can determine the relative performance of different communication workloads. Specifiable communication parameters include the number of nodes, the average amount of communication per node, the degree of sharing among the nodes, and the computation-communication ratio. We describe a general procedure for constructing sparse matrices that have these desired communication and computation parameters, and apply a range of these synthetic workloads to evaluate the hierarchical ring interconnection and cache-only memory architecture (COMA) of the Kendall Square Research KSRI MPP. This analysis discusses the impact of the KSRI architecture on communication performance, highlighting the utility and impact of the automatic update feature. It also investigates the impact of system contention on the performance, particularly how it causes potential updates to be ignored.

REFERENCES

• 1: "KSR1 Principles of Operation, Kendall Square Research Corporation," Waltham, MA, 1991
• 2: "Inside the TC2000 Computer," BBN Advanced Computers Inc., Cambridge, MA 02138, 1990
• 3: "Paragon XP/S Product Overview," Intel Corporation, Hillsboro, OR, 1991.
• 4: "The Connection Machine CM5 Technical Summary," Thinking Machines Corporation, Cambridge, MA, January, 1992.
• 5: Erik Hagersten , Anders Landin , Seif Haridi, DDM: A Cache-Only Memory Architecture, Computer, v.25 n.9, p.44-54, September 1992 [doi>10.1109/2.156381]
• 6: V. E. Taylor, Sparse matrix computations: implications for cache designs, Proceedings of the 1992 ACM/IEEE conference on Supercomputing, p.598-607, November 16-20, 1992, Minneapolis, Minnesota, United States
• 7: K. Gallivan and D. Gannon and W. Jalby and A. Malony and H. Wijshoff 'Behavioral Characterization of Multiprocessor Memory Systems: A Case Study," University of Illinois at Urbana-Champaign, 1988, No. 808.
• 8: François Bodin , Daniel Windheiser , William Jalby , Daya Atapattu , Mannho Lee , Dennis Gannon, Performance evaluation and prediction for parallel algorithms on the BBN GP1000, Proceedings of the 4th international conference on Supercomputing, p.401-413, June 11-15, 1990, Amsterdam, The Netherlands
• 9: Anoop Gupta , Wolf-Dietrich Weber, Cache Invalidation Patterns in Shared-Memory Multiprocessors, IEEE Transactions on Computers, v.41 n.7, p.794-810, July 1992 [doi>10.1109/12.256449]
• 10: Xiaodong Zhang , Xiaohan Qin, Performance Prediction and Evaluation of Parallel Processing on a NUMA Multiprocessor, IEEE Transactions on Software Engineering, v.17 n.10, p.1059-1068, October 1991 [doi>10.1109/32.99193]
• 11: A. Nanda and L. M. Ni. "MAD kernels: An experimental testbed to study multiprocessor memory system behavior," Int. Conf Parallel Processing, Vol. 1, 1992, pp. 28-35.
• 12: A. Nanda , L. M. Ni, Benchmark workload generation and performance characterization of multiprocessors, Proceedings of the 1992 ACM/IEEE conference on Supercomputing, p.20-29, November 16-20, 1992, Minneapolis, Minnesota, United States
• 13: D.Windheiser,E.L. Boyd, E. Hao, S. G. Abraham, E. S. Davidson. "KSR1 multiprocessor: Analysis of latency hiding techniques in a sparse solver," Int. ParaHd Processing Symposium, April 1993
• 14: T H. Dunigan. "Kendall Square Multiprocessor: Early experiences and performance," Oak Ridge National Laboratory Technical Report ORNL/TM- 12065, April 1992.
• 15: E. Rosti , E. Smirni , T. D. Wagner , A. W. Apon , L. W. Dowdy, The KSR1: experimentation and modeling of poststore, Proceedings of the 1993 ACM SIGMETRICS conference on Measurement and modeling of computer systems, p.74-85, May 10-14, 1993, Santa Clara, California, United States
• 16: 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
• 17: B. Kahhaleh, "Analysis of Memory Latency Factors and their Impact on KSR1 MPP Performance, University of Michigan, Technical Repot, CSE-TR-157- 93, 1993.
• 18: Todd Mowry , Anoop Gupta, Tolerating latency through software-controlled prefetching in shared-memory multiprocessors, Journal of Parallel and Distributed Computing, v.12 n.2, p.87-106, June 1991 [doi>10.1016/0743-7315(91)90014-Z]
• 19: M. Dubois , C. Scheurich , F. Briggs, Memory access buffering in multiprocessors, Proceedings of the 13th annual international symposium on Computer architecture, p.434-442, June 02-05, 1986, Tokyo, Japan
• 20: H. P Flatt and K. Kennedy "Performance of Parallel Processor,'" Parallel Computing, Vol. 12, No. 1, pp. 1-12, 1989.
• 21: Alan H. Karp , Horace P. Flatt, Measuring parallel processor performance, Communications of the ACM, v.33 n.5, p.539-543, May 1990 [doi>10.1145/78607.78614]
• 22: P R LaRowe , S C Ellis, Experimental Comparison of Memory Management Policies for NUMA Multiprocessors, Duke University, Durham, NC, 1990
• 23: Xiaodong Zhang, Performance Measurement and Modeling to Evaluate Various Effects on a Shared memory Multiprocessor, IEEE Transactions on Software Engineering, v.17 n.1, p.87-93, January 1991 [doi>10.1109/32.67581]
• 24: X. Zhang and P. Srinivasan, "Distributed Task Processing and Performance on a NUMA Shared Memory Mulfiprocessor," Proceedings of the 2nd IEEE Symposium on Parallel and Distributed Processing, Los Alamitos, CA, pp. 786-789, 1990.

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: Parallel processors**
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Performance attributes

  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems
          Subjects: Computations on matrices

General Terms:
Algorithms, Design, Performance