Sparse triangular solves for ILU revisited: data layout crucial to better performance

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 da...

Full description

Saved in:
Bibliographic Details
Published in:International journal of high performance computing and networking 2011-11, Vol.25 (4), p.386-391
Main Authors: Smith, Barry, Zhang, Hong
Format: Article
Language:English
Subjects:
Adjustment
Central processing units
Computation
Computer memory
CPUs
FACTORIZATION
Floating point arithmetic
Floating structures
Format
GENERAL AND MISCELLANEOUS//MATHEMATICS, COMPUTING, AND INFORMATION SCIENCE
MATRICES
Microprocessors
Sparsity
STORAGE
Utilization
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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 modified 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 buffer) misses in the modified code.
ISSN:1094-3420
1740-0562
1741-2846
1740-0570
DOI:10.1177/1094342010389857