稀疏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>）。

最後，在這兩種情況下，你可以嘗試同時具有行優先和列主要存儲爲稀疏矩陣，並找出哪些稀疏矩陣的戰略和存儲順序的組合最適合你的情況。