Matlab中的多线程稀疏矩阵乘法

Question

我正在执行NxN稀疏(~1-2%)矩阵的几个矩阵乘法,我们称之为B,使用NxM密集矩阵,我们称之为A(其中M <N).N很大,M也是如此; 大约几千.我正在运行Matlab 2013a.

现在,通常,矩阵乘法和大多数其他矩阵运算在Matlab中隐式并行化,即它们自动使用多个线程.如果任何一个矩阵都是稀疏的,那么看起来并非如此(参见例如StackOverflow讨论 - 没有对预期问题的答案 - 以及这个基本上没有答案的MathWorks线程).这对我来说是一个相当不愉快的惊喜.

我们可以通过以下代码验证多线程对稀疏矩阵操作没有影响:

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']

这会产生以下输出,这表明使用1,2和4个线程进行稀疏操作没有区别:

threads   speedup
1.0000    1.0000
2.0000    0.9950
4.0000    1.0155

另一方面,如果我用密集形式替换B,称之为Bf,我获得了显着的加速:

threads   speedup
1.0000    1.0000
2.0000    1.8894
4.0000    3.4841

(说明Matlab中密集矩阵的矩阵运算确实是隐式并行化的)

所以,我的问题是:有没有办法访问稀疏矩阵的矩阵运算的并行/线程版本(在Matlab中)而不将它们转换为密集形式？我在MathWorks上找到了一个涉及.mex文件的旧建议,但似乎链接已经死了,没有很好的文档/没有反馈？任何替代品？

这似乎是对隐式并行功能的相当严格的限制,因为稀疏矩阵在计算上很重的问题中比比皆是,并且在这些情况下非常需要超线程功能.

Answer 1

MATLAB已经使用了Tim Davis的SuiteSparse来处理稀疏矩阵的许多操作(例如参见这里),但我认为它们都不是多线程的.

通常,稀疏矩阵的计算受内存限制而不是CPU绑定.因此,即使您使用多线程库,我怀疑您会在性能方面看到巨大的好处,至少不能与密集矩阵专用的那些相媲美......

毕竟,稀疏矩阵的设计与常规密集矩阵的目标不同,有效的内存存储通常更为重要.

我在网上做了快速搜索,发现了一些实现:

• 稀疏BLAS,spBLAS,PSBLAS.例如,英特尔 MKL和AMD ACML确实支持稀疏矩阵
• 在GPU上运行的cuSPARSE,CUSP,VexCL,ViennaCL等.

Answer 2

在matlabcentral上也提出了同样的问题，并给出了答案：

I believe the sparse matrix code is implemented by a few specialized TMW engineers rather than an external library like BLAS/LAPACK/LINPACK/etc... 

这基本上意味着，你不走运。

不过我可以想出一些技巧来实现更快的计算：

1. 如果您需要进行多次乘法：一次进行多次乘法并并行处理它们？
2. 如果您只想进行一次乘法：将矩阵分成几部分（例如上半部分和下半部分），并行计算各部分，然后合并结果

这些解决方案可能不会像正确实现的多线程那样快，但希望您仍然可以获得加速。