IPB

Welcome Guest ( Log In | Register )

4 Pages V   1 2 3 > »   
Reply to this topicStart new topic
> Sparse Matrix-Vector Multiplication on CUDA
nbell
post Dec 10 2008, 04:57 PM
Post #1



****

Group: Members
Posts: 67
Joined: 10-December 08
Member No.: 129,848
Org.: NVIDIA



I'm pleased to announce the release of our tech report "Efficient Sparse Matrix-Vector Multiplication on CUDA". It can be challenging to implement sparse matrix operations efficiently, so I hope this report offers some guidance to those working on iterative solvers and other areas where sparse matrix-vector products arise. Feel free to follow up with comments/questions about the report.

Update: A collection of test matrices is now available
Update: Supercomputing '09 SpMV paper is now available
Update: New and improved source code is now available (Requires CUDA 2.2 or newer)

Abstract:
QUOTE
The massive parallelism of graphics processing units (GPUs) offers tremendous performance in many
high-performance computing applications. While dense linear algebra readily maps to such platforms,
harnessing this potential for sparse matrix computations presents additional challenges. Given its role
in iterative methods for solving sparse linear systems and eigenvalue problems, sparse matrix-vector
multiplication (SpMV) is of singular importance in sparse linear algebra.

In this paper we discuss data structures and algorithms for SpMV that are efficiently implemented
on the CUDA platform for the fine-grained parallel architecture of the GPU. Given the memory-bound
nature of SpMV, we emphasize memory bandwidth efficiency and compact storage formats. We consider
a broad spectrum of sparse matrices, from those that are well-structured and regular to highly irregular
matrices with large imbalances in the distribution of nonzeros per matrix row. We develop methods to
exploit several common forms of matrix structure while offering alternatives which accommodate greater
irregularity.

On structured, grid-based matrices we achieve performance of 36 GFLOP/s in single precision and
16 GFLOP/s in double precision on a GeForce GTX 280 GPU. For unstructured finite-element matrices,
we observe performance in excess of 15 GFLOP/s and 10 GFLOP/s in single and double precision
respectively. These results compare favorably to prior state-of-the-art studies of SpMV methods on
conventional multicore processors. Our double precision SpMV performance is generally two and a half
times that of a Cell BE with 8 SPEs and more than ten times greater than that of a quad-core Intel
Clovertown system.


This post has been edited by nbell: Sep 9 2009, 07:18 AM
Attached File(s)
Attached File  nvr_2008_004.pdf ( 3.44MB ) Number of downloads: 1787
 
Go to the top of the page
 
+Quote Post
oscarb
post Dec 11 2008, 03:47 AM
Post #2



***

Group: Members
Posts: 26
Joined: 17-November 08
Member No.: 126,289



QUOTE (nbell @ Dec 10 2008, 05:57 PM) *
I'm pleased to announce the release of our tech report "Efficient Sparse Matrix-Vector Multiplication on CUDA". It can be challenging to implement sparse matrix operations efficiently, so I hope this report offers some guidance to those working on iterative solvers and other areas where sparse matrix-vector products arise. I don't have the source code available today, but we'll definitely release that in the near future. Feel free to follow up with comments/questions about the report.

Abstract:

Very interesting..
Since I am interested on it can you give an rough estimate of when the code will be avaiable (say some days, a week,a month..)? thanks!
Go to the top of the page
 
+Quote Post
maringanti
post Dec 11 2008, 10:35 AM
Post #3



***

Group: Members
Posts: 35
Joined: 28-October 07
Member No.: 76,048
Org.: IIT



This is very useful. Thanks a lot guys.

is it possible to point out where i can get the data for the test matrices ?

also when reporting the final results, did you guys use texture cache to read x or without texture cache ?

This post has been edited by maringanti: Dec 11 2008, 10:37 AM
Go to the top of the page
 
+Quote Post
nbell
post Dec 11 2008, 01:13 PM
Post #4



****

Group: Members
Posts: 67
Joined: 10-December 08
Member No.: 129,848
Org.: NVIDIA



QUOTE (oscarb @ Dec 10 2008, 10:47 PM) *
Very interesting..
Since I am interested on it can you give an rough estimate of when the code will be avaiable (say some days, a week,a month..)? thanks!


