CUSPARSE library linking etc.

[danpovey]

@kangshiyin, there is something I need to be done in the 'rnnlm' branch.
We'll need the cuSPARSE library. It will include some changes to the headers and the Makefiles.
Also, there seems to be something called a "library handle" that needs to be initialized, once, at the start of the program, and then supplied to any calls to the cuSPARSE library. This will require some changes to the CuDevice class to initialize the handle and to make it available on request (e.g. in addition to GetHandle(), add a function GetCusparseHandle()).

For your info, in case you want to get a little bit ahead of this specific request, here is where we are going with the sparse-matrix stuff.
We will adding more functionality to the CuSparseMatrix class. Currently it can just add to a dense matrix. We will add functionality including dense += dense * sparse, and (sparse = transpose-of-sparse), and possibly eventually (sparse = sparse * sparse). The way CuSparseMatrix stores its data will be changed, and the "backoff case" (when we're not using CUDA) will be changed, by adding a regular SparseMatrix member to be used for that purpose. We won't be using CuArray any more, or MatrixElement. CuSparseMatrix will be stored in the CSR format, and will contain 3 pointers, although I'm considering only having the first of them actually be allocated, as a single memory region. For "dense += sparse", we might just create a temporary vector of integers and convert to COO format.

Incidentally, unlike the regular (dense) matrices, we will not be having a "transposed view" of the sparse-matrices. That is, the things that CUDA calls the rows, we will call the rows too, as far as sparse matrices are concerned. [Note: above, when I say we'll support dense += dense * sparse, I might have meant dense += dense * sparse^T. There is one case that's efficient and that's the case we need to support.] [Also, note: for sparse = transpose-of-sparse, there is a library function which changes to CSC format, which can be used for that purpose.]

What I have written is just the bottom-line, it doesn't contain the reasoning and the all details. I hope to get to this in more detail soon, but this might be enough for you to get started.

[danpovey]

@kangshiyin, correction to the above...

I just remembered that one of the important operations we support is: trace(dense * sparse).
We'll need to implement in CUDA an operation to gather the relevant elements of a dense matrix (as given by a sparse-matrix structure) into a vector, so we can do a dot-product. I believe that's how the trace operation is currently done. cuSPARSE has a "gthr" (gather) operation for vectors, but , it seems, not for matrices.

Anyway, both that operation and the (dense += sparse) operation require the COO format, and I'm not sure that I want to take the hit of generating the COO format from the CSR format each time we do one of those operations. Something I was considering is, when we create a sparse matrix (e.g. via constructor or Copy() from a CPU-based sparse matrix), is to pass some kind of flag into the constructor that says, "we want to keep around the COO-format indexes for this matrices". So those COO-format indexes would, if we direct, be cached with the CuSparseMatrix, in addition to the CSR-format indexes. For now we could probably have those operations that require the COO-format indexes, crash if they are not present with a suitable error message rather than regenerate themselves. The user would then be forced to add the appropriate constructor flag.

[kangshiyin]

OK, I will start looking into it.

[kangshiyin]

It seems there will be a lot of work, as the storage scheme changes.

I have a few questions.

1. What is the typical sparse pattern and size the sparse matrix? For example if the sparse matrix always have fixed number of non-zero elements per row, we may be able to use some storage format other than CSR to speed up the computation;
2. three pointers in a single memory region - will there be any alignment issue for the 2nd and 3rd pointers?
3. I think CSR may also work for (d+=s) and tr(d * s), so the COO format is not needed. I will take a deeper look of this later.

[danpovey]

1. What is the typical sparse pattern and size the sparse matrix? For example if the sparse matrix always have fixed number of non-zero elements per row, we may be able to use some storage format other than CSR to speed up the computation;

There won't be a fixed number of non-zero elements per row.

1. three pointers in a single memory region - will there be any alignment issue for the 2nd and 3rd pointers?

My understanding is that with newer architectures, these alignment issues are less important. I wanted to avoid having to do 3 copies from main memory to GPU memory.

1. I think CSR may also work for (d+=s) and tr(d * s), so the COO format is not needed. I will take a deeper look of this later.

I don't think tr(d*s) is implemented in CUSPARSE. The way I was planning to do it is to gather the elements of the matrix corresponding to the sparse structure, in a single vector, and do VecVec. Of course this type of thing can be done with CSR too if you write the correct kernel, but I think it's bound to be less efficient. Anyway as long as it works it's probably OK.

[danpovey]

@kangshiyin, do you have any time to work more on this?
I'm starting to get the point, with the RNNLM stuff, where I'm going to start needing to know what the extra sparse-matrix functions look like.
Now, I believe I previously worked out what they would look like, and I think that my description in this 'issue' is mostly sufficient to determine what those functions look like, but it would be very helpful if I could actually see it in black and white.
It's OK for me if, at this point, the new sparse-matrix code is mostly non-functional. One possibility is for you to redesign the internal format of the sparse-matrix class (e.g. to store the CSR format as well as the COO format, and possibly make the COO format optional), but to only get it to the point where the current functionality actually works, and just leave non-working declarations for the new functionality.
BTW I know you have done a lot of stuff for us and we haven't added you on any publications so far. We should definitely be publishing this RNNLM stuff and we'll include you as an author when we do that.

[danpovey]

@kangshiyin, actually I have another idea. I can work out what extra functions are needed, and add declarations for those functions that when called will just crash. Then it will be obvious to you what functionality is needed. That will enable me to continue my work without interruption, and it will give you some clarity about what needs to be supported.

[kangshiyin]

Sounds good. I will send what I have done later today for your reference. I will then focus on implementing the declarations.

[stale]

This issue has been automatically marked as stale because it has not had recent activity. It will be closed if no further activity occurs. Thank you for your contributions.

[stale]

This issue has been automatically closed by a bot strictly because of inactivity. This does not mean that we think that this issue is not important! If you believe it has been closed hastily, add a comment to the issue and mention @kkm000, and I'll gladly reopen it.