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.

By: Fred G. Gustavson

Published in: RC24599 in 2008


This Research Report is available. This report has been submitted for publication outside of IBM and will probably be copyrighted if accepted for publication. It has been issued as a Research Report for early dissemination of its contents. In view of the transfer of copyright to the outside publisher, its distribution outside of IBM prior to publication should be limited to peer communications and specific requests. After outside publication, requests should be filled only by reprints or legally obtained copies of the article (e.g., payment of royalties). I have read and understand this notice and am a member of the scientific community outside or inside of IBM seeking a single copy only.


Questions about this service can be mailed to .