[SciPy-Dev] Multithreading sparse matrix to dense vector(s) multiplication

[Jorge Guerra]

Thank you for the responses. I can see the problem with overloading the
multiplication "*" operator and the dot() method. As for the algorithm
itself, what I'm proposing would only allow for multiple rows of the sparse
matrix to be computed on simultaneously without addressing any of the
underlying issues identified in the reference
http://www.cslab.ece.ntua.gr/~nkoziris/papers/pdp08understanding.pdf.

I'm aware that this would not be an optimal solution, but naively it should
provide some improvement in my opinion. At least it is worth investigating.
I know Matlab is able to do this with multithreading with the use of an
external library... although I have not been able to reverse engineer which
and how that is implemented. Maybe it is in their use of SuiteSparse, but
I'm not sure.

I'm going to work on a verification and I'll have to learn pThreads it
seems. Thank you all,

Jorge


On Mon, Mar 16, 2020 at 12:44 PM Gregory Lee <grlee77 at gmail.com> wrote:

>
>
> On Mon, Mar 16, 2020 at 12:56 PM Jorge Guerra <jeguerra at ucdavis.edu>
> wrote:
>
>> Hello everyone,
>>
>> I'm quite new to the SciPy development community. I've identified a
>> potential improvement that would be very helpful:
>>
>> in scipy/sparse/sparsetools/csr.h @ lines 1092 and 1129 in the
>> csr_matvec() and mat_vecs() methods I would like to parallelize the outer
>> for loop over the rows of the input sparse matrix. The current serial code
>> looks just about optimal, but should take advantage of a multicore machine.
>> This is a place where SciPy is deficient.
>>
>>
> Welcome,
>
> Have you tried this to verify that you do indeed get a performance
> improvement with multithreading? I seem to recall sparse matrix-vector
> mulitiplication is more difficult to accelerate than dense matrix-vector
> multiplication because it tends to be memory bound. A quick search just now
> turned up the following paper that discusses some of the difficulties
> involved:
> http://www.cslab.ece.ntua.gr/~nkoziris/papers/pdp08understanding.pdf
>
>
>
>> Going through the compilation, SciPy depends on pThreads. However, my
>> proposed change would be trivial by including OpenMP, but I don't
>> necessarily want to add to the overall dependencies.
>>
>> Would anyone more familiar with pThreads be willing to collaborate with
>> me to accomplish this proposed task? Or perhaps advice on an alternative to
>> get multithreaded sparse matrix to dense vector multiplication implemented?
>>
>> Thank you all!
>>
>> Jorge
>>
>> --
>> *Jorge E. Guerra, PhD.*
>> *Research Scientist, CIMMS/NOAA*
>> *Earth Systems Research Laboratory, Boulder, CO*
>> _______________________________________________
>> SciPy-Dev mailing list
>> SciPy-Dev at python.org
>> https://mail.python.org/mailman/listinfo/scipy-dev
>>
> _______________________________________________
> SciPy-Dev mailing list
> SciPy-Dev at python.org
> https://mail.python.org/mailman/listinfo/scipy-dev
>


-- 
*Jorge E. Guerra, PhD.*
*Research Scientist, CIMMS/NOAA*
*Earth Systems Research Laboratory, Boulder, CO*
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/scipy-dev/attachments/20200316/a7e6cb24/attachment.html>