SC 740 Presentation Review

By Deborah Dent

"High Performance Solutions of Linear System"

Presented by

Dr. Marcin Paprzycki

Professor of Computer Science

University of Southern Mississippi

September 3, 1997

Dr. Paprzycki presented information on high performance solutions of linear systems, which was based from a paper written by Dr. Paprzycki, "Comparisons of Gaussian Elimination Algorithms on a Cray Y-MP". In scientific computing, one is often confronted with the solution of a system of linear equations

where A is an N x N dense matrix. Dr. Paprzycki's presentation was based on using the Gaussian elimination with partial pivoting for the solution of this system. He first discussed issues concerning implementation of operations and pointed out why the methods of implementation of algorithms are very important in achieving the highest performance. He then introduced to some and presented to others the BLAS (Basic Linear Algebra Subprogram) standard subroutine library, which is a set of standard FORTRAN routines available on many platforms. These standard subroutines were introduced for general use around 1973 or 1977 and have been since undergoing enhancements. Some of the basic operation provided by BLAS includes:

• Dot Product
• Scaling
• Axpy
• Norms
• I-Max

BLAS features include:

• portability of code
• performance as good as the vendor provided libraries

Some of the vendors who provide BLAS on their systems are Digital, HP, SGI, IBM and Cray. The information presented in this talk is based on Cray's implementation of the BLAS code. It was originally written in FORTRAN but has been updated to assure the best optimization and performance. Cray, along with other vendors, has replaced parts of the FORTRAN code with assembly code.

Level 2 BLAS utilizes an unblocked (Matrix-Vector) implementation and Level 3 utilizes a blocked (Matrix-Matrix) implementation. Dr. Paprzycki's research utilized Level 2 and Level 3 BLAS on the Cray Y-MP and performed a comparison of the performance of the blocked and unblocked versions of three of six possible versions of Gaussian elimination: DOT, GAXPY and SAXPY.

The main emphasis of this talk was Dr. Paprzycki's presentation on block algorithms. He presented details on the decomposition of the block columns for each method, the DOT version that is a variation of Crout's decomposition, followed by the GAXPY variant and concluded with the SAXPY variant.

In conclusion, Dr. Paprzycki's research revealed that, due to the assembly code implementation of the BLAS routines provided by Cray, there is very little difference in the performance of the blocked and unblocked versions of the Gaussian elimination routines used. In his paper, this research also revealed that the matrix multiplication routine used makes a performance difference. Depending on the size, Strassen's matrix multiplication improves the performance of large matrices.