GEMM-Based Level 3 BLAS implementations

Autor der Bibliothek:   Per Ling
                        Institute of Information Processing
                        University of Umea
                        S-901 87 Umea, Sweden
                        E-mail: pol@cs.umu.se

Für Standardaufgaben aus dem Bereich Lineare Algebra wurden die BLAS-Routinen (Basic Linear Algebra Subroutines) entwickelt. Level 1 BLAS enthält Routinen für Vektor-Matrix- Operationen, Level 2 Routinen für Matrix-Vektor-Operationen und Level 3 Routinen für Matrix-Matrix-Operationen. Viele Rechnerhersteller stellen hochoptimierte BLAS-Routinen bereit. Durch Verwendung der BLAS-Routinen ist es möglich, portable Programme zu schreiben, die auch auf unterschiedlichen Rechnerarchitekturen optimale Leistungsdaten zeigen.

Einige Level 3 BLAS Routinen lassen sich aus der allgemeinen Matrix*Matrix Multiplikation, GEMM (GEneral Matrix*Matrix Multiplication), und anderen BLAS-Operationen zusammensetzen. Als Beispiel kann hierzu die BLAS Routine STRSM zur Lösung eines triangularen Gleichungssystems dienen:

    A*X = B

wobei X und B mxn Matrizen sind und A eine triangulare Matrix; X ist die gesuchte Lösung des Gleichungssystems. In einer geblockten Form lautet die obige Gleichung etwa:

   +-     -+     +-     -+     +-     -+
   |A11 A12|     |X11 X12|     |B11 B21|
   |       |  *  |       |  =  |       |
   |  0 A22|     |X21 X22|     |B21 B22|
   +-     -+     +-     -+     +-     -+

Das ursprüngliche Problem der Lösung des triangularen Gleichungssystems wird dann umgeformt in Teilaufgaben, die zwar auch die Lösung von triangularen Systemen -- diesmal aber nur für Teilmatrizen -- erfordern, es entstehen aber auch Teilaufgaben, die sich als Matrixmultiplikationen ausdrücken lassen, hier z.B.:

Lösung von A22*X21=B21, wobei B21 mit X21 überschrieben wird (STRSM)
B11 <- B11-A12*B21, Matrixmultiplikation mit SGEMM
Lösung von A11*X11=B11, wobei B11 mit X11 überschrieben wird (STRSM) etc.

The GEMM-Based Level 3 BLAS concept utilizes the fact that it is possible to formulate the Level 3 BLAS operations in terms of the Level 3 operation for general matrix multiply and add, SGEMM, and some Level 1 and Level 2 BLAS operations.

The GEMM-Based Level 3 BLAS model implementations are written in Fortran 77 and designed to be highly efficient on machines with a memory hierarchy. The model implementations consist of five singleprecision Level 3 routines SSYMM, SSYRK, SSYR2K, STRMM, and STRSM and the auxiliary routines SBIGP and SCLD. The auxiliary routines LSAME and XERBLA, from the original Level 3 BLAS are also used. For high performance, the GEMM-Based Level 3 BLAS routines rely on underlying optimized implementations of the Level 3 BLAS routine SGEMM and some Level 1 and Level 2 BLAS routines. The model implementations are primarily intended for single processor use on machines with local or global caches, and micro processors with on-chip caches. However, they can also be parallelized using a parallelizing compiler, or linked with underlying parallel BLAS routines. All routines are structured to reduce data traffic in the memory hierarchy.

The compiler and processor sensitive parts of the operations are concentrated in calls to the underlying BLAS routines. If these are efficiently optimized for the target machine, the GEMM-Based Level 3 BLAS model implementations can offer:

• efficient use of vector instructions (compound instructions, chaining, etc.), through SGEMM, Level 1 and Level 2 BLAS routines.
• vector register reuse, through SGEMM and Level 2 BLAS routines.
• efficient cache reuse, through internal blocking, use of local arrays, and through SGEMM.
• column-wise referencing, for problems with arrays having a leading dimension that could cause sever performance degradation with row-wise referencing (except for reference patterns in underlying BLAS routines).
• parallelism, where the concurrency is explicit through automatic parallelization of the GEMM-Based Level 3 kernels by the compiler, or implicit via use of parallel underlying BLAS kernels.
• an opportunity to conveniently create a Level 3 BLAS library based on unconventional underlying matrix multiply algorithms like, for example, Strassens or Winograds algorithms.

For further information see:

• Dongarra J. J., DuCroz J., Duff I., and Hammarling S., "A Set of Level 3 Basic Linear Algebra Subprograms", ACM Trans. Math. Softw., Vol. 16, No. 1, 1990, pp.1-17.
• Dongarra J. J., DuCroz J., Duff I., and Hammarling S., "Algorithm 679: A Set of Level 3 Basic Linear Algebra Subprograms: Model Implementation and Test Programs", ACM Trans. Math. Softw., Vol. 16, No. 1, 1990, pp.18-28.
• Kagstrom B. and Van Loan C. "GEMM-Based Level-3 BLAS", Tech. rep. CTC91TR47, Department of Computer Science, Cornell University, Dec. 1989.
• Kagstrom B., Ling P. and Van Loan C. "High Performance GEMM-Based Level-3 BLAS: Sample Routines for Double Precision Real Data", in High Performance Computing II, Durand M. and El Dabaghi F., eds., Amsterdam, 1991, North-Holland, pp.269-281.
• Kagstrom B., Ling P. and Van Loan C. "Portable High Performance GEMM-Based Level-3 BLAS", in R. F. Sincovec et al, eds., Parallel Processing for Scientific Computing, SIAM Publications, 1993.

Obwohl die BLAS Level 3 Routinen in der CRAY-Bibliothek libsci selbst schon sehr gut optimiert sind, läßt sich in manchen Fllen durch die Verwendung der hier aufgezeigten Algorithmen eine bis zu 70%-ige Performancesteigerung erreichen. Es hängt jedoch sehr von der konkreten Dimensionierung der Matrizen und der Aufgabenstellung ab, ob die libsci-Routinen oder die GEMM-basierenden Routinen bessere Leistungsdaten zeigen. Folgende GEMM-basierende Routinen stehen an den Crays in der Bibliothek libgemmbased bereit: SSYMM, SSYRK, SSYR2K, STRMM, STRSM. Identische Routinen nur mit anderen Namen (GSSYMM, GSTRSM etc.) stehen in libGEMMbased. Dadurch kann der Benutzer selbst entscheiden, ob er die Routinen aus libsci überladen will oder die GEMMbasierenden Routinen parallel hierzu verwenden will. Auf die Bibliotheken kann etwa wie folgt zugegriffen werden:

Die Quellen befinden sich unter:

Sie können auch für andere Rechner, an denen hochoptimierte GEMM-Routinen bereitstehen, verwendet werden. Näheres zur Funktionalität der Routinen erhält man mit: man SSYMM etc.

Beratung

Mit Fragen zu den GEMM-basierenden Routinen wenden Sie sich bitte an: Dr. Matthias Brehm, Zi. 25126, Tel: (089) 289-28773