SC is the International Conference for
 High Performnance Computing, Networking, Storage and Analysis

SCHEDULE: NOV 13-19, 2010

Hierarchical Diagonal Blocking and Precision Reduction Applied to Combinatorial Multigrid

SESSION: Intra-Node Method Optimization


TIME: 11:00AM - 11:30AM

SESSION CHAIR: William Harrod

AUTHOR(S):Guy Blelloch, Ioannis Koutis, Gary L. Miller, Kanat Tangwongsan


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.

Chair/Author Details:

William Harrod (Chair) - DARPA

Guy Blelloch - Carnegie Mellon University

Ioannis Koutis - Carnegie Mellon University

Gary L. Miller - Carnegie Mellon University

Kanat Tangwongsan - Carnegie Mellon University

Add to iCal  Click here to download .ics calendar file

Add to Outlook  Click here to download .vcs calendar file

Add to Google Calendarss  Click here to add event to your Google Calendar

The full paper can be found in the ACM Digital Library and IEEE Computer Society

   Sponsors    IEEE    ACM