Recursive Blocked Data Formats and BLAS's |
for Dense Linear Algebra Algorithms
Fred Gustavson1, André Henriksson2, Isak Jonsson2, Bo Kågström2, and
Per Ling2 Abstract Recursive blocked data formats and recursive blocked BLAS's are
introduced and applied to dense linear algebra algorithms that are typified by LAPACK. The new data formats allow for maintaining data locality at
every level of the memory hierarchy and hence providing high performance on today's memory tiered processors. This new data format is hybrid. It
contains blocking parameters which are chosen so that the associated submatrices of a block-partitioned A fit into level 1 cache. The
recursive part of the data format chooses a linear order of the blocks that maintains a two-dimensional data locality of A in a one-dimensional
tiered memory structure. We argue that, out of the NB factorial choices of ordering the NB blocks, our recursive ordering leads to one
of the best. This is because our algorithms are also recursive and will do their computations on submatrices that follow the new recursive data
structure definition. This is in analogy with the well known principle that the data structure should be matched to the algorithm. Performance results
in support for our recursive approach are also presented.
- IBM T.J. Watson Research Center, P.O. Box 218, Yorktown Heights, NY 10598, U.S.A.
- Department of Computing Science and HPC2N,
Umeå University, SE-901 87 Umeå, Sweden