International Journal of High Performance Computing Applications

 

Advanced Search

Journal Navigation

Journal Home

Subscriptions

Archive

Contact Us

Table of Contents

Click here for more information

Sign In to gain access to subscriptions and/or personal tools.
This Article
Right arrow Free Full Text (Free PDF) Free
Right arrow References
Right arrow Alert me when this article is cited
Right arrow Alert me if a correction is posted
Services
Right arrow Email this article to a friend
Right arrow Similar articles in this journal
Right arrow Alert me to new issues of the journal
Right arrow Add to Saved Citations
Right arrow Download to citation manager
Right arrow Add to My Marked Citations
Citing Articles
Right arrow Citing Articles via Google Scholar
Google Scholar
Right arrow Articles by Strout, M. M.
Right arrow Articles by Kreaseck, B.
Right arrow Search for Related Content
Social Bookmarking
 Add to CiteULike   Add to Connotea   Add to Del.icio.us   Add to Digg   Add to Reddit   Add to Technorati  
What's this?
International Journal of High Performance Computing Applications, Vol. 18, No. 1, 95-113 (2004)
DOI: 10.1177/1094342004041294
© 2004 SAGE Publications

Sparse Tiling for Stationary Iterative Methods

Michelle Mills Strout

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


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