Paper Info
Title
Automatic Selection of Sparse Triangular Linear System Solvers on GPUs through Machine Learning Techniques
Abstract
The solution of sparse triangular linear systems is often the most time-consuming stage of preconditioned iterative methods to solve general sparse linear systems, where it has to be applied several times for the same sparse matrix. For this reason, its computational performance has a strong impact on a wide range of scientific and engineering applications, which has motivated the study of its efficient execution on massively parallel platforms. In this sense, several methods have been proposed to tackle this operation on graphics processing units (GPUs), which can be classified under either the level-set or the self-scheduling paradigms. The results obtained from the experimental evaluation of the different methods suggest that both paradigms perform well for certain problems but poorly for others. Additionally, the relation between the properties of the linear systems and the performance of the different solvers is not evident a-priori. In this context, techniques that allow to predict inexpensively which is be the best solver for a particular linear system can lead to important runtime reductions. Our approach leverages machine learning techniques to select the best sparse triangular solver for a given linear system, with focus on the case where a small number of triangular systems has to be solved for the same matrix. We study the performance of several methods using different features derived from the sparse matrices, obtaining models with more than 80% of accuracy and acceptable prediction speed. These results are an important advance towards the automatic selection of the best GPU solver for a given sparse triangular linear system, and the characterization of the performance of these kernels.
Year
DOI
Venue
2019
10.1109/SBAC-PAD.2019.00020
2019 31st International Symposium on Computer Architecture and High Performance Computing (SBAC-PAD)
Keywords
Field
DocType
graphics processors,sparse triangular linear systems,high performance,machine learning
Graphics,Small number,Linear system,Iterative method,Matrix (mathematics),Computer science,Massively parallel,Parallel computing,Artificial intelligence,Solver,Machine learning,Sparse matrix
Conference
ISSN
ISBN
Citations 
1550-6533
978-1-7281-4195-4
0
PageRank 
References 
Authors
0.34
7
3
Name
Order
Citations
PageRank
Ernesto Dufrechou12511.02
Pablo Ezzatti212428.24
Enrique S. Quintana-Ortí32112.58