Sparse tiling for stationary iterative methods

Michelle Mills Strout, Larry Carter, Jeanne Ferrante, Barbara Kreaseck

Research output: Contribution to journalArticlepeer-review

45 Scopus citations

Abstract

In modern computers, a program's data locality can affect performance significantly. This paper details full sparse tiling, a run-time reordering transformation that improves the data locality for stationary iterative methods such as Gauss-Seidel operating on sparse matrices. In scientific applications such as finite element analysis, these iterative methods dominate the execution time. Full sparse tiling chooses a permutation of the rows and columns of the sparse matrix, and then an order of execution that achieves better data locality. We prove that full sparse-tiled Gauss-Seidel generates a solution that is bitwise identical to traditional Gauss-Seidel on the permuted matrix. We also present measurements of the performance improvements and the overheads of full sparse tiling and of cache blocking for irregular grids, a related technique developed by Douglas et al.

Original languageEnglish (US)
Pages (from-to)95-113
Number of pages19
JournalInternational Journal of High Performance Computing Applications
Volume18
Issue number1
DOIs
StatePublished - 2004
Externally publishedYes

Keywords

  • Computer architecture
  • Data locality
  • Irregular grids
  • Iterative algorithms
  • Sparse matrix
  • Static and dynamic analysis
  • Tiling

ASJC Scopus subject areas

  • Software
  • Theoretical Computer Science
  • Hardware and Architecture

Fingerprint

Dive into the research topics of 'Sparse tiling for stationary iterative methods'. Together they form a unique fingerprint.

Cite this