Machine learning for optimal selection of sparse triangular system solvers on GPUs

Abstract

[EN] Many numerical algorithms for science and engineering applications require the solution of sparse triangular linear systems (sptrsv) as their most costly stage. For this reason, considerable research has been dedicated to produce efficient implementations for almost all high performance computing platforms. In the case of graphics processing units (GPUs), there are several strategies to perform this operation, which translate into a handful of different routines. In general, it is difficult to establish a priori which is the best routine for a given problem, and thus, an automatic procedure able to select the best solver for each matrix can entail large performance benefits.

This work extends a previous effort, in which we relied on machine learning techniques to predict the bestsptrsvroutine for each matrix, by improving both the accuracy and the speed of the selection procedure. Specifically, we focus on the most efficient machine learning techniques regarding the speed of their training and prediction stages; evaluate the artificial generation of sparse matrices to expand our dataset; and propose heuristics to compute approximations of some expensive features. The experimental results show that we can strongly improve the runtime of our procedure without compromising the quality results. (C) 2021 Elsevier Inc. All rights reserved.