sponsored byIEEEACMThe International Conference for High Performance 
Computing, Networking, Storage and Analysis
FacebookTwitterGoogle PlusLinkedInYouTubeFlickr

SCHEDULE: NOV 16-21, 2014

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.

Parallelization of Reordering Algorithms for Bandwidth and Wavefront Reduction

SESSION: Sparse Solvers


TIME: 1:30PM - 2:00PM


AUTHOR(S):Konstantinos I. Karantasis, Andrew Lenharth, Donald Nguyen, Maria Garzaran, Keshav Pingali



Many sparse matrix computations can be speeded up by first suitably reordering the sparse matrix. Reorderings, originally developed to assist direct methods, have recently become popular for improving cache locality of parallel iterative solvers. When sparse matrix-vector product (SpMV), the key kernel in iterative solvers, runs, reorderings targeting bandwidth and wavefront reduction can improve locality of reference to the compressed sparse storage vectors.

In this paper, we present the first parallel implementations of two widely used reordering algorithms: Reverse Cuthill-McKee (RCM) and Sloan. On 16 cores on Stampede supercomputer, our results show average improvement of 5.56X compared to the state-of-the-art sequential RCM implementation in the HSL library. Sloan is significantly more constrained than RCM; our parallel implementation achieves 2.88X average improvement compared to HSL-Sloan. Considering end-to-end times, using our reordering, SpMV obtains performance improvement of 1.5X compared to natural ordering, and 2X compared to HSL RCM for 100 SpMV iterations.

Chair/Author Details:

Anne C. Elster (Chair) - Norwegian University of Science & Technology / University of Texas at Austin

Konstantinos I. Karantasis - University of Illinois at Urbana-Champaign

Andrew Lenharth - University of Texas at Austin

Donald Nguyen - University of Texas at Austin

Maria Garzaran - University of Illinois at Urbana-Champaign

Keshav Pingali - University of Texas at Austin

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

Paper provided by the ACM Digital Library

Paper also available from IEEE Computer Society