thưa thớt x hiệu suất nhân bản ma trận dày đặc dưới hiệu quả

Question

Bối cảnh: Tôi đang sử dụng Eigen cho mạng nơron nhân tạo với kích thước điển hình khoảng 1000 nút trên mỗi lớp. Vì vậy, hầu hết các hoạt động là nhân ma trận M kích thước ~ (1000,1000) với một vectơ có kích thước 1000 hoặc một lô B vectơ, được biểu diễn dưới dạng ma trận kích thước Bx1000.

Sau khi đào tạo mạng nơron, tôi đang sử dụng cắt xén - một kỹ thuật nén phổ biến kết thúc với ma trận thưa thớt (mật độ của tham số không trống giữa 10 và 50%).

Goal: Tôi muốn sử dụng ma trận thưa thớt cho mục đích nén và secondarily để tối ưu hóa hiệu suất nhưng nó không phải là mục tiêu chính

Issue: tôi so sánh hiệu suất của thưa thớt và rậm rạp nhân ma trận (chỉ có thời gian nhân được tính) đối với kích thước hàng loạt khác nhau và tôi đang quan sát như sau (sử dụng Eigen 3.2.8, MacBook Pro 64bits, không open_mp, và sử dụng g tiêu chuẩn ++):

• khi B = 1 (Matrix x Vec tor) - hoạt động ma trận thưa thớt với mật độ 10% hoặc 30% là hiệu quả hơn các hoạt động ma trận dày đặc - mà dường như kết quả mong đợi: hoạt động ít được thực hiện
• cho B = 32:
  • thời gian cần thiết cho ma trận dày đặc hoạt động chỉ gấp 10 lần thời gian cần cho B = 1 - điều này thật tuyệt vời - nó có cho thấy một số hiệu ứng vector hóa không?
  • thời gian cần thiết cho hoạt động ma trận thưa thớt là lần so với thời gian cần thiết cho B = 1 - có nghĩa là nó là kém hiệu quả hơn so với xử lý 32 vectơ độc lập

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

Mã: Tôi đang sử dụng các loại sau cho thưa thớt và dày đặc các ma trận:

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

hoạt động Tôi benchmarking như sau:

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

nơi o là một ma trận dày đặc (1000xB), m hoặc là một ma trận dày đặc (1000x1000) hoặc ma trận thưa thớt tương ứng thu được với m.sparseView() và in là một ma trận dày đặc (Bx1000)

Một mã đầy đủ dưới đây (trung bình thời gian cho 20 ma trận ngẫu nhiên khác nhau và chạy từng phép nhân 50 lần) - thời gian cho B = 32 và B = 1 là dưới đây.

Mọi phản hồi/trực giác đều được chào đón!

---

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; 
} 

Kết quả mới sau ggael gợi ý: Tôi đã thử các kết hợp khác nhau càng tốt và tìm thấy thực sự khác biệt rất lớn của các hoạt động khi thay đổi M và B RowMajor/ColMajor.

Để tóm tắt tôi quan tâm đến việc thực hiện M*B trong đó M là (1000,1000) và B là (1000, lô): Tôi muốn so sánh hiệu suất của M thưa thớt/dày đặc và khi lô đang phát triển.

Tôi đã thử nghiệm 3 cấu hình:

• M dày đặc, B dày đặc
• M thưa thớt, B dày đặc
• M thưa thớt, B dày đặc, nhưng nhân của M * B được thực hiện bằng tay cột theo cột

Kết quả như sau - nơi số là lần tỷ lệ cho mỗi cột cho B = 32/thời gian cho B = 1 với ma trận M với mật độ 0,3:

Vấn đề được báo cáo ban đầu là trường hợp xấu hơn (M ColMajor, B RowMajor). Đối với (M RowMajor, B ColMajor), có tốc độ tăng gấp 5 lần giữa B = 32 và B = 1 và hiệu suất của ma trận thưa thớt gần như tương đương với ma trận dày đặc.

Answer 1

Trong Eigen, đối với đại số dày đặc, cả ma trận-vector và ma trận-ma trận sản phẩm được tối ưu hóa cao và tận dụng tối đa vectorization. Như bạn đã quan sát, các sản phẩm ma trận ma trận thể hiện hiệu quả cao hơn nhiều. Điều này là do các sản phẩm ma trận ma trận có thể được tối ưu hóa thêm bằng cách tăng tỷ lệ giữa số hoạt động số học và truy cập bộ nhớ, và bằng cách khai thác bộ nhớ cache.

Sau đó, liên quan đến sản phẩm thưa thớt-dày đặc, có hai chiến lược:

1. Process dày đặc ngay phía bên tay một cột cùng một lúc, và do đó quét ma trận thưa thớt nhiều lần. Đối với chiến lược này, tốt hơn sử dụng một lưu trữ cột lớn cho các ma trận dày đặc (bên phải và kết quả). Trong Eigen 3.2, chiến lược này đã được mô phỏng bằng cách quét các cột theo cách thủ công.
2. Quét ma trận thưa thớt chỉ một lần và xử lý các hàng của cạnh bên phải dày đặc và dẫn đến vòng lặp lồng nhau nhiều nhất. Đây là chiến lược mặc định trong Eigen 3.2. Trong trường hợp này, sử dụng tốt hơn dung lượng lưu trữ hàng lớn cho các ma trận dày đặc (Matrix<float,Dynamic,32,RowMajor>).

Cuối cùng, trong cả hai trường hợp, bạn có thể thử với cả một kho hàng-lớn và cột lớn đối với ma trận thưa thớt, và tìm ra sự kết hợp của chiến lược và trật tự lưu trữ của ma trận thưa thớt hoạt động tốt nhất trong trường hợp của bạn .