# 2017q3 Homework2 (software-pipelining)
###### tags: `進階電腦系統理論與實作 (Fall 2017)`

contributed by < `jcyztw` >

__注：繳交期限過後補交__

---
## 開發環境

Architecture:          x86_64
CPU 作業模式：    32-bit, 64-bit
Byte Order:            Little Endian
CPU(s):                8
On-line CPU(s) list:   0-7
每核心執行緒數：2
每通訊端核心數：4
Socket(s):             1
NUMA 節點：         1
供應商識別號：  GenuineIntel
CPU 家族：          6
型號：              158
Model name:            Intel(R) Core(TM) i7-7700 CPU @ 3.60GHz
製程：              9
CPU MHz：             900.000
CPU max MHz:           4200.0000
CPU min MHz:           800.0000
BogoMIPS:              7200.00
虛擬：              VT-x
L1d 快取：          32K
L1i 快取：          32K
L2 快取：           256K
L3 快取：           8192K
NUMA node0 CPU(s):     0-7
Flags:                 fpu vme de pse tsc msr pae mce cx8 apic sep mtrr pge mca cmov pat pse36 clflush dts acpi mmx fxsr sse sse2 ss ht tm pbe syscall nx pdpe1gb rdtscp lm constant_tsc art arch_perfmon pebs bts rep_good nopl xtopology nonstop_tsc aperfmperf tsc_known_freq pni pclmulqdq dtes64 monitor ds_cpl vmx smx est tm2 ssse3 sdbg fma cx16 xtpr pdcm pcid sse4_1 sse4_2 x2apic movbe popcnt tsc_deadline_timer aes xsave avx f16c rdrand lahf_lm abm 3dnowprefetch epb intel_pt tpr_shadow vnmi flexpriority ept vpid fsgsbase tsc_adjust bmi1 hle avx2 smep bmi2 erms invpcid rtm mpx rdseed adx smap clflushopt xsaveopt xsavec xgetbv1 xsaves dtherm ida arat pln pts hwp hwp_notify hwp_act_window hwp_epp

---
## 閱讀論文：[When Prefetching Works, When It Doesn’t, and Why](https://www.cc.gatech.edu/~hyesoon/lee_taco12.pdf)

[以下依論文章節順序摘錄重點，**6. Case studies: source code analysis of individual benchmarks** 請直接參考考論文內容；**7. Related work** 以及 **8. Conclusion and future work** 在此就先不介紹]

### 1. Introduction
* 當今 (此 paper 發表時間為 2012 年) 針對 combined software and hardware prefetching 在測試不同的 benchmarks，在效能表現上有好有壞的相關研究並不多，因此上述現象為本論文主要的研究目標之一
* 本論文的另一個研究目標就是提供一些關於插入 prefetch intrinsics 到現有的 hardware prefetcher 的指南 (_to provide guidelines for inserting prefetch intrinsics in the presence of a hardware prefetcher_)
* 要探討的 hardware prefetching schemes 主要是 stream prefetcher 以及 stride prefetcher (因為前述兩種 scheme 是當時商業上有被實作出來的 scheme)；而 software prefetching scheme 的部份，則是利用 gcc/icc compiler-inserted prefetching 的 prefetch intrinsics

