### When Prefetching Works, When It Doesn’t, and Why 論文閱讀

前情提要：

* CPU 的運算速度遠比 CPU 存取 memory 的速度要快很多
* 所以加入了 cache 來加速資料的存取，避免過度頻繁讀取 memory
* 如果資料不在 cache 中就會產生 cache miss，最後仍得從 memory 中載入資料，指令需一段 cycle 後才被處理

prefetching：預先將所需的資料從 memory 載入至 cache 中，避免 cache miss latency

---

### 1. INTRODUCTION

研究動機：

* 很少精確說明如何正確地插入 prefetch instrinsics 的文件
* SW 與 HW prefething 的交互作用未被全面了解

目標：

* 提供插入 prefetch instrinsics 的指南
* (?) 為自動交互 HW / SW prefetching 的架構下提供新的方向

實驗結果:


* Baseline 是只有 complier 自動新增 instrinsics ，在圖中作為基準，所以未列入長條圖中
* GHB 與 STR 是 hardware prefetcher + complier 的結果
* STR prefetcher [(source)](https://en.wikipedia.org/wiki/Cache_prefetching#Stream_buffers)
* stream-based prefetcher
* 在 cache 與 memory 之間有多個 stream buffer ( 存取速度快，就像 cache 一樣)
* cache miss (可能多次，到已被訓練、已偵測) 載入 block 後，分配 stream buffer，stream buffer 放入多個接下來連續 block 的資料
* 資料從 stream buffer 提取，stream buffer 再從 memory 取得新的下一個 block
* 如下圖，block A 發生 cache miss 後，如果分配了 stream buffer， A+1 ~ A+4 被移入 stream buffer，如果 A+1 從 stream buffer 取得，stream buffer 再移入 A+5，stream buffer 現在為 A+2 ~ A+5
* 
* GHB prefetcher [(source)](http://www.eecg.toronto.edu/~steffan/carg/readings/ghb.pdf)
* 很多 prefetch 方法使用 history table 放入資料 prefetch 的相關資訊或特性，比如 stride information ，
* GHB 著重在 history table 的改善
* GHB = Global History Buffer
* 比起原本的 history table，引入了 hash 至 GHB 查找
* GHB 的 history 以 linked list 串接
* GHB 以 FIFO 的方式丟棄與新增 history
* 

* SW 包含 complier 與手動新增 instrinsics 的結果
* GHB + SW 與 STR + SW 就是比 GHB 與 STR 再手動新增 instrinsics
* x 軸有多個 benchmark，這些都來自於 SPEC CPU^(R)^ 2006 這個 CPU 效能分析套件 [(source-1)](https://www.spec.org/cpu2006/) [(source-2)](https://en.wikipedia.org/wiki/SPECint) [(source-3)](https://en.wikipedia.org/wiki/SPECfp)

幾個觀察：

* SW 與 HW 再怎麼亂搭配都比 baseline 好
* complier 僅最保守地加入 prefetch 指令
* 這篇論文中主要使用 icc ， icc 是不會加任何 prefetch 指令的
* 在論文後面有使用 gcc 編譯，gcc 有加了一些 prefetch 指令
* 將 HW + SW 與 HW 的效能比較，分為 Positive 、 Neutual 、 Negative
* 有些 HW + SW 反而使效能下降 ( Negative )

先講結論：

* SW 適合短陣列的 stream 與不規則的 memory 存取
* SW 會干擾 HW prefetching 的 training (尤其是 SW 只針對 stream 的一部分 )，造成負面的效果
* training : 要 HW prefetcher 去 prefetch 需要累積一些經驗(e.g. FSM 狀態轉移)來偵測

### 2. BACKGROUND ON SOFTWARE AND HARDWARE PREFETCHING

stream：跨 cache-line 的存取
stride：跨超過兩個以上 cache-line 的存取


以上列出資料結構與對應的存取模式，以及可能使用的 HW 、 SW prefetcher

Pattern：
* 分為 stream、stride，還有 irregular (不規律型)

Index：
* stream 、 stride 都是 direct ，只要加 distance 取得 index，irregular 為 indirect ，需經過複雜的計算取得 index

#### 2.1 Software Prefetch Instrinsics

在 icc 的編譯環境中使用 x86 SSE 的 instrinsic
`_mm_prefetch(char *ptr, int hint)`


#### 2.2 Prefetch Classification

將 prefetch 的結果分類

* timely：使用時在資料已出現在 cache ，最佳狀態
* late：資料晚到
* early：資料太早到而從 cache 除去
* redundant_dc：已經在 cache 裡了
* redundant_MSHR：已經在 Miss Status Holding Register 了
* Incorrect：不正確的資料被 prefetch

> Miss Status Holding Register?

#### 2.3 Software Prefetch Distance

這裡是只針對 direct ，就是提供要在多少 index 距離外對資料 prefetch 才能使資料在正確的時間點即時使用的不等式

$$D\ge\lceil\frac{l}{s}\rceil$$

其中 $l$ 是 prefetch (從 memory 至 cache ) 的延遲時間
$s$ 是迴圈主體的最小路徑長度

> 不是很確定 $s$ 代表的意思，我覺得是指單一個 cache-line 內遍歷此 cache-line 內資料的最小時間

#### 2.4 Direct and Indiret Memory Indexing

* direct 容易被 HW prefetcher 偵測
* SW prefetching 比較好處理 indirect 的情況

* 實驗預期 indirect SW prefetching 的效果 > HW prefetching

### 3. POSITIVE AND NEGATIVE IMPACTS OF SOFTWARE PREFETCHING

#### 3.1

### 4. EXPERIMENTAL METHODOLOFY

#### 4.1 Prefetch Instrinsic Insertion Algorithm

> 3.4.5. 看完了，之後再補上重點

## 參考資料
[When Prefetching Works, When It Doesn’t, and Why](http://www.cc.gatech.edu/~hyesoon/lee_taco12.pdf)
[Wikipedia: Cache prefetching](https://en.wikipedia.org/wiki/Cache_prefetching)
[An Introduction to Prefetching](https://www.google.com.tw/url?sa=t&rct=j&q=&esrc=s&source=web&cd=1&ved=0ahUKEwiaucXKo9LSAhVKGpQKHWnaCzoQFggaMAA&url=http%3A%2F%2Fwww.ecs.umass.edu%2Fece%2Fandras%2Fcourses%2FECE668%2FMylectures%2FPrefetching-lecture.ppt&usg=AFQjCNFgJyn22Uh0egaJSvw_P-b9_L2K9Q&sig2=_zzxsiUmrcbdlKzDRPeywQ)
[stream buffer原理](http://blog.csdn.net/qianlong4526888/article/details/41517303)