Sparse matrix-vector multiplication on graphics processor units

1. A method for optimizing sparse matrix-vector multiplication (SpMV) on a graphics processing unit (GPU), wherein the method comprises:

receiving a sparse matrix-vector multiplication, wherein said receiving is carried out by a distinct software module executing on a hardware processor;

analyzing the sparse matrix-vector multiplication to identify one or more optimizations, wherein analyzing the sparse matrix-vector multiplication to identify one or more optimizations comprises analyzing a non-zero pattern for one or more optimizations and determining whether the sparse matrix-vector multiplication is to be reused across a computation, and wherein said analyzing is carried out by a distinct software module executing on a hardware processor;

optimizing the sparse matrix-vector multiplication, wherein optimizing the sparse matrix-vector multiplication comprises optimizing global memory access, optimizing shared memory access and exploiting reuse and parallelism, wherein said optimizing is carried out by a distinct software module executing on a hardware processor; and

outputting an optimized sparse matrix-vector multiplication, wherein said outputting is carried out by a distinct software module executing on a hardware processor.

2. The method of claim 1 , wherein optimizing the sparse matrix-vector multiplication further comprises characterizing memory access cost, type and level of memory, and access pattern.

3. The method of claim 1 , wherein the one or more optimizations comprise at least one of exploiting synchronization-free parallelism, optimized thread mapping based on affinity towards optimal memory access pattern, optimized off-chip memory access to tolerate high access latency, and exploiting data locality and reuse.

4. The method of claim 1 , wherein exploiting parallelism comprises exploiting synchronization-free parallelism.

5. The method of claim 1 , wherein optimizing the sparse matrix-vector multiplication further comprises exploiting data locality.

6. The method of claim 1 , wherein exploiting reuse comprises caching each element in one or more on-chip memories.

7. The method of claim 1 , further comprising performing a run-time preprocessing of the sparse matrix-vector multiplication to identify and extract one or more dense sub-blocks.

8. The method of claim 1 , further comprising tuning one or more configuration parameters.

9. The method of claim 8 , wherein tuning one or more configuration parameters comprises varying a number of threads per thread block used for execution.

10. The method of claim 8 , wherein tuning one or more configuration parameters comprises varying a number of threads handling a row.

11. The method of claim 1 , further comprising providing a system, wherein the system comprises one or more distinct software modules, each of the one or more distinct software modules being embodied on a tangible computer-readable recordable storage medium, and wherein the one or more distinct software modules comprise an inspector-analyzer module, an optimizer module, a cost model module and an executor module executing on a hardware processor.

12. A computer program product comprising a tangible computer readable recordable storage medium including computer useable program code for optimizing sparse matrix-vector multiplication (SpMV) on a graphics processing unit (GPU), the computer program product including:

computer useable program code for receiving a sparse matrix-vector multiplication;

computer useable program code for analyzing the sparse matrix-vector multiplication to identify one or more optimizations, wherein analyzing the sparse matrix-vector multiplication to identify one or more optimizations comprises analyzing a non-zero pattern for one or more optimizations and determining whether the sparse matrix-vector multiplication is to be reused across a computation;

computer useable program code for optimizing the sparse matrix-vector multiplication, wherein optimizing the sparse matrix-vector multiplication comprises optimizing global memory access, optimizing shared memory access and exploiting reuse and parallelism; and

computer useable program code for outputting an optimized sparse matrix-vector multiplication.

13. The computer program product of claim 12 , wherein the computer useable program code for optimizing the sparse matrix-vector multiplication comprises computer useable program code for characterizing memory access cost, type and level of memory, and access pattern.

14. The computer program product of claim 12 , wherein the one or more optimizations comprise at least one of exploiting synchronization-free parallelism, optimized thread mapping based on affinity towards optimal memory access pattern, optimized off-chip memory access to tolerate high access latency, and exploiting data locality and reuse.

15. The computer program product of claim 12 , wherein the computer useable program code for optimizing the sparse matrix-vector multiplication comprises computer useable program code for exploiting data locality.

16. The computer program product of claim 12 , further comprising computer useable program code for performing a run-time preprocessing of the sparse matrix-vector multiplication to identify and extract one or more dense sub-blocks.

17. The computer program product of claim 12 , further comprising computer useable program code for tuning one or more configuration parameters.

18. The computer program product of claim 15 , wherein the computer useable program code comprises one or more distinct software modules, and wherein the one or more distinct software modules comprise an inspector-analyzer module, an optimizer module, a cost model module and an executor module executing on a hardware processor.

19. A system for optimizing sparse matrix-vector multiplication (SpMV) on a graphics processing unit (GPU), comprising:

a memory; and

at least one processor coupled to the memory and operative to:

receive a sparse matrix-vector multiplication;

analyze the sparse matrix-vector multiplication to identify one or more optimizations, wherein analyzing the sparse matrix-vector multiplication to identify one or more optimizations comprises analyzing a non-zero pattern for one or more optimizations and determining whether the sparse matrix-vector multiplication is to be reused across a computation;

optimize the sparse matrix-vector multiplication, wherein optimizing the sparse matrix-vector multiplication comprises optimizing global memory access, optimizing shared memory access and exploiting reuse and parallelism; and

output an optimized sparse matrix-vector multiplication.

20. The system of claim 19 , wherein the at least one processor coupled to the memory operative to optimize the sparse matrix-vector multiplication is further operative to characterize memory access cost, type and level of memory, and access pattern.

21. The system of claim 19 , wherein the one or more optimizations comprise at least one of exploiting synchronization-free parallelism, optimized thread mapping based on affinity towards optimal memory access pattern, optimized off-chip memory access to tolerate high access latency, and exploiting data locality and reuse.

22. The system of claim 19 , wherein the at least one processor coupled to the memory is further operative to perform a run-time preprocessing of the sparse matrix-vector multiplication to identify and extract one or more dense sub-blocks.

23. The system of claim 19 , wherein the at least one processor coupled to the memory is further operative to tune one or more configuration parameters.

24. The system of claim 19 , further comprising a tangible computer-readable recordable storage medium having one or more distinct software modules embodied thereon, wherein the one or more distinct software modules comprise an inspector-analyzer module, an optimizer module, a cost model module and an executor module executing on a hardware processor.

25. An apparatus for optimizing sparse matrix-vector multiplication (SpMV) on a graphics processing unit (GPU), the apparatus comprising:

means for receiving a sparse matrix-vector multiplication;

means for analyzing the sparse matrix-vector multiplication to identify one or more optimizations, wherein analyzing the sparse matrix-vector multiplication to identify one or more optimizations comprises analyzing a non-zero pattern for one or more optimizations and determining whether the sparse matrix-vector multiplication is to be reused across a computation;

means for optimizing the sparse matrix-vector multiplication, wherein optimizing the sparse matrix-vector multiplication comprises optimizing global memory access, optimizing shared memory access and exploiting reuse and parallelism; and

means for outputting an optimized sparse matrix-vector multiplication.