Runtime sparse matrix format selection

Warren Armstrong, Alistair P. Rendell

Research output: Contribution to journalArticlepeer-review

3 Citations (Scopus)

Abstract

There exist many storage formats for the in-memory representation of sparse matrices. Choosing the format that yields the quickest processing of any given sparse matrix requires considering the exact non-zero structure of the matrix, as well as the current execution environment. Each of these factors can change at runtime. The matrix structure can vary as computation progresses, while the environment can change due to varying system load, the live migration of jobs across a heterogeneous cluster, etc. This paper describes an algorithm that learns at runtime how to map sparse matrices onto the format which provides the quickest sparse matrix-vector product calculation, and which can adapt to the hardware platform changing underfoot. We show multiplication times reduced by over 10% compared with the best non-adaptive format selection.

Original languageEnglish
Pages (from-to)135-144
Number of pages10
JournalProcedia Computer Science
Volume1
Issue number1
DOIs
Publication statusPublished - May 2010
Externally publishedYes

Bibliographical note

(CC BY-NC-ND 4.0) Open Access article licensed under a Creative Commons Attribution Non-Commercial No Derivatives license, which permits others to distribute this work non-commercially, provided the original work is properly cited and the use is non-commercial. If you remix, transform, or build upon the material, you may not distribute the modified material. See: http://creativecommons.org/licenses/by-nc-nd/4.0/

Keywords

  • Runtime tuning
  • Sparse matrix formats

Fingerprint Dive into the research topics of 'Runtime sparse matrix format selection'. Together they form a unique fingerprint.

Cite this