A benchmark package for sparse matrix computations

ABSTRACT

We examine the problem of evaluating performance of supercomputer architectures on sparse (matrix) computations and lay out the details of a benchmark package for this problem. Whereas there already exists a number of benchmark packages for scientific computations, such as the Livermore Loops, the Linpack benchmark and the Los Alamos benchmark, none of these deals with the specific nature of sparse computations. Sparse matrix techniques are characterized by the relatively small number of operations per data element and the irregularity of the computation. Both facts may significantly increase the overhead time due to memory traffic. For this reason, the performance evaluation of sparse computations should not only take into account the CPU performance but also the degradation of performance caused by high memory traffic. Furthermore, sparse matrix techniques comprise a variety of different types of basic computations. Taking these considerations into account we propose a benchmark package that consists of several independent modules, each of which has a distinct role.

REFERENCES

• 1: W. Abu-Sufah and Allen Malony, Ezperimental Reaults for Vector Processing on the Alliant FX/8 , CSRD report 539, University of Illinois at Urbana Champaign, 1986.
• 2: E. Ande, son and Y. Saad, Sol~in9 ~riangular sy&tema on parallel computers, CSRD Report, In preparation.
• 3: David S. Dodson , John G. Lewis, Proposed sparse extensions to the Basic Linear Algebra Subprograms, ACM SIGNUM Newsletter, v.20 n.1, p.22-25, January 1985 [doi>10.1145/1057935.1057938]
• 4: :i.J. Dongarra, Performance of various computere using standard linear equation8 aoflware in a FORTRAN environment, Argonne National Lab. report, MCS-TM 23 (1986).
• 5: Iain S Duff , Albert M Erisman , John K Reid, Direct methods for sparse matrices, Oxford University Press, Inc., New York, NY, 1986
• 6: Iain Duff , Roger Grimes , John Lewis , Bill Poole, Sparse matrix test problems, ACM SIGNUM Newsletter, v.17 n.2, p.22-22, June 1982 [doi>10.1145/1057588.1057590]
• 7: Kyle Gallivam , William Jalby , Ulrike Meier, The use of BLAS3 in linear algebra on a parallel processor with a hierarchical memory, SIAM Journal on Scientific and Statistical Computing, v.8 n.6, p.1079-1084, November 1, 1987 [doi>10.1137/0908086]
• 8: Alan George , Joseph W. Liu, Computer Solution of Large Sparse Positive Definite, Prentice Hall Professional Technical Reference, 1981
• 9: J.H. Griffin and M.L. Simmons, Los Alamos National Laboratory Computer B enchmarking 1983. Tech. Report LA 10151-MS, Los Alamos National Lab., June 1984.
• 10: D.J. Kuck, E.S. Davidson, D.H. Lawrie and A. H. Sameh, Parallel Supercomputing Today and the Cedar Approach , Science, vol. 231, pp. 967- 974, Feb. 1986.
• 11: F.H. McMahon, The I, ivermore Fortran Kernels: A computer Test of the IV~merical Performance Range, Tech. Rep. UCRL-53745, Lawrence Livermore National Laboratory, Livezmore CA., (1986).
• 12: H.A. Voz,t, (M)ICCG yo, problems on vector computerJ, Pzoceedings of Inteznational seminar on scientific supercomputers, INRIA, Paris Feb 2-6, 1987, pp. 281-294.
• 13: P.T. Woo and John M. Levesque, Benchmarking a sparse elimination routine on the Cyber 205 and the CRAY.1, SPE paper 10526, Society of Petroleum Engineers, pp. 535-538 (1982).

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.3 Numerical Linear Algebra
          Subjects: Sparse, structured, and very large systems (direct and iterative methods)

Additional Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.2 Multiple Data Stream Architectures (Multiprocessors)
          Subjects: Parallel processors**
  C.5 COMPUTER SYSTEM IMPLEMENTATION
      C.5.1 Large and Medium ("Mainframe") Computers
          Subjects: Super (very large) computers

  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, Measurement, Performance, Theory