LAWRA
Workshop
at
May 8th - 10th, 2000
Amsterdam, The Netherlands
http://www.wins.uva.nl/events/HPCN2000/
http://www.wins.uva.nl/events/HPCN2000/
|
We give a very brief overview of the Algorithms and Architecture
Approach as a means to produce high performance Dense Linear Algebra
Algorithms. The key idea that we develop is blocking for today's deep
memory hierarchies. We develop how recursion relates to dense linear algebra. Specifically we show how recursion leads to automatic variable blocking. Clearly, variable blocking is more general than conventional fixed blocking. We describe new data structures for full and packed storage of dense symmetric/triangular arrays that generalize both. Using the new data structures one is led to several new algorithms that save ``half'' the storage and outperform the current blocked based level 3 algorithms in LAPACK. We will describe a recursive formulation of Cholesky Factorization of a matrix in packed storage due to the authors and Bjarne S. Andersen of UNI$\bullet$C. The key to this algorithm is a novel data structure that converts standard packed format into $n - 1$ ``square'' full matrices and $n$ scalar diagonal elements. This formulation only use conventional GEMM, a surprising result in itself. Performance results for various dense linear algebra algorithms will be presented for several different computers. In particular, performance graphs of the LAPACK Cholesky (full and packed storage) algorithms and our new Cholesky algorithm using Recursive Packed Format will be presented. |