Combining performance aspects of irregular Gauss-Seidel via Sparse tiling

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

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

8 Scopus citations


Finite Element problems are often solved using multigrid techniques. The most time consuming part of multigrid is the iterative smoother, such as Gauss-Seidel. To improve performance, iterative smoothers can exploit parallelism, intra-iteration data reuse, and inter-iteration data reuse. Current methods for parallelizing Gauss-Seidel on irregular grids, such as multi-coloring and owner-computes based techniques, exploit parallelism and possibly intra-iteration data reuse but not inter-iteration data reuse. Sparse tiling techniques were developed to improve intra-iteration and inter-iteration data locality in iterative smoothers. This paper describes how sparse tiling can additionally provide parallelism. Our results show the effectiveness of Gauss-Seidel parallelized with sparse tiling techniques on shared memory machines, specifically compared to owner-computes based Gauss-Seidel methods. The latter employ only parallelism and intra-iteration locality. Our results support the premise that better performance occurs when all three performance aspects (parallelism, intra-iteration, and inter-iteration data locality) are combined.

Original languageEnglish (US)
Title of host publicationLanguages and Compilers for Parallel Computing - 15th Workshop, LCPC 2002, Revised Papers
Number of pages21
StatePublished - 2005
Externally publishedYes
Event15th Workshop on Languages and Compilers for Parallel Computing, LCPC 2002 - College Park, MD, United States
Duration: Jul 25 2002Jul 27 2002

Publication series

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


Conference15th Workshop on Languages and Compilers for Parallel Computing, LCPC 2002
Country/TerritoryUnited States
CityCollege Park, MD

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)


Dive into the research topics of 'Combining performance aspects of irregular Gauss-Seidel via Sparse tiling'. Together they form a unique fingerprint.

Cite this