HackMD
2017q3 Homework2 (software-pipelining)
contributed by <Lihikoka>
GitHub
開發環境
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：
- 上半部的輸出是分別是轉置前和轉置後的
- 下半部的輸出是分別用三種演算法轉置一個
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：
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：
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 指令的情況下才會執行
如果下 make naive 或 make sse 或 make sse_prefetch 的話則不會執行
main.c 裡也需要做對應的修改，詳見 GitHub
用 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
