SC13 Home > SC13 Schedule > SC13 Presentation - Accelerating Sparse Matrix-Vector Multiplication on GPUs using Bit-Representation-Optimized Schemes

SCHEDULE: NOV 16-22, 2013

When viewing the Technical Program schedule, on the far righthand side is a column labeled "PLANNER." Use this planner to build your own schedule. Once you select an event and want to add it to your personal schedule, just click on the calendar icon of your choice (outlook calendar, ical calendar or google calendar) and that event will be stored there. As you select events in this manner, you will have your own schedule to guide you through the week.

Accelerating Sparse Matrix-Vector Multiplication on GPUs using Bit-Representation-Optimized Schemes

SESSION: Optimizing Numerical Code

EVENT TYPE: Papers

TIME: 4:00PM - 4:30PM

SESSION CHAIR: Naoya Maruyama

AUTHOR(S):Wai Teng Tang, Wen Jun Tan, Rajarshi Ray, Yi Wen Wong, Weiguang Chen, Shyh-hao Kuo, Rick Siow Mong Goh, Stephen John Turner, Weng-Fai Wong

ROOM:401/402/403

ABSTRACT:
The sparse matrix-vector (SpMV) multiplication routine is an important building block used in many iterative algorithms for solving scientific and engineering problems. One of the main challenges of SpMV is its memory-boundedness. Although compression has been proposed previously to improve SpMV performance on CPUs, its use has not been demonstrated on the GPU because of the serial nature of many compression and decompression schemes. In this paper, we introduce a family of bit-representation-optimized (BRO) compression schemes for representing sparse matrices on GPUs. The proposed schemes, BRO-ELL, BRO-COO, and BRO-HYB, perform compression on index data and help to speed up SpMV on GPUs through reduction of memory traffic. Furthermore, we formulate a BRO-aware matrix reordering scheme as a data clustering problem and use it to increase compression ratios. With the proposed schemes, experiments show that average speedups of 1.5X compared to ELLPACK and HYB can be achieved for SpMV on GPUs.

Chair/Author Details:

Naoya Maruyama (Chair) - RIKEN Advanced Institute for Computational Science

Wai Teng Tang - Nanyang Technological University

Wen Jun Tan - Nanyang Technological University

Rajarshi Ray - National University of Singapore

Yi Wen Wong - National University of Singapore

Weiguang Chen - National University of Singapore

Shyh-hao Kuo - Agency for Science, Technology and Research

Rick Siow Mong Goh - Agency for Science, Technology and Research

Stephen John Turner - Nanyang Technological University

Weng-Fai Wong - National University of Singapore

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