# 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 訓練,否則容易造成效能降低.
## 實驗紀錄
### 對原始碼進行測試
* <big>naive</big>
```
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% )
```
* <big>sse</big>
```
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% )
```
* <big>sse_prefetch</big>
```
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的共筆](https://hackmd.io/s/r1IWtb9R) 中得知,perf 中的 event 會隨著處理器架構不同而不同,因此要去 [Intel® 64 and IA-32 Architectures Developer’s Manual: Vol. 3B](http://www.intel.com/content/www/us/en/architecture-and-technology/64-ia-32-architectures-software-developer-vol-3b-part-2-manual.html) 中察看自己的處理器以及想要觀察的事件號碼.
* 以下是想要觀察的事件
* 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 的？
### 重新測試
* <big>naive</big>
```
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%)
```
* <big>sse</big>
```
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% )
```
* <big>sse_prefetch</big>
```
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 會因編譯時使用不同的參數而有不同的實作.
```likec
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
* 根據 [許士傑的共筆](https://embedded2015.hackpad.com/-Homework-7-8-XZe3c94XjUh) 可以理解,每個 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 這條指令讓我來使用,後來發現居然沒有這條指令！！
* 於是後來到了前幾屆的 [共筆](https://embedded2015.hackpad.com/ep/pad/static/VGN4PI1cUxh) 中,找到了 _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 的結果大為不同.
> 為何會有這樣的結果！！？？？
### 比較圖表
## 參考資料
* [PGO](https://www.soft4fun.net/tech/news/google-chome-faster.htm)
Sign in with Wallet
Connect another wallet