I would estimate one or two weeks.
Go to the top of the page
 
+Quote Post
nbell
post Dec 11 2008, 01:23 PM
Post #5



****

Group: Members
Posts: 67
Joined: 10-December 08
Member No.: 129,848
Org.: NVIDIA



QUOTE (maringanti @ Dec 11 2008, 05:35 AM) *
This is very useful. Thanks a lot guys.

is it possible to point out where i can get the data for the test matrices ?


Some of the matrices are online here:
http://www.cis.ufl.edu/research/sparse/mat...oeing/pwtk.html (Wind Tunnel)
http://www.cis.ufl.edu/research/sparse/mat...n/rail4284.html (LP)

The full set of matrices is over 200MB in compressed format. I'll find a way to put them online.

QUOTE
also when reporting the final results, did you guys use texture cache to read x or without texture cache ?


Yes, we do use the texture cache in the comparison to the multicore systems.
Go to the top of the page
 
+Quote Post
maringanti
post Dec 11 2008, 02:14 PM
Post #6



***

Group: Members
Posts: 35
Joined: 28-October 07
Member No.: 76,048
Org.: IIT



QUOTE (nbell @ Dec 11 2008, 06:53 PM) *

Thanks
QUOTE
The full set of matrices is over 200MB in compressed format. I'll find a way to put them online.

If these matrices are already available on UF Sparse Matrix page or on the Matrix Market page, you can just point them out.

Go to the top of the page
 
+Quote Post
nbell
post Dec 12 2008, 03:21 PM
Post #7



****

Group: Members
Posts: 67
Joined: 10-December 08
Member No.: 129,848
Org.: NVIDIA



QUOTE (maringanti @ Dec 11 2008, 09:14 AM) *
Thanks

If these matrices are already available on UF Sparse Matrix page or on the Matrix Market page, you can just point them out.


All the matrices are available here:
http://bebop.cs.berkeley.edu/matrices/multicore-subset/

Those files use the Harwell-Boeing format [1]. You can use the BeBOP Sparse Matrix Converter [2] to convert them to another format. Our code (which I will post soon!) uses the MatrixMarket file format [3], so I'll put MM versions of the files online when the code has been released.

[1] http://math.nist.gov/MatrixMarket/formats.html#hb
[2] http://bebop.cs.berkeley.edu/smc/
[3] http://math.nist.gov/MatrixMarket/formats.html#MMformat
Go to the top of the page
 
+Quote Post
Dominik Gddeke
post Dec 13 2008, 01:03 AM
Post #8



*****

Group: Extranet Users
Posts: 110
Joined: 2-April 08
Member No.: 98,683



nbell, terrific work! Will this be made available in future versions of the CUDA SDK or in cudpp?

How does your approach compare to block-CSR as suggested by Buatois et al., http://alice.loria.fr/publications/papers/...s_et_al_CNC.pdf ? I haven't found any comparison in your otherwise brilliant paper.

dom

Go to the top of the page
 
+Quote Post
maringanti
post Dec 13 2008, 09:43 AM
Post #9



***

Group: Members
Posts: 35
Joined: 28-October 07
Member No.: 76,048
Org.: IIT



@nbell, thanks for the links.

This post has been edited by maringanti: Dec 13 2008, 09:50 AM
Go to the top of the page
 
+Quote Post
nbell
post Dec 15 2008, 04:42 PM
Post #10



****

Group: Members
Posts: 67
Joined: 10-December 08
Member No.: 129,848
Org.: NVIDIA



QUOTE (Dominik G�ddeke @ Dec 12 2008, 08:03 PM) *
nbell, terrific work! Will this be made available in future versions of the CUDA SDK or in cudpp?

How does your approach compare to block-CSR as suggested by Buatois et al., http://alice.loria.fr/publications/papers/...s_et_al_CNC.pdf ? I haven't found any comparison in your otherwise brilliant paper.

dom


Hi Dominik,

A (possibly different) version of this code should appear in the CUDA 2.2 SDK. However, we'll release the complete source code in the next week or so here.

