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)