HackMD
2017q1 Homework3 (software-pipelining)
contributed by < jack81306 >
tags: jack81306
論文筆記
SW prefetch 優點
-
hw prefetcher 難以處理太複雜的 prefetch,但是 sw prefetch 可以.
-
hw prefetcher 需要 cache missed 來訓練,但是當遇到 short stream 時便難以發揮,此時 sw prefetch 可以處理.
-
sw prefetch 可以很好的處理不規則資料.
-
程式設計者可以自己決定要把資料放到那一層 cache.
- hw prefetch 通常放到 l2 l3 以降低 pollution
-
可以自行判斷回圈是否到底並不超出範圍 prefetch .
SW prefetch 缺點
-
指令數增加
-
不能動態的改變 prefetch distacne
-
當 loop 過小時可能難以插入 prefetch instruction.或者是需要改變結構.
實驗結果
-
指令增加主要是 sw prefatch 的缺點
-
額外的指令除了 prefetch 指令外,還有處理邊界,或者是計算記憶體位子的指令.
-
儘管 gemesftdt 的指令增加超過 50 %,整體效能仍然是增加的,因為 prefetch 所帶來的增益超過指令增加的損失.
-
為了檢測是那種 sw overhead 影響效能最多,分別移除各種造成緩慢的原因進行測試.
-
移除 cache pollution ：造成 cache pollution 的原因有可是過早或錯誤的 prefetch.移除後對實驗並無顯著影響,代表 cache pollution 並非影響效能的主因.
- cache pollution 是指正在執行的程式將不必要的資料從 memory 移到 cache，降低了資料處理效率的現象
-
移除 bandwidth consumption :提升的效能十分的小,代表記憶體頻寬仍然夠用.
-
移除 latency : 提升的效能十分的大！因為 sw prefetch 並沒有完全的把 memory latency 隱藏起來.
-
移除 redundant prefetch : bwaves 受到蠻大的影響,但是影響其他程式效能小到可以忽略不計.
-
移除 instruction overhead :對前面實驗增加最多 instruction 的程式並沒有顯著的增加效能,反倒是 libquantum ,再前面實驗並沒有增加顯著的 instruction,卻再這裡提升非常多的效能.
觀察 prefetch distance 對效能的影響
- 將資料分為五組,並將各個程式對 prefetch distance 的敏感度分配.
static distance vs. machine configure
- static distance 的限制是無法對機器的變化做出最好的距離設定.
使用不同 machine configure 實驗最佳 prefetch distance
-
除了 lbm 其他並無明顯的效能增加.
-
結論： machine configure 對最佳 prefetch distance 的效能並無顯著影響.
Cache-Level Insertion Policy
-
大部分的 cpu 可以容忍 l1 cache missed ,因此 hw prefetcher 通常將資料放到後面一點的 cache ,以免汙染 l1 cache.
-
太多的 l1 cache missed 仍會降低效能.
-
sw prefetch 可以精準的將資料放進 l1 cache.
cache level 實驗
-
實驗使用 T0 cache level hint (也就是將資料放進三層 cache).
-
T0 效能較高是因為降低 l1 cache miss.
-
通常 T0 效能會比其他來的高是因為可降低 l1 cache miss.
hw prefetch 結合 sw prefetch
-
使用 sw prefetch 幫忙訓練 hw prefetch
-
結論： 雖然有些會效能會成長,但是一般通常會造成效能嚴重下降.
-
coverage 太低是造成效率無法提升的原因
使用 gcc 做實驗
-
因為 gcc 不支援 Fortan intrinsic 所以前面都是使用 icc.並將 intrinsic 再編譯後插入.
-
移除使用 fortan 的 benchmark.
-
gcc 插入更多的 sw prefatch 除了 mcf 和 lbm .
-
gcc 無法處理所有的 cache miss ,效能再 nosw 和 sw 之間.
使用真實系統實驗
-
使用 intel core2 和 Nehalem
-
使用全部的程式碼而非只有 simpointed 的部份
simpointed ???
-
除了 milc,gcc,zeusmp 之外,大部分摹擬的程式和整份程式有差不多的 prefetch 指令.
-
模擬系統的配置接近 core2
-
有幾個程式會再真實系統裡效能下降.
-
再 positive group 裡的程式效能都有上升.
-
Nehalem 的 hw prefetch 的效能大於 core2 ,而且,由於 Nehalem 有 mutiple cache level 導致 sw prefetch 的效能增加量下降.
Profile-Guided Optimization
何謂 PGO?
- PGO (Profile Guided Optimization) 是軟體開發中的其中一項最佳化技術，藉由完整程式碼的分析，將常用的程式碼與少用的程式碼進行封裝與拆離，減少因為執行期間 (runtime) 動態連結 (Dynamic Linking) 對執行效率帶來的影響，此外，PGO 技術也最佳化了記憶體使用方式，將常用的功能放入特定記憶體區塊，提高 CPU 指令集快取命中率，進而提升整體執行效能。
PGO 實驗結果
-
PGO 的效能位在 SW prefetch 和 base 之間.
-
PGO 效能的優化不只是 SW prefetch ,還有其他優化方式.
-
PGO 的指令數比 BASE 還少.
Hardware Prefetcher for Short Streams
-
HW prefetch 的缺點是難以處理 short streams.
-
解決辦法 ： ASD HW prefetcher (仍未實作,僅為概念)
-
儘管 ASD 在 short stream 可以比一般的 HW prefetch 還快,但是仍然比 sw prefetch 還要慢.
到底什麼是 asd prefetcher 咧？
Content Directed Prefetching
-
CDP 通常用來處理不規則的資料結構
-
雖然 CDP 有提升這些不規則的資料結構,但是仍然無法超越 SW prefetch (78% 效能提升) 的增益.
看不太懂 CDP 的意思
手動調整 sw prefetch
- 因為我們無法確定程式是不是已經最優化了,因此要窮進手段來對程式進行優化.
- 通常的方法有移除未始用的 prefetch ,調整 prefetch distance ,增加其他的優化技術,如 loop unrolling 和 prologue/epilogue transformations ?
什麼是 prologue/epilogue transformations ？
論文總結
-
sw prefetch 對某些 regular access pattern 比 hw prefetch 更有效率,如 short stream.
-
就算 hw configure 對 prefetch distance 不敏感,仍要小心設定.
-
儘管 ooo cpu 對 la cache missed 容忍率高,但是當l1 cache missed 超過 20% 時 ,可以藉由 prefetch 降低 l1 cache missed 進行優化.
-
無用的 prefetch instruction 對效能不太造成影響.
-
要小心的對 hw prefetch 訓練,否則容易造成效能降低.
實驗紀錄
對原始碼進行測試
- naive
17,142,240 cache-misses ( +- 0.48% )
1,448,569,562 instructions # 1.10 insn per cycle ( +- 0.00% )
1,316,109,257 cycles ( +- 1.23% )
71,907 L1-icache-load-misses ( +- 4.39% )
16,470,337 LLC-load-misses ( +- 0.07% )
0.424526315 seconds time elapsed ( +- 1.25% )
- sse
Performance counter stats for './sse' (5 runs):
4,874,075 cache-misses ( +- 1.74% )
1,236,561,529 instructions # 1.35 insn per cycle ( +- 0.00% )
917,252,607 cycles ( +- 1.34% )
71,434 L1-icache-load-misses ( +- 10.83% )
4,179,530 LLC-load-misses ( +- 0.17% )
0.300347588 seconds time elapsed ( +- 1.61% )
- sse_prefetch
4,678,095 cache-misses ( +- 0.95% )
1,282,795,897 instructions # 1.79 insn per cycle ( +- 0.01% )
715,914,080 cycles ( +- 1.10% )
68,664 L1-icache-load-misses ( +- 9.53% )
4,188,387 LLC-load-misses ( +- 0.21% )
0.232151802 seconds time elapsed ( +- 1.46% )
-
可以從這結果中觀察到,因為 sse 和 sse_prefetch 的 cahce miss 和 instruction 都比 naive 少,因此會使用 sse 的結果會比 naive 快上許多.
-
但是,有疑問的是,sse_prefetch 和 sse 的測試結果差不多,可是時間卻差了將近 0.07 秒.
進一步分析
-
從 kaizsv的共筆 中得知,perf 中的 event 會隨著處理器架構不同而不同,因此要去 Intel® 64 and IA-32 Architectures Developer’s Manual: Vol. 3B 中察看自己的處理器以及想要觀察的事件號碼.
-
以下是想要觀察的事件
-
MEM_LOAD_UOPS_RETIRED.L1_MISS：Retired load uops missed L1 cache as data sources（D1H,08H）
-
MEM_LOAD_UOPS_RETIRED.L2_MISS:Retired load uops missed L2. Unknown data source excluded.(D1H,10H)
-
MEM_LOAD_UOPS_RETIRED.L3_MISS:Retired load uops missed L3. Excludes unknown data source (D1H,20H)
-
不太明白 UOPS 的意義,但就其他的敘述應該可以判斷這些指令是在偵測 L1 L2 L3 cache missed 的？
重新測試
- naive
Performance counter stats for './naive' (5 runs):
16,849,839 cache-misses ( +- 0.19% ) (25.47%)
1,446,964,134 instructions # 1.12 insn per cycle ( +- 1.45% ) (38.36%)
1,296,977,715 cycles ( +- 0.89% ) (50.89%)
74,503 L1-icache-load-misses ( +- 3.57% ) (50.75%)
16,368,952 LLC-load-misses ( +- 0.84% ) (63.21%)
16,407,896 r08d1 ( +- 0.79% ) (60.06%)
15,712,873 r10d1 ( +- 1.90% ) (24.53%)
15,386,702 r20d1 ( +- 1.54% ) (24.90%)
- sse
Performance counter stats for './sse' (5 runs):
4,433,999 cache-misses ( +- 3.76% ) (24.92%)
1,241,345,259 instructions # 1.43 insn per cycle ( +- 1.55% ) (37.90%)
870,806,366 cycles ( +- 1.70% ) (50.51%)
72,335 L1-icache-load-misses ( +- 5.73% ) (51.22%)
4,036,982 LLC-load-misses ( +- 1.85% ) (64.11%)
4,226,923 r08d1 ( +- 1.90% ) (59.56%)
3,997,999 r10d1 ( +- 2.79% ) (24.59%)
3,882,275 r20d1 ( +- 2.22% ) (24.57%)
0.290662977 seconds time elapsed ( +- 1.37% )
- sse_prefetch
4,855,312 cache-misses ( +- 2.83% ) (25.69%)
1,225,977,099 instructions # 1.70 insn per cycle ( +- 1.31% ) (38.77%)
719,123,446 cycles ( +- 0.61% ) (51.44%)
72,674 L1-icache-load-misses ( +- 5.77% ) (51.74%)
4,500,073 LLC-load-misses ( +- 4.51% ) (64.06%)
3,587,506 r08d1 ( +- 2.02% ) (58.10%)
88,901 r10d1 ( +- 28.17% ) (24.16%)
68,986 r20d1 ( +- 56.87% ) (25.29%)
-
測試結果中的 r08d1,r10d1,r20d1 分別是 L1 L2 L3 cache misses 的數量.
-
從增加了判斷 cache miss 在哪一層發生的事件後,可以很明顯的看出來說 sse_prefetch 多半只有發生 L1 cache miss 且大部份都在 L2 cache hit,而 sse 則是發生了許多 L1 L2 L3 cache miss,這應該就是兩者速度差異的原因了
封裝不同的實作及使用相同介面
- 將所有的 implement function 統一命名為 transpose ,並且使用 -D 參數來控制要使用那一個實作.
- 下列程式碼中的 transpose 會因編譯時使用不同的參數而有不同的實作.
struct timespec start, end;
int *src = (int *) malloc(sizeof(int) * TEST_W * TEST_H);
int *out = (int *) malloc(sizeof(int) * TEST_W * TEST_H);
srand(time(NULL));
for (int y = 0; y < TEST_H; y++)
for (int x = 0; x < TEST_W; x++)
*(src + y * TEST_W + x) = rand();
clock_gettime(CLOCK_REALTIME, &start);
transpose(src, out, TEST_W, TEST_H);
clock_gettime(CLOCK_REALTIME, &end);
printf("naive: \t\t %ld us\n", diff_in_us(start, end));
free(src);
free(out);
- 修改 MAKEFILE 使其能分別產生不同的執行檔.
理解 SSE transpose
- 根據 許士傑的共筆 可以理解,每個 int element 為 32-bit，所以 4x4 矩陣的每一個 row 剛好可以打包成 128-bit，再透過高低位的 swap，就可以達到轉置的效果，運作方式如下圖。
使用 avx 進行改寫
-
因為 avx 使用的是 256bit register 因此,對於 int 來說,變成一次要處理 8x8 的矩陣.
-
會使用的指令
- _mm256_unpacklo_epi32
- _mm256_unpacklo_epi64
- _mm256_permute2x128_si256
-
再我第一次寫程式的時候,我原本以為會有 _mm256_unpacklo_epi128 這條指令讓我來使用,後來發現居然沒有這條指令！！
-
於是後來到了前幾屆的 共筆 中,找到了 _mm256_permute2x128_si256 這條指令.
-
這條指令的特別之處是可以藉由第3個參數,來決定 src1 和 src2 的前128 bit 或後 128 bit擺放順序.這樣的化就可以完成轉置矩陣的最後一個步驟.
avx 測試結果
Performance counter stats for './avx':
4,150,618 cache-misses (34.16%)
1,137,217,451 instructions # 1.67 insn per cycle (50.77%)
680,029,146 cycles (50.77%)
951,759 r08d1 (49.98%)
1,084,546 r10d1 (33.36%)
1,197,231 r20d1 (33.12%)
- 可以從這裡觀察出,avx 的 L1 L2 L3 cache misses 落點十分的平均,這和 sse 的結果大為不同.
為何會有這樣的結果！！？？？
比較圖表
