2017q3 Homework2 (software-pipelining) === contributed by <`Lihikoka`> [GitHub](https://github.com/Lihikoka/prefetcher) # 開發環境 ``` Linux 4.8.0-53-generic Linux Mint 18.2 Cinnamon 64-bit Model name: Intel(R) Core(TM) i7-3770 CPU @ 3.40GHz L1d cache: 32K L1i cache: 32K L2 cache: 256K L3 cache: 8192K ``` # 執行程式 編譯後執行程式，結果如下： ``` 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 0 4 8 12 1 5 9 13 2 6 10 14 3 7 11 15 sse prefetch: 50699 us sse: 99797 us naive: 208990 us ``` 閱讀程式碼後發現這支程式是在做矩陣的轉置 (transpose) ，共實作了三種演算法，分別為 `naive_transpose` 、 `sse_transpose` 和 `sse_prefetch_transpose` 。 共分成兩個 block： * 上半部的輸出是分別是轉置前和轉置後的 $4 \times 4$ 矩陣 * 下半部的輸出是分別用三種演算法轉置一個 $4096 \times 4096$ 的矩陣所需的時間。 ## naive_transpose 用兩個 for 迴圈將輸入矩陣的 (i, j) 元素放到輸出矩陣的 (j, i) 元素。 ## sse_transpose & sse_prefetch_transpose SSE ： Streaming SIMD Extensions SIMD ： Single Instruction Multiple Data streams AVX ： Advanced Vector Extensions SSE 和 AVX 是 Intel 和 AMD 所支援的 SIMD 指令集，可以用一個指令操作多個資料。 線性代數的運算若用 SIMD 指令集來實現會比使用 for 迴圈來得快，尤其是在向量、矩陣的維度大幅增加的時候。 # 以物件導向的方式封裝轉置矩陣的不同實作 原始程式碼直接在 `main.c` 中揭露了函式的名稱 (naive_transpose, sse_transpose, sse_prefetch_transpose) ，為了符合物件導向的精神，我們先在 `main.c` 中定義一個 array of function pointer： ```clike= void (*transpose[3]) (int *src, int *dst, int w, int h) = { &naive_transpose, &sse_transpose, &sse_prefetch_transpose }; enum {NAIVE, SSE, SSE_PREFETCH}; ``` 接著可以用以下的方式呼叫不同的 `transpose` function： ```clike= transpose[NAIVE](src, out1, TEST_W, TEST_H); transpose[SSE](src, out1, TEST_W, TEST_H); transpose[SSE_PREFETCH](src, out0, TEST_W, TEST_H); ``` Makefile 修改成以下 (僅顯示部份)： ``` all: $(GIT_HOOKS) main.c $(CC) $(CFLAGS) -o main main.c -DVER="ALL" naive: main main.c impl.c $(CC) $(CFLAGS) -o main_naive main.c -DVER="NAIVE" sse: main main.c impl.c $(CC) $(CFLAGS) -o main_sse main.c -DVER="SSE" sse_prefetch: main main.c impl.c $(CC) $(CFLAGS) -o main_sse_prefetch main.c -DVER="SSE_PREFETCH" ``` 只有下 `make all` 指令的情況下才會執行 $4\times4$ 矩陣的 demo。 如果下 `make naive` 或 `make sse` 或 `make sse_prefetch` 的話則不會執行 $4\times4$ 矩陣的 demo ，並且在第二個 block 只會執行對應的演算法，這麼作的原因是為了方便作效能分析。 `main.c` 裡也需要做對應的修改，詳見 [GitHub](https://github.com/Lihikoka/prefetcher/commit/4c8be380005cbcb1c3825ba3b6f3b1f1f18b7fb1#diff-2045016cb90d1e65d71c2407a2570927) # 用 perf 分析 cache miss/hit 修改 `Makefile` 以使得可以執行 `make cache-test` 來進行 cache 的效能分析，執行結果如下： ``` perf stat --repeat 10 \ -e cache-misses,cache-references,instructions,cycles \ ./main_naive Performance counter stats for './main_naive' (10 runs): 1860,8464 cache-misses # 92.706 % of all cache refs ( +- 0.03% ) 2007,2615 cache-references ( +- 0.01% ) 14,4845,8774 instructions # 1.09 insn per cycle ( +- 0.00% ) 13,2383,6389 cycles ( +- 0.23% ) 0.385407953 seconds time elapsed ( +- 1.79% ) ``` ``` perf stat --repeat 10 \ -e cache-misses,cache-references,instructions,cycles \ ./main_sse Performance counter stats for './main_sse' (10 runs): 630,9362 cache-misses # 84.354 % of all cache refs ( +- 0.06% ) 747,9648 cache-references ( +- 0.04% ) 12,3647,0737 instructions # 1.38 insn per cycle ( +- 0.00% ) 8,9793,5831 cycles ( +- 0.21% ) 0.277672883 seconds time elapsed ( +- 3.64% ) ``` ``` perf stat --repeat 10 \ -e cache-misses,cache-references,instructions,cycles \ ./main_sse_prefetch Performance counter stats for './main_sse_prefetch' (10 runs): 631,4183 cache-misses # 84.295 % of all cache refs ( +- 0.02% ) 749,0553 cache-references ( +- 0.06% ) 12,8257,1507 instructions # 1.83 insn per cycle ( +- 0.00% ) 6,9954,8363 cycles ( +- 0.25% ) 0.234844431 seconds time elapsed ( +- 5.05% ) ``` ## Cache-misses * naive_transpose ： 92.706 % * sse_transpose ： 84.354 % * sse_prefetch_transpose ： 84.295 % 預期使用 sse_prefetch_transpose 的話 cache-misses 應該要比使用 sse_transpose 低才對，但結果非然。 ## IPC (Instruction per cycle) * naive_transpose ： 1.09 * sse_transpose ： 1.38 * sse_prefetch_transpose ： 1.83