为什么稀疏-密集乘法比密集-稀疏乘法更快？

Question

我很好奇为什么将稀疏矩阵乘以稠密矩阵所需的时间与相反的时间不同。算法有明显不同吗？

这是 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，稀疏-密集产品都比密集-稀疏产品慢。我很好奇

1. 为什么会这样？稀疏-密集算法与密集-稀疏算法有显着差异吗？FLOP的数量是一样的，对吧？

2. 为什么 eigen 匹配或超过 Matlab 的密集稀疏性能而不是稀疏密集产品？性能上的微小差异是正常的，但考虑到两者都是高度优化的库，大约 1.4-1.8 的差异似乎很奇怪。我正在根据文档使用所有优化来编译 eigen。IE-fPIC -fomit-frame-pointer -O3 -DNDEBUG -fopenmp -march=native

Answer 1

你可以通过观察比较列，主要与稀疏矩阵向量时代产品行主存储相同的区别：y = A * x。如果A是 row-major（相当于每个 coeff of y），则A可以并行处理 的每一行而没有任何开销（没有通信，没有额外的临时，没有额外的操作）。相比之下，if Ais column-major multi-threading不能免费来，而且在大多数情况下开销大于增益。

即使没有多线程，您也会看到内存访问模式非常不同：

• Row-major：多次随机只读访问x，每个系数y只写一个。
• Col-major：每个 coeff ofx被读取一次，但我们获得了对目的地的多次随机读写访问y。

所以即使没有多线程，这种情况自然也有利于 row-major。