Sparse Matrix Multiplication on GPU or CPU?

What do you think? What would be faster and how much faster: Doing sparse matrix (CSR) multiplication (with a vector) on the GPU or the CPU开发者_运维知识库 (multithreaded)?

It depends upon the size of the matrix and number of iterations that needs to be performed. This is because you need to copy the matrix data from CPU memory to GPU memory and copy back the results from the GPU to CPU. If you are gonna perform only one iteration on the matrix, its always better to do it on the CPU rather than doing it on a GPU. Moreover, GPU suffers from startup time. So, if you have more iterations to be performed, then go for GPU, else my option will be CPU. Likewise size of the matrix also affects the performance due to the data copying.

Here you can find some performance results for Sparse Matrix-Vector multiplication on CPU and GPU. Performance on GPU is measured for CSR, CSR-Vector, CSR-Adaptive, ELL, COO, SCOO, HYB matrix formats. The matrices were taken from the SuiteSparse Matrix Collection (formerly the University of Florida Sparse Matrix Collection). In the final figure, you could find results for single-thread, multi-thread and MKL CSR.

The average speedup for HYB matrix format is about 8 (max speedup is about 38) for float matrices with more than 10000 non-zero elements. But, as noticed in the comments, the speedup is better on big matrices (14 for matrices with more than 100000 non-zero elements).

My guess is that there would not be a big win with a GPU implementation, since you don't have the kind of homogeneous data structure that lends itself to embarallel processing.

I think veda hits the nail on its head. I am by no means an expert on this but I believe there is an overhead in putting the gpu to work and if the size of the computation isn't big enough the winnings of the gpu processing is lost to the overhead. However if you have something like a character skeleton where you have lots of matrices being multiplied then this would be more suited for the gpu. I'm currently also looking into these things for a project of mine.