Matrix representation

Combinatorics

Physics

Pattern recognition (psychology)

Organic chemistry

Mathematics

Kernel (algebra)

Algorithm

Support vector machine

Matrix (chemical analysis)

Sparse approximation

Gaussian

Parallel computing

Artificial intelligence

Composite material

Chemistry

Materials science

CUDA

Group (periodic table)

Computer science

Sparse matrix

Quantum mechanics

Selection (genetic algorithm)

Sparse Matrix-Vector Multiplication (SpMV) kernel dominates the computing cost in numerous scientific applications. Many implementations based on different sparse formats were proposed recently for this kernel on the GPU side. Since the performance of these sparse formats varies significantly according to the sparsity characteristics of the input matrix and the hardware specifications, no one of them can be considered as the best one to use for every sparse matrix. In this paper, we address the problem of selecting the best representation for a given sparse matrix on GPU by using a machine learning approach. First, we present some interesting and easy to compute features for characterizing the sparse matrices on GPU. Second, we use a multiclass Support Vector Machine (SVM) classifier to select the best format for each input matrix. We consider in this paper four popular formats (COO, CSR, ELL, and HYB), but our work can be extended to support more sparse representations. Experimental results on two different GPUs (Fermi GTX 580 and Maxwell GTX 980 Ti) show that we achieved more than 98% of the performance possible with a perfect selection.

Sparse Matrix Format Selection with Multiclass SVM for SpMV on GPU