稀疏X稠密矩阵乘法性能下高效

Question

上下文：我使用本征人工神经网络，其中典型的尺寸是每层的周围1000个节点。因此，大部分操作是将大小为（1000,1000）的矩阵M与大小为1000的矢量或一批B矢量相乘，其表示为大小为Bx1000的矩阵。

训练神经网络之后，我使用修剪 - 这是一种常见的压缩技术，该技术与稀疏矩阵（在10和50％之间的非空参数密度）结束。

目标：我想用稀疏矩阵压缩的目的，其次为性能优化，但它是不是主要目标

问题： 我比较稀疏和密集矩阵乘法的性能（只有乘法时间被计算），用于不同的批次大小，我观察以下（使用本征3.2.8，MacBook Pro的64位，没有open_mp，并使用标准克++）：

• 当B = 1（矩阵X VEC TOR） - 与密度稀疏矩阵运算的10％或30％的比稠密矩阵运算更有效的 - 这似乎预期的结果：少得多操作被执行
• 为B = 32：
  • 需要密集矩阵的时间操作仅〜10倍为B = 1的时候，需要 - 其是冷的 - 它显示了一些矢量的效果？
  • 需要稀疏矩阵操作的时间是倍所需的B = 1的时间 - 这意味着它比独立地处理32个矢量

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要么是一个致密的基质（1000×1000）或用m.sparseView()和in获得的对应稀疏矩阵是一个密集矩阵（Bx1000）

完整的代码在20个不同的随机矩阵的平均时间，并运行每个乘法50次） - B = 32和B = 1的时间在下面。

欢迎任何反馈/直觉！

---

​​

---

#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/ColMajor时确实发现性能的巨大差异。

总之我有兴趣做M*B其中M是（1000,1000）和B是（1000，批次）：我希望比较的性能中号稀疏/密集，当批量越来越大。

我测试3种配置：

• 中号致密，B致密
• 中号稀疏，B致密
• 中号稀疏，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中，对于密集代数，矩阵向量和矩阵矩阵产品都进行了高度优化，充分利用了矢量化。正如你所观察到的，矩阵矩阵产品展现出更高的效率。这是因为矩阵矩阵产品可以通过增加算术运算和存储器访问次数之间的比率以及利用内存缓存来进一步优化。

然后关于疏密产品，有两种策略：

1. 过程致密右侧一列一次，因此，稀疏矩阵多次扫描。对于这种策略，最好使用密集矩阵的列主存储器（右侧和结果）。在Eigen 3.2中，通过手动扫描列来模拟此策略。
2. 仅扫描稀疏矩阵一次，并处理稠密右侧的行并产生最嵌套的循环。这是Eigen 3.2中的默认策略。在这种情况下，最好使用密集矩阵的行主存储器（Matrix<float,Dynamic,32,RowMajor>）。

最后，在这两种情况下，你可以尝试同时具有行优先和列主要存储为稀疏矩阵，并找出哪些稀疏矩阵的战略和存储顺序的组合最适合你的情况。