c++ - 稀疏 x 密集矩阵乘法性能效率低下

Question

上下文:我将 Eigen 用于人工神经网络，其中典型维度为每层约 1000 个节点。所以大部分操作是将大小为 ~(1000,1000) 的矩阵 M 与大小为 1000 的 vector 或一批 B vector 相乘，表示为矩阵大小 Bx1000。

训练神经网络后，我使用剪枝 - 这是一种常见的压缩技术，最终得到稀疏矩阵(非空参数的密度在 10% 到 50% 之间)。

目标:我想使用稀疏矩阵进行压缩，其次用于性能优化，但这不是主要目标

问题:我正在比较不同批量大小的稀疏矩阵乘法和密集矩阵乘法(仅计算乘法时间)的性能，我正在观察以下内容(使用 Eigen 3.2.8，MacBook Pro 64 位，不带 open_mp，并使用标准 g++):

• 当 B=1(矩阵 x vector )时 - 密度为 10% 或 30% 的稀疏矩阵运算比密集矩阵运算更有效 - 这似乎是预期的结果:执行的运算要少得多
• 对于 B=32:
  • 密集矩阵运算所需的时间仅为 B=1 所需时间的约 10 倍 - 这很酷 - 它显示出一些矢量化效果吗？
  • 稀疏矩阵运算所需的时间是 B=1 所需时间的 67 - 这意味着它的效率低于独立处理 32 个 vector

MxN multiplication time (ms) for M sparse/dense, and N of size 1000xB

Same numbers but showing the time per vector in a batch of different size for sparse and dense matrix. We see clearly the decrease of time for dense matrix when batch size increase, and the augmentation for sparse matrix showing some wrong. Normalized with time for B=1

代码:我将以下类型用于稀疏和密集矩阵:

typedef SparseMatrix<float> spMatFloat;
typedef Matrix<float, Dynamic, Dynamic, RowMajor> deMatRowFloat;

我要进行基准测试的操作如下:

o.noalias()=m*in.transpose();

其中 o 是一个密集矩阵 (1000xB)，m 是一个密集矩阵 (1000x1000) 或通过 m.sparseView( )，而in是一个稠密矩阵(Bx1000)

完整代码如下(20 个不同随机矩阵的平均时间，每个乘法运算 50 次)- B=32 和 B=1 的时间如下。

欢迎任何反馈/直觉!

---

batch   1   ratio   0.3 dense   0.32    sparse  0.29
batch   32  ratio   0.3 dense   2.75    sparse  15.01

---

#include <Eigen/Sparse>
#include <Eigen/Dense>
#include <stdlib.h>
#include <boost/timer/timer.hpp>

using namespace Eigen;
using namespace boost::timer;

typedef SparseMatrix<float> spMatFloat;
typedef Matrix<float, Dynamic, Dynamic, RowMajor> deMatRowFloat;

void bench_Sparse(const spMatFloat &m, const deMatRowFloat &in, deMatRowFloat &o) {
  o.noalias()=m*in.transpose();
}

void bench_Dense(const deMatRowFloat &m, const deMatRowFloat &in, deMatRowFloat &o) {
  o.noalias()=m*in.transpose();
}

int main(int argc, const char **argv) {
  float ratio=0.3;
  int iter=20;
  int batch=32;
  float t_dense=0;
  float t_sparse=0;

  deMatRowFloat d_o1(batch,1000);
  deMatRowFloat d_o2(batch,1000);
  for(int k=0; k<iter; k++) {
    deMatRowFloat d_m=deMatRowFloat::Zero(1000,1000);
    deMatRowFloat d_b=deMatRowFloat::Random(batch,1000);
    for(int h=0;h<ratio*1000000;h++) {
      int i=rand()%1000;
      int j=rand()%1000;
      d_m(i,j)=(rand()%1000)/500.-1;
    }
    spMatFloat s_m=d_m.sparseView();
    {
      cpu_timer timer;
      for(int k=0;k<50;k++) bench_Dense(d_m,d_b,d_o1);
      cpu_times const elapsed_times(timer.elapsed());
      nanosecond_type const elapsed(elapsed_times.system+elapsed_times.user);
      t_dense+=elapsed/1000000.;
    }
    {
      cpu_timer timer;
      for(int k=0;k<50;k++) bench_Sparse(s_m,d_b,d_o2);
      cpu_times const elapsed_times(timer.elapsed());
      nanosecond_type const elapsed(elapsed_times.system+elapsed_times.user);
      t_sparse+=elapsed/1000000.;
    }
  }
  std::cout<<"batch\t"<<batch<<"\tratio\t"<<ratio<<"\tdense\t"<<t_dense/50/iter<<"\tsparse\t"<<t_sparse/50/iter<<std::endl;
}

ggael 建议后的新结果:我尝试了不同的可能组合，发现在更改 M 和 B RowMajor/时确实存在巨大的性能差异上校。

总而言之，我对 M*B 感兴趣，其中 M 是 (1000,1000) 而 B 是 (1000,batch) :我有兴趣比较 M 稀疏/密集的性能以及批量增长时的性能。

我测试了 3 种配置:

• M密集，B密集
• M稀疏，B密集
• M稀疏，B密集，但是M*B的乘法是逐列手动完成的

结果如下 - 其中数字是 B=32 的每列时间/B=1 的时间与矩阵 M 的比率，密度为 0.3:

最初报告的问题是最糟糕的情况(M ColMajor，B RowMajor)。对于(M RowMajor, B ColMajor)，在B=32和B=1之间有5倍的加速，稀疏矩阵的性能几乎等同于稠密矩阵。

Answer 1

在 Eigen 中，对于密集代数，矩阵- vector 和矩阵-矩阵乘积都经过高度优化，并充分利用了向量化。如您所见，矩阵-矩阵产品表现出更高的效率。这是因为矩阵-矩阵乘积可以通过增加算术运算次数与内存访问次数之间的比率以及利用内存缓存来进一步优化。

然后对于稀疏-密集产品，有两种策略:

1. 一次处理密集的右侧一列，从而多次扫描稀疏矩阵。对于此策略，最好对密集矩阵(右侧和结果)使用列优先存储。在 Eigen 3.2 中，已通过手动扫描列来模拟此策略。
2. 只扫描稀疏矩阵一次，处理密集右侧的行，得到最嵌套的循环。这是 Eigen 3.2 中的默认策略。在这种情况下，最好对密集矩阵 (Matrix<float,Dynamic,32,RowMajor>) 使用行优先存储。

最后，无论哪种情况，您都可以尝试对稀疏矩阵使用行优先和列优先存储，并确定稀疏矩阵的策略和存储顺序的哪种组合最适合您的情况。