SCHEDULE: NOV 15-20, 2015

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.

STS-k: A Multilevel Sparse Triangular Solution Scheme for NUMA Multicores

SESSION: Linear Algebra

EVENT TYPE: Papers

EVENT TAG(S): Algorithms, Scientific Computing, Solvers

TIME: 4:30PM - 5:00PM

SESSION CHAIR(S): Gabriel Tanase

AUTHOR(S):Humayun Kabir, Joshua D. Booth, Guillaume Aupy, Anne Benoit, Yves Robert, Padma Raghavan

ROOM:18AB

ABSTRACT:

We consider techniques to improve the performance of parallel sparse triangular solution on non-uniform memory architecture multicores by extending earlier coloring and level set schemes for single-core multiprocessors. We develop STS-k, where k represents a small number of transformations for latency reduction from increased spatial and temporal locality of data accesses. We propose a graph model of data reuse to inform the development of STS-k and to prove that computing an optimal cost schedule is NP-complete. We observe significant speed-ups with STS-3 on a 32-core Intel Westmere-Ex. Execution times are reduced on average by a factor of 6 (83%) for STS-3 with coloring compared to a reference implementation using level sets. Incremental gains solely from the k level transformations in STS-k correspond to reductions in execution times by factors of 1.4 (28%) and 2 (50%) respectively, relative to reference implementations with level sets and coloring.

Chair/Author Details:

Gabriel Tanase (Chair) - IBM Corporation|

Humayun Kabir - Pennsylvania State University

Joshua D. Booth - Sandia National Laboratories

Guillaume Aupy - ENS Lyon

Anne Benoit - ENS Lyon

Yves Robert - ENS Lyon

Padma Raghavan - Pennsylvania State University

  Click here to download .ics calendar file

  Click here to download .vcs calendar file

  Click here to add event to your Google Calendar

Paper provided by the ACM Digital Library

Paper also available from IEEE Computer Society