Publications
B. Smith and H. Zhang, "Sparse Triangular Solve Revisited: Data Layout Crucial to Better Performance," Preprint ANL/MCS-P1658-0809, August 2009. [pdf]
A key to good processor utilization for sparse matrix computations is storing the data in the format that is most conducive to fast access by the memory system. In particular, for sparse matrix triangular solves the traditional compressed sparse matrix format is poor, and
minor adjustments to the data structure can increase the processor utilization dramatically. Such adjustments involve storing the L and U factors separately and storing the U rows "backwards" so that they are accessed in a simple streaming fashion during the triangular solves. Changes to the PETSc libraries to use this modifi ed storage format resulted in over twice the floating-point rate for some matrices. This improvement can be accounted for by a decrease in the cache misses and TLB (transaction lookaside buff er) misses in the modified code.
