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. E-mail: gustav@watson.ibm.com Department of Computing Science and HPC2N, Umeå University, SE-901 87 Umeå, Sweden E-mail: {andropov,isak,bokg,pol}@cs.umu.se