Hierarchical diagonal blocking and precision reduction applied to combinatorial multigrid

Guy E. Blelloch, Ioannis Koutis, Gary L. Miller, Kanat Tangwongsan

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

4 Scopus citations

Abstract

Memory bandwidth is a major limiting factor in the scalability of parallel iterative algorithms that rely on sparse matrix-vector multiplication (SpMV). This paper introduces Hierarchical Diagonal Blocking (HDB), an approach which we believe captures many of the existing optimization techniques for SpMV in a common representation. Using this representation in conjuction with precision-reduction techniques, we develop and evaluate high-performance SpMV kernels. We also study the implications of using our SpMV kernels in a complete iterative solver. Our method of choice is a Combinatorial Multigrid solver that can fully utilize our fastest reduced-precision SpMV kernel without sacrificing the quality of the solution. We provide extensive empirical evaluation of the effectiveness of the approach on a variety of benchmark matrices, demonstrating substantial speedups on all matrices considered.

Original languageEnglish (US)
Title of host publication2010 ACM/IEEE International Conference for High Performance Computing, Networking, Storage and Analysis, SC 2010
DOIs
StatePublished - 2010
Externally publishedYes
Event2010 ACM/IEEE International Conference for High Performance Computing, Networking, Storage and Analysis, SC 2010 - New Orleans, LA, United States
Duration: Nov 13 2010Nov 19 2010

Publication series

Name2010 ACM/IEEE International Conference for High Performance Computing, Networking, Storage and Analysis, SC 2010

Other

Other2010 ACM/IEEE International Conference for High Performance Computing, Networking, Storage and Analysis, SC 2010
Country/TerritoryUnited States
CityNew Orleans, LA
Period11/13/1011/19/10

All Science Journal Classification (ASJC) codes

  • Computer Networks and Communications
  • Hardware and Architecture

Fingerprint

Dive into the research topics of 'Hierarchical diagonal blocking and precision reduction applied to combinatorial multigrid'. Together they form a unique fingerprint.

Cite this