我很好奇为什么将稀疏矩阵乘以稠密矩阵所花的时间与反向矩阵所用的时间不同。算法有明显不同吗?
这是Matlab 2018a中的示例:
a=sprand(M,M,0.01);
b=rand(M);
tic;ref1=a*b;t_axb=toc
tic;ref2=b*a;t_bxa=toc
这是使用1个线程的Eigen 3和C++的示例:
//prepare acol=MxM ColMajor Eigen sparse matrix with 0.01 density
...
Map<Matrix<double,M,M,ColMajor> > bcol (PR, M, M );
double tic,toc;
tic=getHighResolutionTime();
result=acol*bcol;
toc=getHighResolutionTime();
printf("\nacol*bcol time: %f seconds", (toc - tic));
tic=getHighResolutionTime();
result=bcol*acol;
toc=getHighResolutionTime();
printf("\nbcol*acol time: %f seconds\n", (toc - tic));
当M = 4000时,结果为:
t_axb =
0.6877
t_bxa =
0.4803
acol*bcol time: 0.937590 seconds
bcol*acol time: 0.532622 seconds
当M = 10000时,结果为
t_axb =
11.5649
t_bxa =
9.7872
acol*bcol time: 20.140380 seconds
bcol*acol time: 8.061626 seconds
在这两种情况下,对于Matlab和Eigen而言,稀疏产品的速度都比稠密产品的速度慢。我很好奇
-fPIC -fomit-frame-pointer -O3 -DNDEBUG -fopenmp -march=native
最佳答案
通过比较稀疏矩阵乘以向量乘积y = A * x
的列主存储和行主存储,可以观察到相同的差异。如果A
是行主要的(等效于y
的每个系数),则可以并行处理A
的每一行,而不会产生任何开销(无需通信,无需额外的临时操作,无需额外的操作)。相反,如果A
是主要列的多线程处理程序是不能免费获得的,那么在大多数情况下,开销要大于 yield 。
即使没有多线程,您也会看到内存访问模式非常不同:
x
的多个随机只读访问,y
的每个系数仅写入一个。 x
的每个系数都读取一次,但是我们对目标y
进行了多次随机读写访问。 因此,即使没有多线程,这种情况自然也适合行优先。
关于matlab - 为什么稀疏-密集乘法比密集-稀疏乘法快?,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/51461429/