# 2017q3 Homework2 (software-pipelining) contributed by <`ZixinYang`> ### Reviewed by `st9007a` - 在 **prefetch 程式碼測試與討論**中的**開發環境**的部分可以附上電腦 cpu 的資訊，可以讓讀者驗證後面使用 raw counter 的 event - 在 **prefetch 程式碼測試與討論**中的 **sse** 的部分，`Key point: 一次將4筆資料放入sse暫存器中，執行一條指令就可以完成4筆資料處理。`，這句敘述不精確，如果今天一筆資料大小不為 32-bit 時無法套用你的 Key Point - 承上，在 **avx** 中，`AVX 的暫存器是 256-bit，一次可以讀取 8 筆資料`，這句敘述不夠精確 - 在 **prefetch 程式碼測試與討論**中的 **sse** 的部分，解釋程式碼的部分過於精簡，什麼是該互換的值，什麼是正確的位置，雖然可以從轉置矩陣這個概念得知，但是還是沒有解釋到 unpack 的具體功能 - 在 **prefetch 程式碼測試與討論**中的 **sse prefetch** 的部分，提到`不同的 prefetch 指令則是告訴 CPU 將資料載入不同層次的 cache`，應改成 `不同的 prefetch hint` - 在 **prefetch 程式碼測試與討論**中，使用 raw counter 查看 L1 跟 L2 cache 相關資訊後，應解釋數據 - 在 **prefetch 程式碼測試與討論**中，可以說明選擇 raw counter 的 event 的原因 - 應比較執行速度，不同方法的執行速度是有差的，並用統計學來分析 - 應比較不同 prefetch distance 對執行效能的影響 - 在 commit [2db50c97](https://github.com/ZixinYang/prefetcher/commit/2db50c973ecc3217c1c3cdb563088da3414de80d) 中，commit message 的敘述有問題，`Modify main.c to run 3 functions independently`，所以這三個 functions 原本有相依關係 ? - 在 commit [d7bb47d5](https://github.com/ZixinYang/prefetcher/commit/d7bb47d5bdef048fccea4fdf6fc299d4b0e2c006) 中，commit message 與 [2db50c97](https://github.com/ZixinYang/prefetcher/commit/2db50c973ecc3217c1c3cdb563088da3414de80d) 一模一樣，但是這個 commit 中的改動與 commit message 沒有關聯 - 執行檔不應進 github：[naive_transpose](https://github.com/ZixinYang/prefetcher/blob/master/naive_transpose)，保持 repo 簡潔 ## 閱讀論文並記錄 論文連結: [When Prefetching Works, When It Doesn’t, and Why](https://www.cc.gatech.edu/~hyesoon/lee_taco12.pdf) ### Abstract * 為了達到效能提升, 現代處理器重視如何包容 cache miss latency, 以及如何管理記憶體。 * 此篇論文的目標在於分析 HW 及 SW prefetching 的好處及限制。 * 開放程式碼, 包含分析了 HW 及 SW pretching 之間的 synergistic 和 antagonistic 效應, 並運用在真實系統上實驗。 ### Introduction * 許多研究中提出了 HW 及 SW 的機制, 但只有少數相對簡單的演算法被應用在 compiler 中 (icc, gcc), 通常需要手動安插 prefetching intrinsics 以提升效能。 * 存在的問題: * 目前沒有最佳安插 prefetching intrinsics 的方法被提出。 * 對 HW & SW prefetching 之間的關係不理解 * 利用以下圖表, 呈現 HW 及 SW prefetching 的互動關係: ![](https://i.imgur.com/qZbAZnz.png) 左 y 軸為執行時間 x 軸為各種 benchmarks GHB 及 STR 皆為 HW prefetching 的方法 圖表中依照 SW 加上 HW prefetching 所 speed up 的程度分成 Positive, Neutral 及 Negative 三個區塊 ***從此圖可以推測效能提升跟 benchmark 有很直接的關係*** * 過去研究的論述 * 當 SW prefetching 針對 short array streams, irregular memory address patterns 及 L1 cache miss reduction, 會對提升效能有很大的幫助。 * HW prefetching 會對 SW prefetching 造成干擾, 使效能下降。 ### Background * 下圖為過去研究提出用在 prefetching 對應的資料結構: ![](https://i.imgur.com/S14JOte.png) * 連續的資料結構會較容易 prefetch, 不連續的資料結構則較困難, 所以 HW 及 SW prefetching 的機制用在較複雜的資料結構上預測 cache miss address 的方法不斷被提出。 * Notations * Streams: unit-stride cache-line accesses * Strided: access stride distances greater than two cache lines * Software Prefetch Intrinsics `手動安插 intrinsics 的策略提示` ![](https://i.imgur.com/M7gfJlz.png) * Prefetch Classification `prefetch 要求分成六類` ![](https://i.imgur.com/pqLUVte.png) * Software Prefetch Distance * prefetching request 要在有足夠時間隱藏 memory latency 的情況下才有效。 ![](https://i.imgur.com/jj8zEkD.png) * Prefetch distance D: prefetch request 需預留的距離。 * D $\geq$ $\frac{l}{s}$ * l: prefetch latency * s: loop body 中的最短路徑 * l, s 皆會隨時間變動 * D 足夠大時就可以做 prefetch * 但若 D 太大, 有用的 cache blocks 可能被踢出, 導致無法收斂造成 cache misses。 * Direct and Indirect Memory Indexing * Direct memory indexing 較容易被 HW prefetch, 而 indirect 則需要特殊的機制。 * Indirect memory indexing 相對 direct 在 SW 計算上較有效率, 所以 indirect 應專注在 SW prefetching。 * Indirect memory indexing 需要較多的 load instructions, 如下圖: ![](https://i.imgur.com/GbPgPM0.png) ### Positive and Negative Impacts of Software Prefetching 這部份主要在闡述相對 HW prefetching, SW prefetching 的優缺點, 及兩者互相影響的效應。 * Positive impacts * Large number of streams: HW prefetechers 受硬體容量所限制, SW prefetchers 則可獨立安插 request。 * Short streams: HW prefetchers 需要訓練時間來偵測方向及 stream 或 stride 的距離, 所以如果 stream 長度太短, HW prefetchers 就會來不及找到有用的 cache, SW prefetchers 則不受此限。 * Irregular memory access: SW prefetchers 可以在各種不連續的資料結構上安插 prefetch intrincics * Cache locality hint: 一般 HW prefetchers 將資料存在 L2 或 L3 cache, 而 L2 到 L1 的延遲會造成嚴重影響效能, 反之 SW prefetchers 可以較彈性地將資料存放在適當的 level * Loop bound: 可以很容易地在 array 資料結構中決定 loop bounds, 且一些方法會避免在其他結構上產生 prefetch requests * Negative impacts * Increased instruction count: SW prefetchers 需要動用較多資源。 * Static insertion: 程式設計者或編譯器決定哪一筆資料要 prefetch 以及 pretch 的距離, 所以不容易適應記憶體延遲的變化。 * Code structure change: 如果 loop 中的指令數太小, SW prefetchers 很難安插 requests, 所以需要改變程式結構, 那就會增加多餘的指令, 導致 prefetch 更加困難。 ``` 從以上的優缺點來看, 會想到或許 SW 與 HW 的結合可以保留 SW 的優點, 避免 SW 的缺點， 所以接下來就要討論兩者的互動。 ``` * Synergistic effects * Handling multiple streams: SW 負責不連續的資料, HW 負責連續的資料。 * Positive training: 當 SW prefetcher 延遲了, 可能幫助 HW prefetcher 訓練。 * Antagonistic effects * Negative training: SW prefetcher 截到的 blocks 隱藏了一部份的串流, HW prefetcher 就很難訓練好, 或是 SW prefetcher 或刺激 HW prefetcher 導致提早丟出 request。 * Harmful software prefetching: 通常 SW prefetcher 會表現地比 HW prefetcher 好, 所以如果 SW prefetcher 表現地很差時,　會增加 cache 的負擔而造成 HW prefetcher 表現的效能也下降。 ### Experimental Methodology * Prefetch intrinsic insertion algorithm * Prefetch candidate: L1 MPKI 大於 0.05 的區塊。 * 對每個 candidate 安插 SW prefetch。 * Distance: $\frac{K\times L \times IPC \ _ {bench}}{W \ _ {loop}}$ * Simulation methodology `處理器配置` ![](https://i.imgur.com/u0Bo99T.png) `每個 benchmark 的特徵值` ![](https://i.imgur.com/cn9SFSO.png) ### Evaluation * Overhead and Limitations of SW Prefetching * Instruction overhead ![](https://i.imgur.com/r5c1nHG.png) SW prefetchers 造成的指令增加, 不只是來自 prefetch 指令, 還有處理 indirect memory access 和 index 計算。 * SW prefetch overhead ``` 下圖去除掉某些情況的處理時間 P: no pollution, B: no bandwidth, L: no latency, R: eliminate redundant prefetch overhead, I: eliminate instructions overhead ``` ![](https://i.imgur.com/n3Zr7dZ.png) cache pollution: 發生在提早或是錯誤的 prefetch, 由此可見實驗中很少出現此情況。 bandwidth: 去除後影響也不大, 表示 machine 提供了足夠的 bandwidth latency: 影響較大, 表示 prefetch 的效果沒有完全隱藏延遲的狀況。 redundant prefetch overhead: 儘管有大量多餘的 prefetch instructions, 但結果意外地影響並不大。 instructions overhead: 對某些 benchmarks 來說影響很小。 * The effect of prefetch distance `下圖呈現 prefetch distance 對效能的影響` ![](https://i.imgur.com/7OIyXjj.png) `基於上圖的曲線, 將 benchmark 分成五類, 從敏感度高排到低` ![](https://i.imgur.com/DKnz9t8.png) 這個實驗發現大部分 neutral 及 negative 的 benchmark 屬於 insensitive * Effect of Using HW and SW Prefetching together * Apply two HW training policies: * NT (SW+GHB, SW+STR): HW ignore SW's requests * Train (SW+GHB+T, SW+STR+T): training includes SW's requests ![](https://i.imgur.com/Z4aBUwh.png) 從圖中可看出雖然利用 SW prefetch requests 訓練 HW prefetchers 對某些 benchmark 可以帶來好處, 但整體來說負面影響還是較大的。 * Summary of New Findings * 在處理 regular access patterns 時, 若資料是 short stream, 用 SW prefetch 反而更有效率。 * SW prefetch distance 對 HW 組態較不敏感。 需要好好設定 prefetch distance, 但只要 prefetch distance 大於最小距離, 效能就不會差太多。 * 雖然大部分的 L1 cache misses 會被 out-of-order 執行的處理器容忍，但在 L1 cache misses 太大時 (> 20 %)，還是採取 prefetch 降低 L1 cache misses 對效能的提升比較有效率。 * 大部分有 prefetch instruction 的應用也同時會遇到 memory operation 的限制，因此在 SW prefetching 中，instruction overhead 對效能的影響並不是很大。 * SW prefetching 可以用來訓練 HW prefetcher 因此能夠獲得效能上的提升。但是在有些情況中，也可能因此造成效能嚴重下降，必須小心使用。 ## prefetch 程式碼測試與討論 * 開發環境 ``` Linux 4.10.0-35-generic Ubuntu 16.04.1 LTS L1d cache: 32K L1i cache: 32K L2 cache: 256K L3 cache: 6144K ``` * 原始程式碼執行結果 ``` 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: 50777 us sse: 120415 us naive: 222326 us ``` 檢視 main.c 程式碼可知, 執行結果的上半段是做矩陣的 transpose, 作法單純是將 row 跟 column 的值互換。 下半段列了三種 tranpose 的方法, 並分別印出執行的時間。 接著我們在檢視三個 function 的內容 * naive ```clike= void naive_transpose(int *src, int *dst, int w, int h) { for (int x = 0; x < w; x++) for (int y = 0; y < h; y++) *(dst + x * h + y) = *(src + y * w + x); } ``` 為最簡單的方法, 傳入原本的矩陣指標, 要用來存新的矩陣的指標及矩陣的大小。 在 function 裡面執行 row 跟 column 互換。 * sse ```clike= void sse_transpose(int *src, int *dst, int w, int h) { for (int x = 0; x < w; x += 4) { for (int y = 0; y < h; y += 4) { __m128i I0 = _mm_loadu_si128((__m128i *)(src + (y + 0) * w + x)); __m128i I1 = _mm_loadu_si128((__m128i *)(src + (y + 1) * w + x)); __m128i I2 = _mm_loadu_si128((__m128i *)(src + (y + 2) * w + x)); __m128i I3 = _mm_loadu_si128((__m128i *)(src + (y + 3) * w + x)); __m128i T0 = _mm_unpacklo_epi32(I0, I1); __m128i T1 = _mm_unpacklo_epi32(I2, I3); __m128i T2 = _mm_unpackhi_epi32(I0, I1); __m128i T3 = _mm_unpackhi_epi32(I2, I3); I0 = _mm_unpacklo_epi64(T0, T1); I1 = _mm_unpackhi_epi64(T0, T1); I2 = _mm_unpacklo_epi64(T2, T3); I3 = _mm_unpackhi_epi64(T2, T3); _mm_storeu_si128((__m128i *)(dst + ((x + 0) * h) + y), I0); _mm_storeu_si128((__m128i *)(dst + ((x + 1) * h) + y), I1); _mm_storeu_si128((__m128i *)(dst + ((x + 2) * h) + y), I2); _mm_storeu_si128((__m128i *)(dst + ((x + 3) * h) + y), I3); } } } ``` 先查一下什麼是 [SSE](https://www.csie.ntu.edu.tw/~r89004/hive/sse/page_1.html) `Key point: 一次將4筆資料放入sse暫存器中，執行一條指令就可以完成4筆資料處理。` 因此 for 迴圈使用的變數可以一次增加 4, 處理上速度較快。 接著查詢 [intel intrinsics guide](https://software.intel.com/sites/landingpage/IntrinsicsGuide/#techs=SSE,SSE2,SSE3,SSE4_1,SSE4_2&expand=3162)， 了解程式碼中每個 intrinsics function 的作用 簡單來說, load 是用來載入 src 的資料, 一連串的 unpack 把該互換的值放在正確的位置, store 再將 unpack 的結果存回 dst * sse prefetch ```clike= void sse_prefetch_transpose(int *src, int *dst, int w, int h) { for (int x = 0; x < w; x += 4) { for (int y = 0; y < h; y += 4) { #define PFDIST 8 _mm_prefetch(src+(y + PFDIST + 0) *w + x, _MM_HINT_T1); _mm_prefetch(src+(y + PFDIST + 1) *w + x, _MM_HINT_T1); _mm_prefetch(src+(y + PFDIST + 2) *w + x, _MM_HINT_T1); _mm_prefetch(src+(y + PFDIST + 3) *w + x, _MM_HINT_T1); __m128i I0 = _mm_loadu_si128 ((__m128i *)(src + (y + 0) * w + x)); __m128i I1 = _mm_loadu_si128 ((__m128i *)(src + (y + 1) * w + x)); __m128i I2 = _mm_loadu_si128 ((__m128i *)(src + (y + 2) * w + x)); __m128i I3 = _mm_loadu_si128 ((__m128i *)(src + (y + 3) * w + x)); __m128i T0 = _mm_unpacklo_epi32(I0, I1); __m128i T1 = _mm_unpacklo_epi32(I2, I3); __m128i T2 = _mm_unpackhi_epi32(I0, I1); __m128i T3 = _mm_unpackhi_epi32(I2, I3); I0 = _mm_unpacklo_epi64(T0, T1); I1 = _mm_unpackhi_epi64(T0, T1); I2 = _mm_unpacklo_epi64(T2, T3); I3 = _mm_unpackhi_epi64(T2, T3); _mm_storeu_si128((__m128i *)(dst + ((x + 0) * h) + y), I0); _mm_storeu_si128((__m128i *)(dst + ((x + 1) * h) + y), I1); _mm_storeu_si128((__m128i *)(dst + ((x + 2) * h) + y), I2); _mm_storeu_si128((__m128i *)(dst + ((x + 3) * h) + y), I3); } } } ``` 這個 function 的程式碼增加了 prefetch 的指令, 在 load 資料之前, prefetch 了往後數 PFDIST + 0 ~ 3 個 row 的資料並且放置到 L2 以及更高階的 cache 上 > prefetch 指令的主要目的，是提前讓 CPU 載入稍後運算所需要的資料。 通常是在對目前的資料進行運算之前，告訴 CPU 載入下一筆資料。 這樣就可以讓目前的運算，和載入下一筆資料的動作，可以同時進行。 如果運算的複雜度夠高的話，這樣可以完全消除讀取主記憶體的 latency。 不同的 prefetch 指令則是告訴 CPU 將資料載入不同層次的 cache。 ---節錄自[prefetch 指令](https://www.csie.ntu.edu.tw/~r89004/hive/sse/page_7.html) ## 效能分析 用 switch 來個別執行三個 function ```clike= switch(argv[1][0]){ case 'p': clock_gettime(CLOCK_REALTIME, &start); sse_prefetch_transpose(src, out0, TEST_W, TEST_H); clock_gettime(CLOCK_REALTIME, &end); printf("sse prefetch: \t %ld us\n", diff_in_us(start, end)); break; case 's': clock_gettime(CLOCK_REALTIME, &start); sse_transpose(src, out1, TEST_W, TEST_H); clock_gettime(CLOCK_REALTIME, &end); printf("sse: \t\t %ld us\n", diff_in_us(start, end)); break; case 'n': clock_gettime(CLOCK_REALTIME, &start); naive_transpose(src, out2, TEST_W, TEST_H); clock_gettime(CLOCK_REALTIME, &end); printf("naive: \t\t %ld us\n", diff_in_us(start, end)); break; default: printf("Invalid function"); break; } ``` per stat 的結果 ``` Performance counter stats for './main n' (100 runs): 3726,4426 cache-misses # 85.406 % of all cache refs ( +- 0.18% ) 4363,1900 cache-references ( +- 0.16% ) 14,4833,7908 instructions # 1.33 insn per cycle ( +- 0.00% ) 10,9110,6474 cycles ( +- 0.05% ) 0.332581729 seconds time elapsed ( +- 0.08% ) Performance counter stats for './main s' (100 runs): 1479,4510 cache-misses # 76.696 % of all cache refs ( +- 0.17% ) 1928,9818 cache-references ( +- 0.03% ) 12,3637,1346 instructions # 1.62 insn per cycle ( +- 0.00% ) 7,6289,6692 cycles ( +- 0.13% ) 0.233147495 seconds time elapsed ( +- 0.18% ) Performance counter stats for './main p' (100 runs): 877,0174 cache-misses # 66.930 % of all cache refs ( +- 0.29% ) 1310,3588 cache-references ( +- 0.12% ) 12,8242,8826 instructions # 2.39 insn per cycle ( +- 0.00% ) 5,3705,8358 cycles ( +- 0.07% ) 0.164465353 seconds time elapsed ( +- 0.15% ) ``` 結果顯示引入 sse 可以加快運算的速度, 而 prefetch 可以讓 cache miss 下降。 ## 嘗試用 AVX 進一步提昇效能 * 作業要求提到 ``` 修改 Makefile，產生新的執行檔，分別對應於 naive_transpose, sse_transpose, sse_prefetch_transpose (學習 phonebook 的做法)，學習 你所不知道的 C 語言：物件導向程式設計篇 提到的封裝技巧，以物件導向的方式封裝轉置矩陣的不同實作，得以透過一致的介面 (interface) 存取個別方法並且評估效能 ``` 所以我應該將三種 function 寫在不同的檔案, 再共用一個 transpose.h, 才能運用封裝技巧增加效能並修改 makefile 讓程式一起執行。如下: 建立一個transpose.h ```clike= #ifndef TRANSPOSE_H #define TRANSPOSE_H void transpose(int *src, int *dst, int w, int h); #endif ``` 在 main.c include "transpose.h" 並呼叫 transpose function ```clike= transpose(src, out0, TEST_W, TEST_H); ``` 在各個 .c 檔寫各自的執行方法, 如 naive_transpose.c 檔中 ```clike= #include "transpose.h" void transpose(int *src, int *dst, int w, int h) { for (int x = 0; x < w; x++) for (int y = 0; y < h; y++) *(dst + x * h + y) = *(src + y * w + x); } ``` 修改 makefile (參考 [st9007a 的 github](https://github.com/st9007a/prefetcher)) ```clike= all: $(GIT_HOOKS) $(EXEC) run: $(EXEC) @for method in $(EXEC); do \ echo exec $$method; \ ./$$method; \ done naive_transpose: $(SRC) naive_transpose.c $(CC) $(CFLAGS) -o $@ $^ sse_transpose: $(SRC) sse_transpose.c $(CC) $(CFLAGS) -o $@ $^ sse_prefetch_transpose: $(SRC) sse_prefetch_transpose.c $(CC) $(CFLAGS) -o $@ $^ ``` `note: $@: 代表所有工作目標 （%.o), $^: 代表所有必要條件 (%.c)` * 先查一下什麼是 [AVX](http://online.ithome.com.tw/itadm/article.php?c=65950&s=5), 並參考[此篇共筆](https://paper.dropbox.com/doc/Week8-bW6HKDcSi6kZ9dGV1FqGp) AVX 的暫存器是 256-bit，一次可以讀取 8 筆資料，所以 for loop 的 step 改成 8 ```clike= void transpose(int *src, int *dst, int w, int h) { for (int x = 0; x < w; x += 4) { for (int y = 0; y < h; y += 4) { __m128i I0 = _mm_loadu_si128((__m128i *)(src + (y + 0) * w + x)); __m128i I1 = _mm_loadu_si128((__m128i *)(src + (y + 1) * w + x)); __m128i I2 = _mm_loadu_si128((__m128i *)(src + (y + 2) * w + x)); __m128i I3 = _mm_loadu_si128((__m128i *)(src + (y + 3) * w + x)); __m128i T0 = _mm_unpacklo_epi32(I0, I1); __m128i T1 = _mm_unpacklo_epi32(I2, I3); __m128i T2 = _mm_unpackhi_epi32(I0, I1); __m128i T3 = _mm_unpackhi_epi32(I2, I3); I0 = _mm_unpacklo_epi64(T0, T1); I1 = _mm_unpackhi_epi64(T0, T1); I2 = _mm_unpacklo_epi64(T2, T3); I3 = _mm_unpackhi_epi64(T2, T3); _mm_storeu_si128((__m128i *)(dst + ((x + 0) * h) + y), I0); _mm_storeu_si128((__m128i *)(dst + ((x + 1) * h) + y), I1); _mm_storeu_si128((__m128i *)(dst + ((x + 2) * h) + y), I2); _mm_storeu_si128((__m128i *)(dst + ((x + 3) * h) + y), I3); } } } ``` 加上 prefetch 指令 ```clike= void transpose(int *src, int *dst, int w, int h) { for (int x = 0; x < w; x += 4) { for (int y = 0; y < h; y += 4) { #define PFDIST 8 _mm_prefetch(src+(y + PFDIST + 0) *w + x, _MM_HINT_T1); _mm_prefetch(src+(y + PFDIST + 1) *w + x, _MM_HINT_T1); _mm_prefetch(src+(y + PFDIST + 2) *w + x, _MM_HINT_T1); _mm_prefetch(src+(y + PFDIST + 3) *w + x, _MM_HINT_T1); __m128i I0 = _mm_loadu_si128 ((__m128i *)(src + (y + 0) * w + x)); __m128i I1 = _mm_loadu_si128 ((__m128i *)(src + (y + 1) * w + x)); __m128i I2 = _mm_loadu_si128 ((__m128i *)(src + (y + 2) * w + x)); __m128i I3 = _mm_loadu_si128 ((__m128i *)(src + (y + 3) * w + x)); __m128i T0 = _mm_unpacklo_epi32(I0, I1); __m128i T1 = _mm_unpacklo_epi32(I2, I3); __m128i T2 = _mm_unpackhi_epi32(I0, I1); __m128i T3 = _mm_unpackhi_epi32(I2, I3); I0 = _mm_unpacklo_epi64(T0, T1); I1 = _mm_unpackhi_epi64(T0, T1); I2 = _mm_unpacklo_epi64(T2, T3); I3 = _mm_unpackhi_epi64(T2, T3); _mm_storeu_si128((__m128i *)(dst + ((x + 0) * h) + y), I0); _mm_storeu_si128((__m128i *)(dst + ((x + 1) * h) + y), I1); _mm_storeu_si128((__m128i *)(dst + ((x + 2) * h) + y), I2); _mm_storeu_si128((__m128i *)(dst + ((x + 3) * h) + y), I3); } } } ``` perf stat 結果 ``` Performance counter stats for './avx_transpose' (100 runs): 1065,8090 cache-misses # 71.066 % of all cache refs ( +- 0.13% ) 1499,7409 cache-references ( +- 0.03% ) 11,4253,5599 instructions # 2.11 insn per cycle ( +- 0.00% ) 5,4173,0425 cycles ( +- 0.04% ) 0.168060712 seconds time elapsed ( +- 0.22% ) Performance counter stats for './avx_prefetch_transpose' (100 runs): 1106,1211 cache-misses # 71.471 % of all cache refs ( +- 0.23% ) 1547,6603 cache-references ( +- 0.04% ) 11,6553,2177 instructions # 2.27 insn per cycle ( +- 0.00% ) 5,1406,7729 cycles ( +- 0.12% ) 0.159071534 seconds time elapsed ( +- 0.21% ) ``` 結果 cache miss 竟然沒有減少, 那就搭配 raw counter 使用 perf stat, 來看在 cache 上更精確的資訊。 *** L1-cache 的資訊 * L1D_PEND_MISS.PENDING: Increments the number of outstanding L1D misses every cycle * L1D_PEND_MISS.PENDING_CYCLES: Cycles with at least one outstanding L1D misses from this logical processor * L1D.REPLACEMENT: Counts the number of lines brought into the L1 data cache ``` Performance counter stats for './avx_transpose' (100 runs): 8,9010,2905 L1D_PEND_MISS.PENDING ( +- 0.27% ) 1,3914,8076 L1D_PEND_MISS.PENDING_CYCLES ( +- 0.40% ) 800,6081 L1D.REPLACEMENT ( +- 0.03% ) 0.168739765 seconds time elapsed ( +- 0.22% ) Performance counter stats for './avx_prefetch_transpose' (100 runs): 3,0279,7969 L1D_PEND_MISS.PENDING ( +- 0.16% ) 8892,7927 L1D_PEND_MISS.PENDING_CYCLES ( +- 0.11% ) 796,5051 L1D.REPLACEMENT ( +- 0.02% ) 0.156435634 seconds time elapsed ( +- 0.06% ) ``` 增加 prefetch 指令後, L1-cache miss 明顯下降許多。 *** L2-cache 的資訊 * L2_RQSTS.DEMAND_DATA_RD_MISS: Demand Data Read requests that missed L2, no rejects * L2_RQSTS.DEMAND_DATA_RD_HIT: Demand Data Read requests that hit L2 cache * L2_RQSTS.ALL_DEMAND_DATA_RD: All demand data read requests to L2. ``` Performance counter stats for './avx_transpose' (100 runs): 308,1384 L2_RQSTS.DEMAND_DATA_RD_MISS ( +- 0.00% ) 2,9401 L2_RQSTS.DEMAND_DATA_RD_HIT ( +- 0.60% ) 314,6292 L2_RQSTS.ALL_DEMAND_DATA_RD ( +- 0.01% ) 0.165062276 seconds time elapsed ( +- 0.05% ) Performance counter stats for './avx_prefetch_transpose' (100 runs): 91,8949 L2_RQSTS.DEMAND_DATA_RD_MISS ( +- 0.14% ) 177,3311 L2_RQSTS.DEMAND_DATA_RD_HIT ( +- 0.12% ) 272,6394 L2_RQSTS.ALL_DEMAND_DATA_RD ( +- 0.05% ) 0.159467838 seconds time elapsed ( +- 0.24% ) ``` 增加 prefetch 指令後, L2 hit rate 大幅提昇。