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.
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/
- Runtime tuning
- Sparse matrix formats