This Article Free Full Text (Free PDF) Free References Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Add to Saved Citations Download to citation manager Add to My Marked Citations Citing Articles Citing Articles via Google Scholar Google Scholar Articles by Strout, M. M. Articles by Kreaseck, B. Search for Related Content Social Bookmarking                   What's this?

Sparse Tiling for Stationary Iterative Methods

ARGONNE NATIONAL LABORATORY

Larry Carter

Jeanne Ferrante

UNIVERSITY OF CALIFORNIA, SAN DIEGO

Barbara Kreaseck

LA SIERRA UNIVERSITY

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

Key Words: tiling • iterative alogorithms • static and dynamic analysis • irregular grids • data locality • sparse matrix • computer architecture

CiteULike    Connotea    Del.icio.us    Digg    Reddit    Technorati    What's this?