Rescheduling for locality in sparse matrix computations

Michelle Mills Strout, Larry Carter, Jeanne Ferrante

Research output: Chapter in Book/Report/Conference proceedingConference contribution

22 Scopus citations


In modern computer architecture the use of memory hierarchies causes a program’s data locality to directly affect performance. Data locality occurs when a piece of data is still in a cache upon reuse. For dense matrix computations, loop transformations can be used to improve data locality. However, sparse matrix computations have non-affine loop bounds and indirect memory references which prohibit the use of compile time loop transformations. This paper describes an algorithm to tile at runtime called serial sparse tiling. We test a runtime tiled version of sparse Gauss-Seidel on 4 different architectures where it exhibits speedups of up to 2.7. The paper also gives a static model for determining tile size and outlines how overhead affects the overall speedup.

Original languageEnglish (US)
Title of host publicationComputational Science - ICCS 2001 - International Conference, 2001, Proceedings
EditorsVassil N. Alexandrov, Jack J. Dongarra, Benjoe A. Juliano, René S. Renner, C.J. Kenneth Tan
Number of pages10
ISBN (Print)3540422323, 9783540422327
StatePublished - 2001
Externally publishedYes
EventInternational Conference on Computational Science, ICCS 2001 - San Francisco, United States
Duration: May 28 2001May 30 2001

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


ConferenceInternational Conference on Computational Science, ICCS 2001
Country/TerritoryUnited States
CitySan Francisco

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'Rescheduling for locality in sparse matrix computations'. Together they form a unique fingerprint.

Cite this