> software prefetching 和 hardware prefetching 的定義？
>> 可先參考[維基百科](https://en.wikipedia.org/wiki/Cache_prefetching#Hardware_vs._software_cache_prefetching "Cache prefetching from Wikipedia")的中定義

### 2. Background on software and hardware prefetching

下面的表格總結一些常見的 data structures，相對應的 data access patterns，以及已提出用來對這些 data structures 作 prefetch 的 hardware/software prefetching 機制。(`RDS`：Recursive Data Structure)

#### Software prefetch intrinsics

論文中會用到以下的 prefetch intrinsic (來自 Intel x86 SSE SIMD extensions)：

`_mm_prefetch(char *ptr, int hint)`

`ptr`：想要 prefetch 的 memory address
`hint`：prefetch usage hint

`hint` 可分成以下四種：

#### Prefetch classification
prefetch request 在此可分成六種：
(`mshr`：miss status holding register)

下圖用時間軸來表示當 demand access 時，prefech 是屬於哪一種分類。舉例來說，當預先抓進 cache 的 block 已經被驅逐出 cache，而此時來了一個這個 block 的 demand access，則此種 prefetch 就屬於 _early prefetch_。

#### Software prefetch distance
prefetch distance 在此定義為在某一 memory address 算起，所預先抓取的 _distance_。

一個 array 的 prefetch distance 可由以下式子決定：

$$
D \geq \left\lceil \frac{l}{s} \right\rceil\mbox{(1)}
$$

其中 $l$ 表示 prefetch lantency，$s$ 表示一個 loop 中最短路徑的長度 (_the length of the shortest path through the loop body_)。

#### Direct and indirect memory indexing
用下面的 x86 指令來看 direct 和 indirect memory indexing：

可看到 indirect prefetch request 會比 direct prefetch request 的 overhead 還來的高 (多出一個 `PREFETCH` 指令)。

### 3. Positive and negative impacts of software prefetching

> stream 和 stride 是指什麼？

#### software prefetching 與 hardware prefetching 相比的優點和缺點

**優點**

* _Large number of streams_
* stream prefetcher 可預先抓取的 stream 數量受限於硬體資源，如 stream detector 和 book-keeping mechanism
* 有些 benchmark 在測試時用到的 stream 數量會超過硬體所能負擔的數量，此時可利用 software prefetching 的方式，在每個 stream 中插入 prefetch request。而這對 hardware prefetching 來說是很難作到的。

* _Short streams_
* hardware prefetching 若在 stream 長度非常短的情況，會無法訓練 hardware prefetcher (cache miss 太少以致於不能用來訓練) 來偵測出 stream/stride 的 direction 和 distance

* _Irregular memory access_
* software prefetching 可透過插入適當的 prefetch intrinsics 來預先抓取各式各樣的 irregular data structures (可參考前述 Table I 中的 **Pattern** 欄位)；相比之下，hardware prefetching 則是需要非常複雜的硬體結構才能做到預先抓取 irregular data structure

* _Cache locality hint_
* hardware-prefetched data 放在 lower-level cache (e.g. L2/L3 cache)，而 software-prefetched data 則是被放在 L1 cache
* 將 prefetched data 放在 lower-level cache 雖然可以降低 L1 cache 的 cache pollution，但 L2 到 L1 cache 的 access latency 會受到影響 (大幅地降低效能)
* 而 software prefetching 可以有彈性地選擇放置 prefetched data 的適當的 cache level (利用 Table II 的 prefetch hint)

* _Loop bounds_
* software prefetching 可以利用 loop unrolling、software pipelining 或是 branch 指令，來決定 array data structure 的 loop bound (_determine loop bounds in array data structures_)
* 而 hardware prefetching 雖可有很大的 prefetch distance 和很高的 prefetch degree (稱此為 aggressive)，但是過度的 aggressive prefetching 會導致 early/incorrect prefetch requests

**缺點**

* _increased instruction count_

* _static insertion_
* 哪些 data 要被預先抓取以及其相對應的 prefetch distance 是由 programmer 或 compiler 來決定，要不要 prefetch 和選擇 parameter 都屬於靜態地作決定 (例如編譯程式時設定的參數不能在 runtime 時，根據不同的 memory latency、effective cache size 或 bandwidth 動態調整)
* memory address 的 access pattern 是屬於 phase behavior，因此 software prefetching 對於此種情況的適應性 (adaptivity) 非常不好

* _code structure changes_
* 當在 loop 中的指令數非常少時，要提供及時的 prefetching request (插入 software prefetching 指令) 變得很有挑戰性，因為在預先抓取指令和發出 prefetch request 之間沒有足夠的計算 (_there are not enough computations between prefetching instructions and demand requests_)

#### 當 software prefetching 和 hardware prefetching 一起使用時的效果

* _協同效果 (Synergistic Effects)_

* handling multiple streams
* 例如 hardware prefetch 可以負責 (cover) regular streams 而 software prefetching 則可負責 irregular streams
* positive training
* 如果一個被 software prefetcher 預先抓取的 block 太遲插入 cache，那麼利用一個訓練過的 hardware prefetcher 便可以改善 prefetch timeliness

* _拮抗效果 (Antagonistic Effects)_

* negative training
* 如果 software prefetching 預先抓取的 blocks 隱藏了部份的 streams，則 hardware prefetcher 將無法被好好地訓練
* harmful software prefetching
* hardware prefetching 的準確性通常比 software prefetching 還低。所以當 software prefetch requests 不正確或是 early，hardware prefetching 的有效性會因為增加的 cache 和 memory bandwidth 的關係降低

### 4. Experimental methodology

#### Prefetch intrinsic insertion algorithm

為了找出 prefetch candidates，因此需要對每個 application (benchmark) 作數據量化 (profiling) (prefetch candidate 指的是一個 L1 MPKI (Misses Per Kilo Instructions) 超過 0.05 的 benchmark)。

$$
Distance = \frac{K \times L \times IPC_{bench}}{W_{loop}}
$$
where $K$ is a constant, $L$ is an average memory latency, $IPC_{bench}$ is the profiled average IPC of each benchmark, and $W_{loop}$ is the average instruction count in one loop iteration.

此處實驗設定為：
* $K$ = 4, $L$ = 300 ($Distance$ 由 $IPC_{bench}$ 和 $W_{loop}$ 決定，而 $IPC_{bench}$ 和 $W_{loop}$ 又是由 profile data 決定。所以 $Distance$ 為 profile-driven)
* default prefetch hint: $T_{0}$ (參見上方 Table II)
* 上述設定只用於 regular loads，而那些複雜的 data structures (例如 RDS、hash、C++ overloaded operators 等) 的 loads 則不使用 prefetch intrinsics

#### Simulation methodology

* simulator: MacSim


* benchmarks: 13 memory-intensive benchmarks from SPEC CPU 2006，每個 benchmark 大約執行 200 萬個 X86 指令


* Pinpoint: 用來幫助分析整體系統架構以及追蹤系統中的 distributed applications 之間的如何互相連結的一種 [APM tool](https://github.com/naver/pinpoint "Pinpoint on GitHub")

### 5. Evaluations: basic observations about prefetching

#### Overhead and limitations of software prefetching

##### Instruction overhead

* _GemsFDTD_、_bwaves_ 和 _leslie3d_ 這三個 benchmark 增加了超過 50% 的指令數 (參見 Fig. 4，_bwaves_ 甚至增加超過 100% 的指令)
* 這些增加的指令不只來自 prefetch 指令，還包括因為要處理 indirect memory access 以及 index calculation 的 regular instructions


##### Software prefetching overhead

* cache pollution 是由 early/incorrect prefetches 造成。由 Fig.5 可以看到，即使消除了 cache pollution (SW+P 部分)，大部分的 benchmarks 都沒有顯著的降低執行時間，表示 cache pollution 對於 software prefetching 的影響很小
* 消除 bandwidth (SW+B 部分，指 core 和 memory 之間的 bandwidth 消耗) 的影響對於大部分的 benchmark 並不會很明顯地減少執行時間 (表示實驗的機器提供了足夠的 bandwidth 給 single-thread aaplications)
* memory latency 的因素 (SW+L 部分) 拿掉之後，由下表可以看出 software prefetching 在大部分的 benchmarks 都降低很多執行時間。表示 software prefeteching 無法改善 memory latency 對效能的影響
* redundant prefetch instructions (SW+R 部分)對 software prefetching 的影響不大，即使有大量的 redundant prefetches 也可以忽略
* 做 software prefetching 即使增加很多指令 (SW+I 部分) 的 benchmark，例如 _GemsFDTD_、_bwaves_ 和 _leslie3d_ ，在消除 instruction overhead 後也沒有明顯的改善效能


##### The effect of prefetch distance

下圖表示 prefetch distance 對效能的影響。x 軸表示對 base prefetch distance 的 offset (0 表示 base prefetch distance)，而 base prefetch distance 是使用公式 (1) 計算得來。prefetch distance 的單位為一個 cache block。


根據 optimal distance zone 和 performance variance 可將 benchmarks 分為五類，如下表。從 Fig. 6 可以看出每個 group 的 performance variance (Perf. Delta)。


在 Fig. 1 中歸類為 neutral 和 negative 的 benchmarks 大都屬於 Table VII 中的 group E (insensitive to the prefetch distance)，_cactusADM_ 和 _bwaves_ 兩者除外 (各成一個分類)。

**Fig. 1**

##### Static distance vs. machine configuration

* 使用 static prefetch distances 的其中一個限制在於 optimal distance 會隨著不同的機器而有所不同，這對未來的 heterogeneous multicore systems 的影響甚大—因為 programmer 不可能事先知道他的程式會在什麼樣的機器上執行 (不曉得 core/system configuration)
* 使用 Table IV 中提到的 machine configurations (base, less-aggressive, and aggressive processors)，並比較這三種設定的可達到最佳效能的 static distance
* 以 _lbm_ 為例，其 best prefetch distance 在 less-aggressive、base 以及 aggressive processor 分別是 2，0，8 (Fig. 7 左方圖)。而 less-aggressive processor 效能差異，則是去找在此 configuration 下，distance 2 和 0 的效能差異；aggressive processor 同理，找 distance 8 和 0 的效能做比較可得效能差異
* 儘管不同的 benchmarks 的 optimal distance 有所不同，效能大致上與 baseline processor 差不多，除了 _lbm_ 例外 (因為大部分的 benchmark 屬於 groupt E (insensitive)，_lbm_ 的部分後面第 6 章另作分析)


* 小結論：static prefetch distance variance 並不會對效能有重大的影響，即使 machine configuration 在 runtime 時被改變

##### Cache-level insertion policy

* 一般來說，out-of-order processor 可以很輕易地容忍 L1 cache misses。所以 hardware prefetcher 會將 prefetched blocks 放入 last level cache (LLC)，以降低汙染 (pollute) L1 cache 的機會
* 但是當 L1 miss rate 高過 processor 可以容忍的程度，甚至一個 L1 cache miss 都會降低效能。因為 software prefetching 大致上很準確 (accurate)，prefetched blocks 可以安全地直接插入 L1 cache 而不會汙染 L1 cache
* 所有的實驗都是使用 T0 hint (參考 Table II) 作為 cache-level placement hint，Fig. 8 顯示不同的 hint 對效能的影響。T0 比 T1 (或 T2) 好的地方在於可以藉由把 prefetched blocks 插入到 L1 cache 來隱藏 L1 cache misses，_libquantum_ 的實驗結果 (Fig. 26) 正好表現了前述行為：使用 software prefetching 可以把 L1 cache miss rate 從 10.4% 降到 0.01%



#### Effect of using hardware and software prefetching together

##### Hardware prefetcher training effects

* 兩種 hardware prefetcher training policies
* **NT (SW+GHB, SW+STR).** 訓練 hardware prefetcher 的演算法會忽略掉 software prefetch requests。也就是說，hardware prefetcher 只被 demand cache misses 訓練
* **Train (SW+GHB+T, SW+STR+T).** 訓練 hardware prefetcher 的演算法包含 software prefetch requests，除此之外還包括一般的 demand misses


上圖顯示對採用 SW+GHB/SW+STR 的 hardware prefetcher 做訓練所得到的效能改善。

以下為各 benchmarks 做 hardware prefetching training 後對效能的影響：
* small benefits: _sphinx3_
* negative effects for both GHB and STR: _milc_ , _gcc_ , _soplex_
* largely unaffected: _mcf_ , _bwaves_
* prefetcher-specific: the remaining benchmarks

由 Fig. 9 的實驗結果圖表可看出，效能可提升 3% 到 5%，這些提升部分主要是因為減少 late prefetching。然而負面影響會造成很嚴重的效能降級，例如 _libquantum_ 的效能降低 55.9%，_milc_ 則是降低 22.5%。

* _libquantum_
* 效能降級的第一個原因：**severe L1 miss penalties** (因為受 software prefetching 訓練的 hardware prefetcher 只會把 prefetched blocks 放到 L2 cache，不會放到 L1 cache，造成減少 L1 prefetching benefits)
* 效能降級的第二個原因：**overly aggressive prefetches** (為了提供及時性，software prefetches 和 hardware prefetches 有各自的 prefetch distance。然而用 software prefetching 訓練 hardware prefetcher 時，基於 software prefetch distance，又會加入 hardware prefetcher 的 prefetch distance，將導致過多 early prefetches)
* _milc_
* _milc_ 屬於 short streams 的 benchmark，所以 software prefetching 會引發不必要的 hardware prefetches

小結論：大致上訓練 hardware prefetcher 時，最好不要搭配 software prefetching requests 來做訓練。

##### Prefetch coverage

* prefetch coverage: the ratio of useful prefetches to total L2 misses

Fig. 10(a) 顯示 GHB 和 STR 的 prefetch coverage。Fig. 10(b) 顯示 SW+GHB 和 SW+STR 的 prefetch coverage，其他有用的 hardware prefetches (標示為 HW) 則顯示在 SW bars 的上方。


大致上，software prefetch coverage 高於 hardware prefetch coverage。但是屬於 neutral 和 negative group 的 benchmarks，其 software prefetch coverage 卻比 hardware prefetching 的 coverage 還低。

小結論：屬於 neutral 和 negative group 的 benchmarks，造成 performance loss 主因為 software coverage 輸給 hardware coverage。

##### Prefetching classification

參考 Table III，由 Fig. 11 可看到只有 _bzip2_ 和 _soplex_ 有超過 10% 的 early prefetches (使用 prefetch cache 應該可減輕 cache pollution effect)；而 _mcf_ 有 10% 的 late prefetches，這是因為 prefetch intrinsic 產生的 dependant load instruction 造成。


#### Using the GCC compiler

* 除了在此有使用 gcc (gcc 版本為 4.4) 編譯 benchmarks，其餘章節都是使用 icc 來編譯
* 在此實驗中，為了探討 gcc compiler 的影響，插入 intrinsics 都是在 benchmarks 用 gcc 編譯完成之後才做
* 所有 Fortran benchmarks 在此實驗中不被使用，因為 gfortran compiler 不支援 prefetch intrinsics

下圖為使用 gcc compiler 的實驗結果。


下圖顯示每個 benchmark binary 中的 prefetch instructions 數量。


#### Real system experiments

* 除了在模擬系統上做實驗，另外也有在實體環境做 software prefetching 的影響的實驗 (在兩種 Intel processor 上做實驗：Core 2 和 Nehalem)
* 在實體系統做的實驗，是跑所有的 reference input sets，而不只是 sim point section
* 由下表可看出 simulated regions 以及 entire execution 有類似的一定 prefetch instructions 比例
* 本論文中的模擬系統，其設定與 Core 2 較相近
* 下圖為實體系統實驗的結果。其中 software prefetching 會造成 _cactusADM_、_soplex_、_bwaves_、_leslie3d_ 和 _sphinx3_ 的效能變得稍差，縱使在模擬系統中這些 benchmarks 都會顯示 benefits

#### Profile-guided optimization (PGO)

此處的實驗結果都是用 gcc 4.4，加上 _fprofile-generate_ 和 _fprofile-use_ 的選項進行編譯 (benchmarks)。下圖顯示 profile-guided optimization (PGO) 的實驗結果。

大致上用 PGO 的 benchmark binaries 的效能皆於 Base 和 SW 之間。

#### Hardware prefetcher for short streams

* 使用 ASD hardware prefetcher 來解決 hardware prefetching 對 short streams 表現不佳的情況
* 實驗結果如下圖
* _milc_: ASD 可改善 _milc_ 效能 7% (沒加上 software prefetching)
* _gcc_, _sphinx3_, _leslie3d_: 在 SW+ASD+GHB/STR 的情況下，可以改善效能最多到 2%
* 小結論：software prefetching 在 short stream 做 prefetching 會比 ASD 來的更有效

#### Content directed prefetching

* content directed prefetching (CDF) 主要針對 linked/ irregular data structures 做 prefetching。下圖顯示實驗結果
* CDP: 可讓 _mcf_ 和 _gcc_ 分別改善 3.9% 和 6.5% 的效能
* CDP+PF (PF: prefetch cache): 可讓 _mcf_ 和 _gcc_ 分別改善 5% 和 12% 的效能

* 小結論：由於 software prefetching 可以做到 78% 的改善，對 irregular data structures 來說，用 software prefetching 做 prefetching 比較有效

#### Manual tuning

雖然可以對所有的 benchmarks 使用 prefetch intrinsic insertion algorithm (第四章有提到)，但不能確定 software prefetching 有被全力發揮出來。因此需要手動地做一些調整，例如移除無用的 prefetches，調整每個 software prefetch 的 prefetch distance，以及使用額外的 overhead-reduction 技巧(如 loop unrolling, prologue/epilogue transformatons)。

下圖為手動 tuning 的實驗結果。可看到 neutral 和 negative group 的 benchmarks 的 speedup 比 positive group 來的高—表示手動移除負面影響的 intrinsics 會更有效率。

然而，手動調整和前述提到的演算法對效能並沒有太大的差異，尤其是在 positive group。這顯示出其實第 4 章所提的演算法就足以拿來決定怎麼插入 software prefetch intrinsics。


---
## 參考資料
* [論文重點提示和解說](https://hackmd.io/s/HJtfT3icx)