Multithreaded sparse matrix multiplication?

5 次查看（过去 30 天）
Thomas
Thomas 2014-8-15
评论： Tri Nguyen 2021-4-29
Dear community,
I am performing several (thousands) matrix multiplications of an NxN sparse (~1-2%) matrix, let's call it B, with an NxM dense matrix, let's call it A (where M<N). N is large, as is M; on the order of several thousands.
Now, usually, matrix multiplications and most other matrix operations are implicitly parallelized in Matlab, i.e. they make use of multiple threads automatically. This appears NOT to be the case if either of the matrices are sparse (see e.g. this StackOverflow discussion and this largely unanswered MathWorks thread). This is a rather unhappy surprise to me. We can verify this by the following code:
clc; clear all;
N = 5000; % set matrix sizes
M = 3000;
A = randn(N,M); % create dense random matrices
B = sprand(N,N,0.015); % create sparse random matrix
Bf = full(B); %create a dense form of the otherwise sparse matrix B
for i=1:3 % test for 1, 2, and 4 threads
m(i) = 2^(i-1);
maxNumCompThreads(m(i)); % set the thread count available to Matlab
tic % starts timer
y = B*A;
walltime(i) = toc; % wall clock time
speedup(i) = walltime(1)/walltime(i);
end
% display number of threads vs. speed up relative to just a single thread
[m',speedup']
This produces the following output, which illustrates that there is no difference between using 1, 2, and 4 threads:
threads speedup
1.0000 1.0000
2.0000 0.9950
4.0000 1.0155
If, on the other hand, I replace B by its dense form, refered to as Bf above, I get significant speedup:
threads speedup
1.0000 1.0000
2.0000 1.8894
4.0000 3.4841
So, my question: is there any way at all to access a parallelized/threaded version of matrix operations for sparse matrices without converting them to dense form? Alternatively, is this something one might expect would be implemented in future versions of Matlab? I found some suggestion involving .mex files here, but it seems the links are dead and not very well documented/no feedback?
It seems to be a rather severe restriction of implicit parallelism functionality, since sparse matrices are abound in computationally heavy problems, and hyperthreaded functionality highly desirable in these cases.
I appreciate anyone's consideration of the this issue at any level - thanks a bunch in advance! -Thomas
  2 个评论
Matt J
Matt J 2014-8-15
Alternatively, is this something one might expect would be implemented in future versions of Matlab?
Future relative to what? What version are you using for these tests?
Thomas
Thomas 2014-8-15
Hi Matt,
Sorry I forgot to include this in my original question; I am using Matlab 2013a.
-Thomas

请先登录，再进行评论。

请先登录，再回答此问题。

回答（2 个）

Eric Sampson
Eric Sampson 2014-8-15
I believe the sparse matrix code is implemented by a few specialized TMW engineers rather than an external library like BLAS/LAPACK/LINPACK/etc. So it will be quite a bit of work for them, but you never know... Send them flowers, candy, etc!! :)
  1 个评论
Thomas
Thomas 2014-8-20
That is rather sad news. Quite a gap in a 'matrix laboratory' :(.
I don't suppose there are any other external libraries that could be matched up with Matlab to take care of this?
Thanks for providing your insight into this matter.

请先登录，再进行评论。

Carlo Monjaraz
Carlo Monjaraz 2018-8-23
In version 2018a, Sparse matrix operations still seem single threaded...

类别

在 Help Center 和 File Exchange 中查找有关 Sparse Matrices 的更多信息

标签

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Translated by