# 2017q1 Homework3 (software-pipelining)
contributed by < ` changyuanhua ` >
## 開發環境
* 輸入指令 ` lscpu `
```
Architecture: x86_64
CPU 作業模式： 32-bit, 64-bit
Byte Order: Little Endian
CPU(s): 4
On-line CPU(s) list: 0-3
每核心執行緒數：1
每通訊端核心數：4
Socket(s): 1
NUMA 節點： 1
供應商識別號： GenuineIntel
CPU 家族： 6
型號： 94
Model name: Intel(R) Core(TM) i5-6300HQ CPU @ 2.30GHz
製程： 3
CPU MHz： 799.890
CPU max MHz: 3200.0000
CPU min MHz: 800.0000
BogoMIPS: 4608.00
虛擬： VT-x
L1d 快取： 32K
L1i 快取： 32K
L2 快取： 256K
L3 快取： 6144K
NUMA node0 CPU(s): 0-3
```
## 論文閱讀紀錄
### 名詞解釋
Data reference patterns 被分類為以下三種情形:
* Temporal (時間): 數據將很快再次被使用
* Spatial (空間): 數據將用於相鄰位置（例如，在同一個 cache line 上）。
* Non-temporal (非時間): 數據在將來被引用一次並且不被重用的（例如，對於一些多媒體數據類型，作為3D圖形應用中的頂點緩衝器）
* Prefetch:
* 從記憶體層級上來看 prefetch intrinsic 提供參數可以選擇載入到哪個層級的快取記憶體
> 先搞懂 prefetch
> >在資料被需要之前，把資料從 main memory 中，預先載入到 cache 。因為當資料被需要使用時，從 cache 訪問比 main memory 請求更快速。因此，prefetch 可以隱藏 memory access latency。
> Where to place prefetched data?
> > Cache or dedicated buffer
* Hardware prefetch
* 是用過去的存取紀錄作為 prefetch 的依據，所以 HW 是需要 training 的
* GHB:Global History Buffer
> 搞懂 Hardware prefetch
> >Hardware prefetch 監視從處理器到 cache 的 memory 存取過程，它監視處理器當前正在訪問哪些 memory 的位置，預測將來需要哪些 memory 的位置，以及向那些 memory 的位置發出預取。
* Software prefetch
* 可以是人為或是 compiler 在適當的地方加入 prefetch 指令.
* SW 指的就是老師寫的 _mm_prefetch，可以由我們來控制的
### 研究目的
* the goal of this study is to develop a novel, foundational understanding of both the benefits and limitations of hardware and software prefetching
* 提供在 HW prefetcher 有效的 intrinsic 使用方法
* 提供 HW & SW prefetcher 共存時，效能好的組合
### 研究
* source code-level analysis (源代碼級分析): 幫助理解 compiler- and software-based prefetching (基於編譯器和基於軟件的預取)的實際優缺點
* the synergistic (協同) and antagonistic (對抗) effects between software and hardware prefetching
* an evaluation (評估) of hardware prefetching training policies in the presence of software prefetching requests
### 介紹
手動加入指令有兩個最大的問題:
* 對於如何插入 prefetch intrinsic 沒有一個嚴格的標準
* 軟體與硬體的 prefetch 交互使用的複雜度沒有一個很好的了解
#### 實驗
* 總結了軟件和硬件預取之間的複雜交互
* SPEC CPU 2006 benchmark(x軸)
* 執行時間標準化(y軸): 使用baseline binaries(只有compiler插入的SW prefetcher)的執行時間
* CPU: Intel’s Core 2 and Nehalem
* 使用 icc compiler (也有對gcc compiler做實驗)
* GHB(stride prefetcher)/STR(stream prefetcher): compiler + HW prefetcher
* Base: (i.e., the best among Base, GHB, and STR)
* SW: compiler + 程式中插入 intrinsic (i.e., the best among SW, SW+GHB, and SW+STR)
* 已知驗證: SW prefetch 用在短陣列、連續且不規則的記憶體存取、減少 L1 cache miss 時效能較好
* 實驗發現: SW prefetch 對於HW prefetcher 會有 training effect，造成效能變差。特別是在 SW prefetch只用在stream的一部分時
* 本實驗只會針對現有機制，而模擬與真實系統都會被使用，以模擬完成較複雜的實驗，再對其中的發現以真實系統做驗證
### HW & SW prefetcher背景知識
#### 不同資料結構適合的SW prefetch 和 HW prefetch:
* summarizes common data structures, their corresponding data access patterns, and the hardware/software prefetching mechanisms previously proposed for each.
* 各種資料結構都適用: dead-block-based prefetching
* Recursive Data Structures (RDS): RDS data structure accesses 可以透過 software 容易地預測訪問
* hashing: 難以有效 prefetch
* 定義 cache-line access:
stream: unit-stride
stride: access stride distances 大於 2 個 cache-line
* HW prefetcher 嘗試了 stream prefetcher、GHB prefetcher(stride prefetcher)、content-based prefetcher
#### Software Prefetch Intrinsics
* 當手動插入預取請求時，我們使用 software prefetch intrinsics (x86 SSE SIMD 擴展的一部分)
* 使用 SSE 的__mm_prefetch(char *ptr, int hint) 時要指定
* prefetch address
* prefetch usage hint
* direct address prefetches: 2個指令 /intrinsic
* indirect memory addresses prefetch: 4個指令 /intrinsic
#### prefetch分類
> early vs late
> > Too early : 取代其他有用數據 (cache pollution) 或在使用前被取代掉
Too late : 不能隱藏 processor stall
* ex: if a demand access occurs after its corresponding prefetch request but before it is inserted into the cache, we classify the prefetch as “late.”
* MSHR: Miss Status Holding Register
#### Software Prefetch Distance
* prefetch distance 必須要大到能夠隱藏 memory latency
* D 稱為 prefetch 距離 ; 又定義為應該在存儲器地址上請求 prefetch 的距離
* l is the prefetch latency
* s 是迴圈當中的最短路徑
* prefetch distance 太大可能造成不良的後果，如 coverage 更小、 cache miss 更多
* Coverage: 藉由 prefetch 避掉的 cache miss 比例
* 100 x (Prefetch Hits / (Prefetch Hits + Cache Misses))
#### Direct and Indirect Memory Indexing
* direct memory indexing :
* 可以容易地由 HW prefetched ，因為存儲器地址顯示常規的 stream/stride behavior (流/步幅行為)
* 在 software 中計算不容易
* Direct 是直接可以從指令中知道要存取的記憶體位址,可以透過 hareward prefetch.
* indirect memory indexing :
* 需要特殊的 hardware prefetching mechanisms
* 在 software 中計算容易
* 程式碼 x = a[b[i]] ,需要先計算 b[i] 的值才知道要存取 a[] 中的哪個位置,機器不會比人更知道 b[i] 是怎麼來的,所以使用 software prefetch 比較容易達成.
* indirect memory access 可能造成 SW prefetching overhead
* e.g… a[i] prefetch 一次 ， a[b[i]]則要分兩次prefetch
## Prefetching in the Intel® Core™ Microarchitecture
* 我的 CPU 的 Microarchitecture 是 Skylake [[參考]](http://www.cpu-world.com/CPUs/Core_i5/Intel-Core%20i5-6300HQ%20Mobile%20processor.html)
--> 知道microarchitecture是哪種，才可以確定 HW prefetcher 有哪些種類
## 原始程式碼
* 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);
}
```
這是一個 ` dst[x][y] = src[y][x] ` 的程式
* C 是 row-major 的語言，所以當以 colum order 的方式去讀取，會導致 cache 沒辦法有效地被利用。
* 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);
}
}
}
```
這個程式碼是一次將16筆整數橫向讀入到4個 128bit 的 sse 暫存器，接著利用 unpackhi、unpacklo 使資料 swap ，最後以直排順序存到橫排
* matrix1 一次橫向讀入128bit = 四個int 存進I0 ，只要給要讀入陣列的起始位置，他會往後抓127bit, I1,I2,I3同理
```
__m128i I0 = _mm_loadu_si128((__m128i *)(src1 + (x + 0) * src1_w + k));
```
詳細內容參考 [kobeyu 的筆記](https://hackmd.io/s/BycRx2EC) -> 解釋得很清楚
* 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);
}
}
}
#endif /* TRANSPOSE_IMPL */
```
這個程式碼是將 sse 版本中，加入 SW Prefetch
* 效能分析
* naive
```
Performance counter stats for './naive_transpose' (100 runs):
40,396,950 cache-misses # 86.186 % of all cache refs ( +- 0.30% )
46,872,044 cache-references ( +- 0.24% )
21,069,452 L1-dcache-load-misses # 3.79% of all L1-dcache hits ( +- 0.01% )
555,330,933 L1-dcache-loads ( +- 0.00% )
219,108,523 L1-dcache-stores ( +- 0.00% )
72,803 L1-icache-load-misses ( +- 2.12% )
0.358395944 seconds time elapsed ( +- 0.31% )
```
* sse
```
Performance counter stats for './sse_transpose' (100 runs):
14,842,277 cache-misses # 77.006 % of all cache refs ( +- 0.28% )
19,274,268 cache-references ( +- 0.05% )
8,514,541 L1-dcache-load-misses # 1.91% of all L1-dcache hits ( +- 0.02% )
445,306,115 L1-dcache-loads ( +- 0.00% )
232,791,733 L1-dcache-stores ( +- 0.00% )
103,480 L1-icache-load-misses ( +- 2.20% )
0.273274670 seconds time elapsed ( +- 0.31% )
```
* sse_prefetch
```
Performance counter stats for './sse_prefetch_transpose' (100 runs):
10,613,966 cache-misses # 72.171 % of all cache refs ( +- 0.70% )
14,706,647 cache-references ( +- 0.28% )
8,519,990 L1-dcache-load-misses # 1.83% of all L1-dcache hits ( +- 0.02% )
466,169,620 L1-dcache-loads ( +- 0.00% )
232,724,643 L1-dcache-stores ( +- 0.00% )
83,636 L1-icache-load-misses ( +- 2.14% )
0.186173153 seconds time elapsed ( +- 0.63% )
```
| method | cache-misses rate| L1-dcache-load-misses rate |
| ------ | ---------------- | -------------------------- |
| naive | 86.186 % | 3.79% |
| sse | 77.006 % | 1.91% |
| sse prefetcher | 72.171 % | 1.83% |
* 時間
```
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
```
* naive : 236494 us
* sse : 139678 us
* sse_prefetch : 62750 us
## 實驗一： avx
AVX 的指令集中，沒有 unpack128 這個指令，所以用 _mm256_permute2x128_si256() 來替代
* code:
```clike=
void avx_transpose(int *src, int *dst, int w, int h)
{
for (int x = 0; x < w; x += 8) {
for (int y = 0; y < h; y += 8) {
__m256i I0 = _mm256_loadu_si256((__m256i *)(src + (y + 0) * w + x));
__m256i I1 = _mm256_loadu_si256((__m256i *)(src + (y + 1) * w + x));
__m256i I2 = _mm256_loadu_si256((__m256i *)(src + (y + 2) * w + x));
__m256i I3 = _mm256_loadu_si256((__m256i *)(src + (y + 3) * w + x));
__m256i I4 = _mm256_loadu_si256((__m256i *)(src + (y + 4) * w + x));
__m256i I5 = _mm256_loadu_si256((__m256i *)(src + (y + 5) * w + x));
__m256i I6 = _mm256_loadu_si256((__m256i *)(src + (y + 6) * w + x));
__m256i I7 = _mm256_loadu_si256((__m256i *)(src + (y + 7) * w + x));
__m256i T0 = _mm256_unpacklo_epi32(I0, I1);
__m256i T1 = _mm256_unpacklo_epi32(I2, I3);
__m256i T2 = _mm256_unpackhi_epi32(I0, I1);
__m256i T3 = _mm256_unpackhi_epi32(I2, I3);
__m256i T4 = _mm256_unpacklo_epi32(I4, I5);
__m256i T5 = _mm256_unpacklo_epi32(I6, I7);
__m256i T6 = _mm256_unpackhi_epi32(I4, I5);
__m256i T7 = _mm256_unpackhi_epi32(I6, I7);
I0 = _mm256_unpacklo_epi64(T0, T1);
I1 = _mm256_unpackhi_epi64(T0, T1);
I2 = _mm256_unpacklo_epi64(T2, T3);
I3 = _mm256_unpackhi_epi64(T2, T3);
I4 = _mm256_unpacklo_epi64(T4, T5);
I5 = _mm256_unpackhi_epi64(T4, T5);
I6 = _mm256_unpacklo_epi64(T6, T7);
I7 = _mm256_unpackhi_epi64(T6, T7);
T0 = _mm256_unpacklo_epi128(I0, I4);
T1 = _mm256_unpacklo_epi128(I1, I5);
T2 = _mm256_unpacklo_epi128(I2, I6);
T3 = _mm256_unpacklo_epi128(I3, I7);
T4 = _mm256_unpackhi_epi128(I0, I4);
T5 = _mm256_unpackhi_epi128(I1, I5);
T6 = _mm256_unpackhi_epi128(I2, I6);
T7 = _mm256_unpackhi_epi128(I3, I7);
_mm256_storeu_si256((__m256i *)(dst + ((x + 0) * h) + y), T0);
_mm256_storeu_si256((__m256i *)(dst + ((x + 1) * h) + y), T1);
_mm256_storeu_si256((__m256i *)(dst + ((x + 2) * h) + y), T2);
_mm256_storeu_si256((__m256i *)(dst + ((x + 3) * h) + y), T3);
_mm256_storeu_si256((__m256i *)(dst + ((x + 4) * h) + y), T4);
_mm256_storeu_si256((__m256i *)(dst + ((x + 5) * h) + y), T5);
_mm256_storeu_si256((__m256i *)(dst + ((x + 6) * h) + y), T6);
_mm256_storeu_si256((__m256i *)(dst + ((x + 7) * h) + y), T7);
}
}
}
* 效能分析
* naive
```
Performance counter stats for './naive_transpose' (100 runs):
41,691,591 cache-misses # 86.654 % of all cache refs ( +- 0.24% )
48,112,706 cache-references ( +- 0.22% )
21,074,570 L1-dcache-load-misses # 3.79% of all L1-dcache hits ( +- 0.01% )
555,368,170 L1-dcache-loads ( +- 0.00% )
219,132,867 L1-dcache-stores ( +- 0.00% )
78,851 L1-icache-load-misses ( +- 2.26% )
0.362426909 seconds time elapsed ( +- 0.45% )
```
* sse
```
Performance counter stats for './sse_transpose' (100 runs):
15,237,833 cache-misses # 78.909 % of all cache refs ( +- 0.47% )
19,310,745 cache-references ( +- 0.06% )
8,526,042 L1-dcache-load-misses # 1.91% of all L1-dcache hits ( +- 0.03% )
445,281,290 L1-dcache-loads ( +- 0.00% )
232,777,361 L1-dcache-stores ( +- 0.00% )
98,770 L1-icache-load-misses ( +- 2.42% )
0.266709924 seconds time elapsed ( +- 0.38% )
```
* sse_prefetch
```
Performance counter stats for './sse_prefetch_transpose' (100 runs):
8,041,382 cache-misses # 65.431 % of all cache refs ( +- 0.89% )
12,289,899 cache-references ( +- 0.28% )
8,523,157 L1-dcache-load-misses # 1.83% of all L1-dcache hits ( +- 0.02% )
466,153,254 L1-dcache-loads ( +- 0.00% )
232,714,767 L1-dcache-stores ( +- 0.00% )
71,794 L1-icache-load-misses ( +- 2.35% )
0.168626115 seconds time elapsed ( +- 0.71% )
```
* avx
```
Performance counter stats for './avx_transpose' (100 runs):
10,646,344 cache-misses # 70.440 % of all cache refs ( +- 0.17% )
15,114,039 cache-references ( +- 0.06% )
8,129,909 L1-dcache-load-misses # 2.02% of all L1-dcache hits ( +- 0.03% )
402,956,831 L1-dcache-loads ( +- 0.00% )
210,944,765 L1-dcache-stores ( +- 0.00% )
72,525 L1-icache-load-misses ( +- 1.06% )
0.192949994 seconds time elapsed ( +- 0.20% )
```
| method | cache-misses rate| L1-dcache-load-misses rate |
| ------ | ---------------- | -------------------------- |
| naive | 86.654 % | 3.79% |
| sse | 78.909 % | 1.91% |
| sse prefetcher | 65.431 % | 1.83% |
| avx | 70.440 % | 2.02% |
> 我發現 L1-dcache-load-misses rate 跟最初的版本都一樣，不知道是剛好，還是我操作有問題？待會在測試其他版本試試看
* 時間：
轉置了8*8的矩陣
```
0 1 2 3 4 5 6 7
8 9 10 11 12 13 14 15
16 17 18 19 20 21 22 23
24 25 26 27 28 29 30 31
32 33 34 35 36 37 38 39
40 41 42 43 44 45 46 47
48 49 50 51 52 53 54 55
56 57 58 59 60 61 62 63
0 8 16 24 32 40 48 56
1 9 17 25 33 41 49 57
2 10 18 26 34 42 50 58
3 11 19 27 35 43 51 59
4 12 20 28 36 44 52 60
5 13 21 29 37 45 53 61
6 14 22 30 38 46 54 62
7 15 23 31 39 47 55 63
```
* naive : 231472 us
* sse : 128587 us
* sse_prefetch : 58680 us
* avx : 55967 us
## 參考資料
* [論文 When Prefetching Works, When It Doesn’t, and Why 重點提示和解說](https://hackmd.io/s/HJtfT3icx)
* [論文 When Prefetching Works, When It Doesn’t, and Why ](http://www.cc.gatech.edu/~hyesoon/lee_taco12.pdf)
* [kobeyu 的筆記](https://hackmd.io/s/BycRx2EC)
* [prefetch 相關資料](http://www.ece.cmu.edu/~ece740/f11/lib/exe/fetch.php%3Fmedia%3Dwiki:lectures:onur-740-fall11-lecture24-prefetching-afterlecture.pdf)
Sign in with Wallet
Connect another wallet