# 2017q1 Homework3 (software-pipelining)
contributed by < `ect276` >
###### tags: `嵌入式`
**[code here]("https://github.com/etc276/prefetcher")**
## 開發環境
- Ubuntu 16.10 ( 64 bit )
```
Architecture: x86_64
CPU op-mode(s): 32-bit, 64-bit
Byte Order: Little Endian
CPU(s): 4
On-line CPU(s) list: 0-3
Thread(s) per core: 2
Core(s) per socket: 2
Socket(s): 1
NUMA node(s): 1
Vendor ID: GenuineIntel
CPU family: 6
Model: 61
Model name: Intel(R) Core(TM) i7-5500U CPU @ 2.40GHz
Stepping: 4
CPU MHz: 2400.878
CPU max MHz: 3000.0000
CPU min MHz: 500.0000
BogoMIPS: 4788.90
Virtualization: VT-x
L1d cache: 32K
L1i cache: 32K
L2 cache: 256K
L3 cache: 4096K
NUMA node0 CPU(s): 0-3
```
## 預期目標
* 學習計算機結構並且透過實驗來驗證所學
* 理解 prefetch 對 cache 的影響，從而設計實驗來釐清相關議題
* 論文閱讀和思考
## 論文閱讀
### 研究目標
---
探討 SW(軟體) 和 HW(硬體) 在 prefetch(預取) 對於效能影響的機制與交互作用
### 名詞解釋
---
- cache (一種 memory)
由於 CPU 的處理速度大於 RAM 的，所以藉由將等下會用到的資料先放到 cache，以彌補之間的速度差。而因為 cache 的空間較小，所以 prefetch 的技術更顯得重要，才能有效降低 cache miss，而提升效能。
- latency
> cache 對速度有什麼影響呢？這可以由 latency 來表示。CPU 在從記憶體中讀取資料（或程式）時，會需要等待一段時間，這段時間就是 latency，通常用 cycle 數表示。
資料來源：[CPU 的 cache 和 latency [Part 1]]("https://www.csie.ntu.edu.tw/~r89004/hive/cache/page_1.html")
- overhead
overhead 可理解為額外的 penalty，也就是當 cache miss 發生時，才會有的多餘時間，相對於 latency 是總共的 (就算 cache hit 也會有)
資料來源：[記憶體系統-快取記憶體]("http://systw.net/note/af/sblog/more.php?id=252")
- cache miss vs. cache pollution
cache miss 是結果，也就是 CPU 實際預存取的時候是失敗的。而 cache pollution 是原因，例如過早存取 (early prefetch) 以至於實際要用時已被 replaced，或是預先存取了用不到的data (incorrect prefetch)
### 1. Introduction
---
各種 SW 和 HW 組合對效能的影響 ( x 軸是各種 benchmark)
### 2. BACKGROUND ON SOFTWARE AND HARDWARE PREFETCHING
---
不同資料結構與其相對應的 prefetch 的方法
- stream:英文原意為"流"，可以先理解為 row major 然後走 row
- stride:英文原意為"邁"，也就是踏一大步的意思，可以先理解為 走 col
- RDS 在 HW 上就會需要用到指標的幫忙了，並不單純為硬體
- Hash 在 HW 上只能倚賴平行化或預先計算來 prefetch，我理解為不能純硬體了
#### 2.1 Software Prefetch Intrinsics
- intrinsic (內建函式)：function call 時會根據 standard library 編譯成 built-in 的程式碼 (有點像 memset 這個 function 會被編譯成怎麼樣的組語，或是以下)
參考資料：[What are intrinsics?]("http://stackoverflow.com/questions/2268562/what-are-intrinsics")
- inline (內嵌、內聯函式)：可以藉由人工或給編譯器建議，將 function 展開以減少 overhead (在 complie 階段將 function 轉成 instruction cache)，用在少量程式碼的 function 可提升效能，但過於多的 source code 可能會導致 cache miss.
:::danger
intrinsics 不是 inline functions，不要搞錯！ --jserv
:::
#### 2.2 Prefetch Classification
分類 prefetch 的各種情況， timely 最優
#### 2.3 Software Prefetch Classification
>This value D is called the prefetch distance. We define prefetch distance as the distance ahead of which a prefetch should be requested on a memory address
由於 prefetch 的時候會 將記憶體的資料寫進 cache line 裡，也就是其實一次的 prefetch 可能不只抓一筆資料，所以選擇 prefetch distance 就顯得重要，因為若是距離太小，會造成無謂的 prefetch；距離太大則會造成 cache miss (應該要抓進來的資料被跳過了)。
prefetch 其實就是為了"隱藏" latency(預先存取，造成下次要讀取資料不需要時間的假象)，所以 D 要求大於 l，不然就沒有隱藏的效果了。
> 至於除以 s 的用意還不理解，只知道跟 loop 的路徑有關，等待實驗分析後再看看。
#### 2.4 Direct and Indrect Memory Indexing
- SW 在 indirect 的 prefetch 表現比 HW 好
- HW通常處理可預測的 stream, stride 模式
- indirect 可能會造成 SW prefetch overhead (e.g. 兩次 prefetch a[b[i]] )
### 3. POSTIVE AND NEGATIVE IMPACTS OF SOFTWARE PREFETCHING
---
#### 3.1 Benefits of Software Prefetching over Hardware Prefetching
SW 相對於 HW 的優勢通常為較自由，能根據不同情況做調整
- Large Number of Streams (Limited Hardware Resources)
- HW 能處理的 stream prefetch 受限於硬體
- 如 stream detectors和book-keeping mechanisms
- 而 SW 的 stream 則可以根據不同要求做調整
- Short Streams
- HW 的 prefetch 需要訓練
- 太短的 stream 就無法訓練
- 且 HW 需要 2 個 cache miss 才會調整方向
- Irregular Memory Access
- Cache Locality Hint
- 程式開發者使用SW prefetcher時，能自行調整 locality hint
- HW prefetcher 的設計上則是大多將prefetch的資料搬移至lower-level cache ( L2 或 L3 )
- 優點: 減少 L1 cache的 cache pollution
- 缺點: lower-level cache 資料搬移至 L1 的時間(latency)會造成效能下降
- Loop Bounds
- SW 可以確定 prefetch 的次數
- HW 則無法無法有效控制，當 distance 較大時會消耗較多 bandwidth
#### 3.2 Negative Impacts of Software Prefetching
- Increased Instruction Count 指令數會增加
- Static Insertion
在執行時期 (runtime)無法根據以下因素做動態調整
- varying memory latency
- effective cache size
- bandwidth
- especially in heterogeneous architectures
- Code Structure Change
原本 loop 的指令就少的時候，插入多的 prefetch 指令會導致結構改變 (distance 過短無法隱藏 latency)
#### 3.3 Synergistic Effects when Using Software and Hardware Prefetching Together
- Handling Multiple Streams
- SW 和 HW 分工
- SW 處理 irregular stream
- HW 處理 regular stream
- Positive Training
- SW 訓練 HW
- 當 SW 太慢，可以由 HW 取代
#### 3.4 Antagonistic Effects when Using Software and Hardware Prefetching Together
- Negative Training
- SW 的 prefetch request 會降低 HW 的速度
- SW 的指令會引發 HW 的 prefetch，導致 early
- Harmful Software Prefetching
- 單用 SW 的 prefetch 較為精準
- 因為 HW 是由 SW 訓練的，當 SW 出問題會連帶影響
## 開發紀錄
### Original
- 先理解程式碼， `Makefile`裡只有簡單的`$(CC) $(CFLAGS) -o main main.c`
所以 `make` 之後只產生 `main.c`，那我先執行看看
```
sse prefetch: 59432 us
sse: 116758 us
naive: 242177 us
```
- 再回去看 `main.c` 發現有 `#include "impl.c"`，也就是以上三種的實作 code
- 作業要求中有提到要學習 [你所不知道的 C 語言：物件導向程式設計篇](https://hackmd.io/s/HJLyQaQMl) 裡提到的封裝方法
- 為了實作物件導向並統一介面，因此先修改 `Makefile` 並分別產生執行檔
```c=
all: $(GIT_HOOKS) main.c
$(CC) $(CFLAGS) -o main main.c
// before vs. after
EXEC = naive_transpose sse_transpose sse_prefetch_transpose
naive_transpose: main.c
$(CC) $(CFLAGS) -DNAIVE_TRANSPOSE -o $@ main.c
sse_transpose: main.c
$(CC) $(CFLAGS) -DSSE_TRANSPOSE -o $@ main.c
sse_prefetch_transpose: main.c
$(CC) $(CFLAGS) -DSSE_PREFETCH_TRANSPOSE -o $@ main.c
all: $(GIT_HOOKS) $(EXEC)
```
> 這邊或許可以參考 [勃興學長]("https://github.com/0140454/compute-pi/commit/89ab12a144d0ce6d2d3c498e50277fe81c42b8d4")的 commit 用 % 取代 NAIVE_TRANSPOSE (不確定用法，只是突然想到)，等之後改完後面的再回來補
- 以下是 `main.c` 修改的部分內容
```c=
typedef struct object Object;
typedef void (*func_t)(int *src, int *dst, int w, int h);
int init_sse_transpose(Object **self)
{
if ((*self = malloc(sizeof(Object))) == NULL) return -1;
(*self) -> transpose = sse_transpose)
return 0;
}
Object *o = NULL;
#ifdef SSE_TRANSPOSE
if (init_sse_transpose(&o) == -1)
printf("error.");
#endif
...
o->transpose(src, out0, TEST_W, TEST_H);
// change from
// sse_prefetch_transpose(src, out0, TEST_W, TEST_H);
...
#ifdef SSE_TRANSPOSE
printf("SSE_TRANSPOSE: \t %ld us\n", diff_in_us(start, end));
#endif
```
- 接下來要使用 perf 分析效能
```
perf stat --repeat (次數) -e cache-misses,cache-reference,instructions,cycles ./(執行檔)
```
||cache-misses|cache-references|instructions|cycles|
|:---:|:---:|:---:|:---:|:---:|:---:|:---:|
|naive|90.836%|26,325,696|1,465,339,765|1,130,960,634|
|sse|85.321 %|12,703,570|1,253,388,735|771,443,403|
|sse_prefetch|80.887 %|9,710,287|1,299,456,469|625,649,736|
> 這邊可以看到雖然 cache-miss 沒有下降很多，但時間卻大幅降低。這是因為就算是 cache hit，還是會有 L1, L2, L3 的時間差異，例如 L1 -> reg. = 1 cycle，但 L3 -> reg. = 10 cycle (論文中也提到 SW prefetch 較有機會放到 L1)。
:::danger
請從 latency 落差去解釋數據 --jserv
:::
### 實驗一、調整 prefetch distance
- 在進行實驗前，先看懂 `impl.c`
```c=
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);
}
```
- 上面就是一般的轉置，接下來看 sse 的版本
```c=
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 怎麼運作，還有為什麼會比較快
- 運作說明：
- `mm_loadu` 就是把一次把 128 bit 的資料放進 reg.
- `__m128i T0 = _mm_unpacklo_epi32(I0, I1)` 意思是將 I0 和 I1 的 low 128 bit 以 32 bit 為單位交錯放進 T0
- `I0 = _mm_unpacklo_epi64(T0, T1)`就是處理 high 128 bit
- 參考共筆：[ierosodin]("https://hackmd.io/s/rkX95E-il")、[carolc0708]("https://hackmd.io/s/B1lDZtO0#使用avx來提升效能")
- 速度差異：
- 先來看以下一段簡易的程式碼
```=
int p[100][100]={}
for (int i=0; i<100; ++i)
for (int j=0; j<100; ++i)
printf ("%d ", p[i][j]); // stream
for (int i=0; i<100; ++i)
for (int j=0; j<100; ++i)
printf ("%d ", p[j][i]); // stride
```
- 如果拿去分析會發現 `p[j][i]` 較慢，因為 C 語言是 row major，跳著讀取會比較慢 (prefetch 機制)
- 而使用 sse 會比較快的原因是， naive 的寫法我們一次只讀一個 int ，而 sse 一次讀 128 bit，也就是 4 個int，也不會發生跳 row 的問題
- 再來是 sse_prefetch 的版本
```c=
#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);
```
- 這邊看到兩個可以實驗的地方， PFDIST 和 locality
- 先查看一個 loop 會花多久時間 (s)，再除 latency (l)
- 假設這邊 D=8 是 timely 的話，預期結果是 8 > 4=12 > 0=16
- 以下是實驗結果
```
D=0 -> 102078 us
D=4 -> 68133 us
D=8 -> 69905 us
D=12-> 82102 us
D=16-> 81566 us
D=20-> 111937 us
```
- 可以發現 D 差不多是以 8 為一個級距，所以原先的預期錯誤
- 值得一提的是 D=0 還是比沒有 prefetch 的 sse 的版本快
> 這邊不太理解原因，可能要用其他工具分析 latency 才能說明
### 實驗二、修改 locality hint
- 修改 `_MM_HINT_T1` 為 `T2, T3, NTA`，預期結果是時間會越來越長
```
T1 = 81408 us
T2 = 107164 us
T3 = 71822 us
NTA= 86694 us
```
> 為什麼...
### 實驗三、新增 avx 和 avx prefetch 版
```c=
void avx_prefetch_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 ) {
#define PFDISTHUGE 16
_mm_prefetch(src+(y + PFDISTHUGE + 0) *w + x, _MM_HINT_T0);
_mm_prefetch(src+(y + PFDISTHUGE + 1) *w + x, _MM_HINT_T0);
_mm_prefetch(src+(y + PFDISTHUGE + 2) *w + x, _MM_HINT_T0);
_mm_prefetch(src+(y + PFDISTHUGE + 3) *w + x, _MM_HINT_T0);
_mm_prefetch(src+(y + PFDISTHUGE + 4) *w + x, _MM_HINT_T0);
_mm_prefetch(src+(y + PFDISTHUGE + 5) *w + x, _MM_HINT_T0);
_mm_prefetch(src+(y + PFDISTHUGE + 6) *w + x, _MM_HINT_T0);
_mm_prefetch(src+(y + PFDISTHUGE + 7) *w + x, _MM_HINT_T0);
__m256i I0, I1, I2, I3, I4, I5, I6, I7, T0, T1, T2, T3, T4, T5, T6, T7;
I0 = _mm256_loadu_si256((__m256i *)(src + (y + 0) * w + x));
I1 = _mm256_loadu_si256((__m256i *)(src + (y + 1) * w + x));
I2 = _mm256_loadu_si256((__m256i *)(src + (y + 2) * w + x));
I3 = _mm256_loadu_si256((__m256i *)(src + (y + 3) * w + x));
I4 = _mm256_loadu_si256((__m256i *)(src + (y + 4) * w + x));
I5 = _mm256_loadu_si256((__m256i *)(src + (y + 5) * w + x));
I6 = _mm256_loadu_si256((__m256i *)(src + (y + 6) * w + x));
I7 = _mm256_loadu_si256((__m256i *)(src + (y + 7) * w + x));
T0 = _mm256_unpacklo_epi32(I0, I1);
T1 = _mm256_unpackhi_epi32(I0, I1);
T2 = _mm256_unpacklo_epi32(I2, I3);
T3 = _mm256_unpackhi_epi32(I2, I3);
T4 = _mm256_unpacklo_epi32(I4, I5);
T5 = _mm256_unpackhi_epi32(I4, I5);
T6 = _mm256_unpacklo_epi32(I6, I7);
T7 = _mm256_unpackhi_epi32(I6, I7);
I0 = _mm256_unpacklo_epi64(T0, T2);
I1 = _mm256_unpackhi_epi64(T0, T2);
I2 = _mm256_unpacklo_epi64(T1, T3);
I3 = _mm256_unpackhi_epi64(T1, T3);
I4 = _mm256_unpacklo_epi64(T4, T6);
I5 = _mm256_unpackhi_epi64(T4, T6);
I6 = _mm256_unpacklo_epi64(T5, T7);
I7 = _mm256_unpackhi_epi64(T5, T7);
T0 = _mm256_permute2x128_si256(I0, I4, 0x20);
T1 = _mm256_permute2x128_si256(I1, I5, 0x20);
T2 = _mm256_permute2x128_si256(I2, I6, 0x20);
T3 = _mm256_permute2x128_si256(I3, I7, 0x20);
T4 = _mm256_permute2x128_si256(I0, I4, 0x31);
T5 = _mm256_permute2x128_si256(I1, I5, 0x31);
T6 = _mm256_permute2x128_si256(I2, I6, 0x31);
T7 = _mm256_permute2x128_si256(I3, I7, 0x31);
_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);
}
}
}
```
- 由於 avx 是 256 bit (相對於 sse 是 128 bit)，預期時間會是比一半再多一些 (Amdahl’s Law)
- 五個版本的時間比分別是 40 : 14 : 13 : 8 : 11
- 後來想到因為 avx 做的是 8`*`8 的矩陣，所以應該會比 sse 做 4`*`4 的快不到兩倍
Sign in with Wallet
Connect another wallet