Unfortunately, I don't have any direct comparisons to the CNC work. Blocking is often a very useful optimization as it improves locality and reuse of the "source" vector (i.e. x in y = A*x). This is nearly always a win when the matrix has a natural blocksize, such as a vector-valued problem with regular KxK subblocks. The CNC paper uses blocking even though the underlying problem is scalar-valued. In their application (mesh-based matrices) this proves to be advantageous because the subblocks have a reasonable number of nonzeros due to the ordering of rows and columns. However, there are many problems that do not benefit from blocking, so formats like block-CSR aren't always beneficial.

We'd definitely like to explore this area though. I think it's likely that different strategies are needed to handle different block sizes optimally. For example, the best method for 2x2 blocks will probably be different than the best method for 6x6 blocks, since you run into a different set of constraints.
Go to the top of the page
 
+Quote Post
Dominik Gddeke
post Dec 15 2008, 09:29 PM
Post #11



*****

Group: Extranet Users
Posts: 110
Joined: 2-April 08
Member No.: 98,683



Hi nbell,

I agree, blocking is not always beneficial (or better, that the optimal blocking technique is application-dependent). I've toyed around a bit with renumbering strategies like Cuthill-McKee and the like, and for our FEM-CFD matrices, this helps at creating a reasonable number of nonzero values per average block.

Anyway, having code available for general SpMV is definitely one of the missing links between CUDA and (some) real-world applications, so congrats again!

dom
Go to the top of the page
 
+Quote Post
dlmeetei
post Dec 16 2008, 04:19 AM
Post #12



****

Group: Members
Posts: 65
Joined: 15-December 07
Member No.: 83,342
Org.: NAL,Bangalore



Yea, The Links wre useful to me too, Waiting for the CUDA version of it.
Go to the top of the page
 
+Quote Post
nbell
post Dec 19 2008, 12:46 AM
Post #13



****

Group: Members
Posts: 67
Joined: 10-December 08
Member No.: 129,848
Org.: NVIDIA



QUOTE (dlmeetei @ Dec 15 2008, 11:19 PM) *
Yea, The Links wre useful to me too, Waiting for the CUDA version of it.


I've attached a zip file containing the source code to the original post. The included README.txt should provide enough info to get you started. Please let me know if you have any trouble with the code!

Once I get the complete set of matrices online I'll add another link.
Go to the top of the page
 
+Quote Post
Kagami
post Dec 19 2008, 06:57 AM
Post #14



*

Group: Members
Posts: 2
Joined: 17-December 08
Member No.: 130,943



Dear nbell,
Is it best to use your method for calculating sparse matrix matrix multiplication?
Go to the top of the page
 
+Quote Post
Bruno Levy
post Dec 19 2008, 02:33 PM
Post #15



*

Group: Members
Posts: 1
Joined: 16-December 08
Member No.: 130,722
Org.: INRIA



Hi,

Thank you very much Nathan for making your code available,

We are excited to see this technology coming out,

About blocking, there is a possible strategy (that we did not include yet in the Concurrent Number Cruncher):

One can construct the sparsity pattern for different blocking sizes, and evaluate the best block size to use based
on the filling ratios. Since constructing the sparsity pattern costs less than constructing the whole sparse matrix,
several block sizes can be reasonably tryed. I have read a while ago a paper that used this strategy (I do not
remember where, I will post the reference if I find it)

Regards,
-- Bruno Levy

Go to the top of the page
 
+Quote Post
nbell
post Dec 19 2008, 03:27 PM
Post #16



****

Group: Members
Posts: 67
Joined: 10-December 08
Member No.: 129,848
Org.: NVIDIA



QUOTE (Kagami @ Dec 19 2008, 01:57 AM) *
Dear nbell,
Is it best to use your method for calculating sparse matrix matrix multiplication?


Hi Kagami,

Are you referring to the case A*X where A is a sparse matrix but X is a dense matrix? If so, you can use the code above, and simply compute A*x several times, where x is a single column of the matrix X. Alternatively, you could write a kernel that did multiple columns at the same time, as we suggest in the "Future Work" section of the paper. This optimization can improve performance considerably.

If you're referring to the case A*X where both A and B are sparse matrices, then that's a harder problem that this code does not address. FWIW I have implemented this operation in another code (an algebraic multigrid (AMG) solver), so if you're interested I can provide some assistance.
Go to the top of the page
 
