# prefetch 背景知識簡略整理
contributed by<`BodomMoon`,`TingL7`>

[分組表](https://hackmd.io/MDIXcaHRTTK-SpAHLNYGTQ?both)

:::info
本文章撰寫目的是讓有心了解 software-pipelining 這項作業的同學對於 prefetch 有基礎的認識即可。
:::

## [When Prefetching Works, When It Doesn’t, and Why](https://www.cc.gatech.edu/~hyesoon/lee_taco12.pdf)論文筆記
* 閱讀完論文要知道的幾件事
- [x] software prefetch 的優缺點、限制
- [x] hardware prefetch 的優缺點、限制
- [x] software/hardware prefetch 之間的交互作用、正負面影響
### prefetch
將記憶體中的資料在讀寫單元空閒時(運算單元努力工作時)平行下載，達到降低 cache miss latency 的效果

* prefetch 依抓取到資料的時間分類
* prefetch 資料太早到的話，要在 cache 中等很久，占位子，還可能被踢出去 。
* 太晚到的話，就達不到降低 latency 的效果

* prefetch 是有額外開銷(over head)的
* prefetch 本身就是使用不同方式快取內容進行額外的補充，進行額外操作時就會消耗額外的有限資源，但如果這個補充的資料並沒有恰好被使用到則這些額外消耗的有限資源就都是浪費掉的，也就是所謂的快取污染。

### hardware prefetch
透過資料的訓練來預期之後會使用到的資料，並且將其載入 cache 中。一般作法有兩種:
* GHB prefetcher : Global History Buffer，將 cache miss 的資料暫存起來，根據這些資料去選擇較佳的 prefetching method。採 FIFO ，可避免 stable data，提高精準度。
* STR prefetcher : Stream buffers，將 cache miss 在記憶體中附近的連續資料放到 stream buffer 中，在假設常常用到都會放在一起的前提下，可以減少 cache miss 的情況。
> 上次CSAPP 習題 6.3.7 考的就是 STR prefetcher 的行為


* hardware prefetch 優點
* 透過訓練，可以在執行時間做出適當的 prefetch 選擇
* 不增加指令，直接以硬體運作

* hardware prefetch 缺點/限制
* 大量的 Streams
* 硬體受到資源限制，無法一次操作大量的 streams
* 極短的 Streams
* stream 太短沒有足夠的 cache misses 去做硬體的預取和載入有用的 cache block
* 不規則記憶體存取
* 因為硬體是有規則的拿取，如果要存取不規則的記憶體(資料結構)，會變得很複雜

### software prefetch
透過編譯器或者直接在程式中插入 [intrinsics](https://www.csie.ntu.edu.tw/~r89004/hive/sse/page_3.html)，達到 prefetch 的效果，常見的有 intel SSE (Streaming SIMD Extensions) 、 AVX
* intrinsics : 使用起來像函式，但實際上會直接被編譯器編譯成組合語言，在 SSE 中，型式為 `_mm_<opcode>_<suffix>` ，例如:

        __m128 _mm_add_ps(__m128 a, __m128 b)

* opcode : 指令類別，如: `add` 、 `sub`
* [suffix](https://www.csie.ntu.edu.tw/~r89004/hive/sse/page_2.html) : 資料種類，有 `ps`(Packed Single-precision) 、 `ss`(Scalar Single-precision) 兩種。
* [SSE intrinsics 轉置矩陣解析](https://hackmd.io/s/Byp2oH1AM#)
* software prefetch 優點
* 不規則的記憶體存取
* Cache Locality Hint
* 可以利用 hint 將資料放在適合的 cache level ，減少不同 level 之間造成的 Latency
* 硬體只會將 prefetch 到的資料放在 LLC (last level cache)
* Loop Bounds
* 由 loop unrolling, software pipelining, and using branch instructions 這幾個技巧，使得軟體的 prefetch 較硬體靈活
* software prefetch 缺點
* 增加指令數量
* 除了指令本身，每道指令都需要額外的計算記憶體位置
* Static Insertion
* 無法在執行時間根據情況來做更好的調整
* 改變程式結構
* 為了使預取達到效果，有時候會做一些結構的修改，例如:迴圈的拆解(loop unrolling)，可能使可讀性下降
* software prefetch overhead
* cache pollution
* 有些資料過早進到 cache ，或是進到 cache 之後沒有用到，導致 overhead
* 影響小
* bandwidth consumption
* core 與記憶體之間的頻寬，只能確保夠 single-thread 使用
* 影響小
* memory access latency
* 從記憶體存去資料到 cache 或 buffer 需要一段時間， software prefetch 沒辦法保證能隱藏這段時間
* 影響**大**
* redundant prefetch overhead
* 負面影響很小，即使大量
* instruction overhead
* 即使大量， overhead 也很小

### software + hardware prefetch
同時採用 software 及 hardware prefetch ，兩者會互相影響，有加成的效果，也可能有負面的影響。
* software + hardware prefetch 優點/正面影響
* 針對規則/不規則的 stream 分別交給 hardware / software prefetch，達到截長補短的正面效果
* 如果 software prefetch 的資料遲了， hardware prefetch 也能及時補上資料
* software + hardware prefetch 缺點/負面影響
* software prefetch 會減少能夠訓練 hardware prefetch 的資料，因為都已經 prefetch ， hardware prefetcher 就以為這些是不需要 prefetch 的資料
* software prefetch 指令會觸發 hardware prefetch ，造成過早要求 prefetch
* software prefetch 取到錯誤或多餘的資料時，會造成硬體上的負擔，降低效率

### software / hardware / software+hardware prefetcher 之間的比較
* SPEC CPU 2006 的效能比較
* software+hardware prefetcher 所造成的效果，可能有三種:
* Positive : 要達到此效果，通常會有以下特性
* short array streams
> 這裡就可以應用老師之前提到的 loop unrolling 技巧
* irregular memory address patterns
* L1 cache miss reduction
* Neutral
* Negative

* 資料結構與對應的 prefetch
* ~~stream : 兩筆要取的資料，只有在一個 cache line 抓~~
* ~~stride : 兩筆要取的資料，跨越兩個以上的 cache line~~
> 同學您這裡的的解釋好像不太對，這邊計算的都是下一筆預取資料的位置喔，沒有什麼兩筆的資料。[name=BodomMoon]
>> 兩筆資料就是指現在的資料跟下一個要預取的資料，我沒有解釋好。[name=TingL7]
* stream : 要預取的資料擺放位置，在一個 cache line 可以同時抓取的範圍內
* stride : 要預取的資料擺放位置，跨越一個以上的 cache line 範圍
> 我個人覺得這樣解釋比較明確一點 :D[name=BodomMoon]

### prefetch distance D
要預先載入多遠的資料。舉例來說，原本要載入的進度是 a[i] ，而要預先載入下 N 筆資料的資料，就是 D = N , a[i+D] 。
* 計算:
$D \geq \lceil \dfrac l d\rceil$
* l : prefetch lantency
* d : 存取該資料結構的最小間隔距離
* D 要足夠大，才不容易被踢出 cache
* **prefetch distance 必須要大到能夠隱藏 memory latency**
> 因為 prefetch 本質上也是從 memory 取資料到 cache ，這個取的過程也是要經過一次的 memory latency ，所以如果 prefetch distance 小於 memory latency 的話資料**一定**來不及在存取前放到 cache 。
* prefetch distance 大小對效能的影響

# ~~懶人包~~ 結論
1. 因為從 memory 取資料到 cache 需要一定的時間，為了減少這個情況造成的效能損耗， prefetch 因應誕生。
2. prefetch 可以加速執行也可以減慢執行速度，所以必須有技巧的使用。
3. prefetch 用硬體跟軟體都可以實現，並且各有利弊還可以同時兩者並存。
4. prefetch 時預取的資料距離尤其重要，不能太長也不能太短。

## 相關參考資料整理

[Prefetch 論文閱讀](https://hackmd.io/s/B1KOuuWog#) contributed by<zhanyangch>

[software pipelining 有錄影](https://hackmd.io/s/S1fZ1m6pe#) contributed by <yangyang95> <changyuanhua>

[2017q3 software-pipelining 老師給的版本 也有錄影](https://hackmd.io/s/BJWcEb3xM) contributed by<changyuanhua,vonchuang>

[2017q1 Homework3 (作業區) ](https://hackmd.io/s/HkYlSCJil#2017q1-Homework3-%E4%BD%9C%E6%A5%AD%E5%8D%80)有大量之前同學寫的資料可參考

[B06: software-pipelining ](https://hackmd.io/s/rks62p1sl#)2016作業精華區

[2016q3 Homework3 (software-pipelining)](https://hackmd.io/s/B1lDZtO0#)包含通篇論文筆記的先賢作業

[Data Prefetch Support](https://gcc.gnu.org/projects/prefetch.html) GNU 官方對於 prefetch 支援的說明

[亮谷大大的紀錄](https://hackmd.io/s/S1oi85qR#) 解釋的挺平易近人(?)