The Relevance of New Data Structure Approaches for Dense Linear Algebra in the New Multicore/Manycore Environments

For over ten years now, Bo K°agstr¨om’s Group in Umea, Sweden, Jerzy Wa´sniewski’s Team at Danish Technical University in Lyngby, Denmark, and I at IBM Research in Yorktown Heights have been applying recursion and new data structures to increase the performance of Dense Linear Algebra (DLA) factorization algorithms. Later, John Gunnels, and later still, Jim Sexton, both now at IBM Research began working in this area. For about three years now almost all computer manufacturers have dramatically changed their computer architectures which they call Multicore (MC). The traditional designs of DLA libraries such as LAPACK and ScaLAPACK perform poorly on MC. Recent results of Jack Dongarra’s group at the Innovative Computing Laboratory in Knoxville, Tennessee have shown how to obtain high performance for DLA factorization algorithms on the Cell architecture, an example of an MC processor, but only when they used new data structures. We will give some reasons why this is so.

We also present new algorithms for Blocked In-Place Rectangular Transposition of an M by N matrix A. This work adds blocking to the work by Gustavson and Swirszcz presented at Para06 on scalar in-place transposition. We emphasize the importance of RB format and also provide efficient algorithms between RB format and standard column and row major formats of 2-D arrays in the Fortran and C languages. Performance results are given. From a practical point of view, this work is very important as it will allow existing codes using LAPACK and ScaLAPACK to remain usable by new versions of LAPACK and ScaLAPACK.