[求教]MEX優化稀疏矩陣運算選擇

看板MATLAB作者InnocentMage時間7年前 (2017/10/12 01:15)推噓3(3推 0噓 1→)

留言4則, 1人參與討論串1/1

各位版友好: 最近在實作演算法 sub routine 時遇到了效能問題，sub routine 的目標是在給定Z矩陣的情況下，找到最好的W來使得 L(ZW) + C*Tr(W'W)最小，其中Loss function 的長相是 \sum_{(i,j) sample} -R_{ij}log(sigmoid(ZW_{ij}))-(1-R_{ij})log(1-sigmo id(ZW_{ij})), R 是觀察到的資料，取值在{0,1}。C 是 regularization constant. 然後 minimize function 的gradient 會是 ▼W = Z'▼L(ZW)+2CW 資料型態 : Z 會是一個 N*K 的sparse 矩陣， W 會是 K*N 的 dense 矩陣 , R 會是 N*N 的 sparse 矩陣 (只考慮有被抽樣的點), N >>> K, N/K = 10^2~10^3 。當前解法 : 之前已經實作了一個 Z 是 dense 的版本，由 matlab 經由 mex 把資料傳到 C裡，然後我再在C裡使用 liblbfgs library 求解傳回。而我需要做的事就是給定w 求 gradient給liblbfgs,目前的複雜度是 nnz(R)*K (算ZW) + nnz(R)*K (算Z'▼L) + K^2 (算+CW) 現在我有問題的點是我有很多可能的改進方向，不知道該選擇什麼比較好。 (1) 沿用原本的架構，只是將Z是sparse 也考慮進去，再自己利用迴圈實作sparse 矩陣乘法，複雜度應該是 nnz(R)*K*r (evaluate ZW, 其中因為Z的row sparse,在算ZW_ij可能平均起來只要做 rK 次) + nnz(R)*K*r (同理) + K^2 結果 : 速度大概會變快1/r 倍優 : 我只要改改code就好，也不用學新東西缺 : 因為自己實作，不會平行處理，沒有利用到 multi core (2) 在做稀疏矩陣乘法時直接使用類似Intel-MKL 的library 來加速優 : 簡單，之前有修過數值方法，還記得怎麼call API 缺 : 我不太清楚要怎麼使用ICC 來編譯mex file,不知是否相容，可以 mex -setup ICC? 不清楚實際怎麼implement，無法細緻的分析 (3) 交由GPU來計算，不管是在C裡自己寫還是就直接在matlab 裡做，用matlab提供的GPU API 優: 可以很平行的處理?學習GPU運算增強自己的能力XD 缺: 沒有寫過這樣利用GPU去做事的程式，learning curve有點抖，可能需要花很多時間找資料或實作，一樣可能很難分析。 (4) 可能還有其他方法? 或者要進一步考慮Block Algorithm 或 catch affinity 版友覺得應該朝哪個方向努力呢?這個subroutine會很常被call到，效能是非常重要的考量 -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 140.112.218.160 ※ 文章網址: https://www.ptt.cc/bbs/MATLAB/M.1507742158.A.5F3.html

推

sunev

10/12 01:27, 7年前 , 1^F

10/12 01:27, 1^F

抱歉沒有講清楚，由於演算法還在早期研究正確性，目前主要是使用matlab，但為了加快 W求解，所以寫了一個mex function 從 matlab 讀入 Z,W,R 等資料，在這個mex function 處理好變數的傳遞後，會call一個普通的C++ function，然後計算都在上面。 ※ 編輯: InnocentMage (140.112.218.160), 10/12/2017 01:33:06

推

sunev

10/12 01:29, 7年前 , 2^F

10/12 01:29, 2^F

我原本是覺得matlab不夠快，而手邊又有C++的lbfgs solver http://www.chokkan.org/software/liblbfgs/ 所以想把它用mex file 接起來，目前的瓶緊是 lbfgs 每個iteration 算得不夠快，而這個library 需要自己實作evaluate 就是在給定W下gradient 會是啥，所以才想優化這部分。 ※ 編輯: InnocentMage (140.112.218.160), 10/12/2017 01:38:20