+Quote Post
nbell
post Dec 19 2008, 03:40 PM
Post #17



****

Group: Members
Posts: 67
Joined: 10-December 08
Member No.: 129,848
Org.: NVIDIA



QUOTE (Bruno Levy @ Dec 19 2008, 09:33 AM) *
Hi,

Thank you very much Nathan for making your code available,

We are excited to see this technology coming out,

About blocking, there is a possible strategy (that we did not include yet in the Concurrent Number Cruncher):

One can construct the sparsity pattern for different blocking sizes, and evaluate the best block size to use based
on the filling ratios. Since constructing the sparsity pattern costs less than constructing the whole sparse matrix,
several block sizes can be reasonably tryed. I have read a while ago a paper that used this strategy (I do not
remember where, I will post the reference if I find it)

Regards,
-- Bruno Levy



Are you referring to the "Sparsity" package [1]? They discuss a simple model based on filling ratios that guides the selection block size. Since the Sparsity paper, there has been some work on "variable blocking" where, I believe, one first extracts all the larger blocks (e.g. 4x4) and then extracts smaller blocks (4x1, 2x2, etc.). I haven't experimented with these methods myself, but it seems like a good idea.

[1] http://hpc.sagepub.com/cgi/reprint/18/1/135
Go to the top of the page
 
+Quote Post
maringanti
post Dec 21 2008, 06:34 PM
Post #18



***

Group: Members
Posts: 35
Joined: 28-October 07
Member No.: 76,048
Org.: IIT



@nathan

I have been playing around with source code to understand it. One thing I have noticed is that some of the calls that I have commented out are still executing

Say for example i comment out test_dia_matrix_kernels(csr) and test_csr_matrix_kernels(csr) - these calls are executed even though i have commented them out.
Can you tell me why this is happening ?

I have recompiled them and tried it a few times but they are still getting executed.

EDIT: Nevermind. Some stupidity on my part. I was recompiling the same object files again and again.

This post has been edited by maringanti: Dec 22 2008, 12:47 AM
Go to the top of the page
 
+Quote Post
Kagami
post Dec 22 2008, 02:27 AM
Post #19



*

Group: Members
Posts: 2
Joined: 17-December 08
Member No.: 130,943



QUOTE (nbell @ Dec 19 2008, 04:27 PM) *
Hi Kagami,

Are you referring to the case A*X where A is a sparse matrix but X is a dense matrix? If so, you can use the code above, and simply compute A*x several times, where x is a single column of the matrix X. Alternatively, you could write a kernel that did multiple columns at the same time, as we suggest in the "Future Work" section of the paper. This optimization can improve performance considerably.

If you're referring to the case A*X where both A and B are sparse matrices, then that's a harder problem that this code does not address. FWIW I have implemented this operation in another code (an algebraic multigrid (AMG) solver), so if you're interested I can provide some assistance.


Hi nbell,

I just ask to make sure that your program is not suitable for calculating matrix-matrix multiplication in which both matrices are sparse.

I would contact you to ask for more information.

Thank you very much for your consideration.
Go to the top of the page
 
+Quote Post
ph03
post Dec 27 2008, 07:39 PM
Post #20



*

Group: Members
Posts: 2
Joined: 27-December 08
Member No.: 132,416
Org.: University of Magdeburg



QUOTE (Kagami @ Dec 22 2008, 03:27 AM) *
Hi nbell,

I just ask to make sure that your program is not suitable for calculating matrix-matrix multiplication in which both matrices are sparse.

I would contact you to ask for more information.

Thank you very much for your consideration.


I would be very interested in the Sparse Matrix - Sparse Matrix multiplication operator, too. nbell, would you mind to post some informations
about it here? I also wanted to ask if there are some considerations of including this operation in the native cuda/cublas library in some
future SDK?

Regards, Janick
Go to the top of the page
 
+Quote Post

4 Pages V   1 2 3 > » 
Reply to this topicStart new topic

 



Copyright 2008 NVIDIA Corporation.  Terms of Use | Legal Info | Privacy Policy Time is now: 22nd November 2009 - 05:11 AM
Unites States Argentina Brazil Chile China Colombia France Germany India Italy Japan Korea Mexico Poland Russia Spain Taiwan United Kingdom Venezuela