2017q1 Homework5(matrix) === contributed by < `jack81306` > ###### tags:`jack81306` ## 開發環境 ``` Architecture: x86_64 CPU 作業模式： 32-bit, 64-bit Byte Order: Little Endian CPU(s): 4 On-line CPU(s) list: 0-3 每核心執行緒數：2 每通訊端核心數：2 Socket(s): 1 NUMA 節點： 1 供應商識別號： GenuineIntel CPU 家族： 6 型號： 60 Model name: Intel(R) Core(TM) i5-4210M CPU @ 2.60GHz 製程： 3 CPU MHz： 2463.049 CPU max MHz: 3200.0000 CPU min MHz: 800.0000 BogoMIPS: 5187.96 虛擬： VT-x L1d 快取： 32K L1i 快取： 32K L2 快取： 256K L3 快取： 3072K NUMA node0 CPU(s): 0-3 ``` ## 閱讀程式碼 #### matrix.h ``` #define DECLARE_MATRIX(col, row) \ typedef struct { float values[col][row]; } Mat ## col ## x ## row ``` * 在 define 中 ## 代表連接,可以把不同變數或字串連接起來,而單一個 # 則是代表是轉為字串.以上程式碼的意義是用 ``` DECLARE_MATRIX(col, row)``` 定義不同大小的矩陣結構. * 程式碼當中的 ```extern MatrixAlgo NaiveMatrixProvider;``` 讓 test_matrix.c 可以讀取到 matrix_naive.c 中的 NaiveMatrixProvider. #### matrix_naive.c * 定義了矩陣的 assign, mul, equal 等實作方式,並將其打包成 MatrixAlgo. #### testmatrix.c * 如果要測試不同的實作方式,只要提供不同的 MatrixAlgo 就可以了. ## 解除限制 * 為了讓矩陣可以自由決定大小,因此用雙重指標來儲存陣列裡的資料. >> 雙重指標一詞，我記得jserv老師說應該稱 "指向指標的指標" > cdecl> explain int **a > declare a as pointer to pointer to int > [name=chihsiang] * 修改了 mul, assign, equal 等方法,這些方法可以根據 matrix 裡的長寬來進行運算和比較. * 要注意 mul 裏面左邊矩陣的 col 要等於右邊矩陣的 row 運算才會成立. * 一樣將方法包裝成 MatrixAlgo ,這樣要新增實作方式一樣只要更改提供的資料就可以了. ## 新增了 avx 和 sse 實作 * 目前 sse 仍然只能處理 4 的倍數矩陣,而 avx 只能處理 8 的倍數矩陣. > 有個問題,要如何 free 掉放在 void* 裡的 float**? ## 轉置 naive * 考慮到因為再乘右邊的矩陣時,因為是一行一行讀取,會產生大量的 cache miss,因此,先把右邊的矩陣進行轉置,之後再乘的時候就可以一列一列讀取,如此就可以降低 cache miss; * 轉置資料 ```clike= for(int i=0;i<MATRIXSIZE;i++){ for(int j=0;j<MATRIXSIZE;j++){ output[j*MATRIXSIZE+i]=data[i*MATRIXSIZE+j]; } } ``` ## 效能分析 * 注意測試資料的隨機範圍,太大可能會 overflow. * 以下為1024*1024的<s>運行</s> 執行時間 ``` naive:14.028386 sse:12.968821 avx:11.449824 naive_transpose:6.029659 ``` :::warning "execute" 的台灣慣用翻譯詞為「執行」，而非「運行」，後者是對岸術語，請尊重傳統文化 --jserv ::: * 這個結果令我十分的感到驚訝,沒想到減少 cache miss 的效能優化居然遠大於 simd. #### 各個矩陣大小的測試資料. #### 各種運算方法的 cache misses * <big>Naive</big> ``` Performance counter stats for './tests/naive': 66,983,683 cache-misses # 88.141 % of all cache refs 75,996,363 cache-references 58,084,537,446 instructions # 1.27 insn per cycle 45,866,493,774 cycles 14.542472807 seconds time elapsed ``` * <big>SSE</big> ``` Performance counter stats for './tests/sse': 68,215,176 cache-misses # 85.206 % of all cache refs 80,058,776 cache-references 49,234,001,424 instructions # 1.08 insn per cycle 45,396,147,390 cycles 14.459807306 seconds time elapsed ``` * <big>AVX</big> ``` Performance counter stats for './tests/avx': 65,359,895 cache-misses # 86.235 % of all cache refs 75,792,685 cache-references 43,991,457,067 instructions # 1.29 insn per cycle 34,081,830,641 cycles 12.200735470 seconds time elapsed ``` * <big>Transpose</big> ``` Performance counter stats for './tests/tran': 2,732,514 cache-misses # 71.331 % of all cache refs 3,830,777 cache-references 58,078,890,203 instructions # 2.19 insn per cycle 26,539,475,851 cycles 8.395667288 seconds time elapsed ``` * 可以發現說 Transpose 的 cache-misses 比 Naive 的 cache-misses 減少許多. * 而 AVX,SSE 比 Naive 的指令數低了許多,但是差別不大的原因是因為這些指令數都包括了產生隨機資料. ## 參考資料 * [define特殊用法](http://kasonblog.blogspot.tw/2012/09/cc-define.html)