---
tags: ncku-course
---
# 2016q3 Homework3 (software-pipelining)
contributed by <`0140454`>
## 閱讀資料
### [SIMD Programming Introduction](https://goo.gl/Rc8xPE)
#### SIMD 是什麼
在 SIMD 中「車道」可以說是最重要的概念。
有別於傳統的 scalar mode，每次只能對一筆資料做處理，SIMD 則是一條指令，對多組資料進行操作。就有如單車道 vs. 多車道一樣。
而在用到 SIMD 的情況不外乎是為了處理大量資料(如：相機解析度越來越高)、為了更好的效能。因此在各大 framework 中其實都有用到 SIMD，如 OpenCV 等。
#### SIMD 優化方式
SIMD 的使用方式也分為很多種
* Auto/Semi-Auto Method
* 讓 compiler 來負責 vectorization 的處理。
* 透過 `#pragma` 來完成，下方即為 OpenMP 的範例。
```clike=
#pragma omp simd
for (i = 0; i < N; ++i) {
A[i] = B[i] + C[i];
}
```
* IR Optimization：針對 IR 來做優化。
* Compiler Intrinsics
利用 intrinsics 可以讓 compiler 在編譯的時候，直接輸出相對應的 assembly。
例如 `_mm256_add_pd()` 會輸出 `VADDPD`。
* Specific Framework/Infrastructure
直接利用相關的 data parallel framework，或是透過 SIMD 優化過的 library，如 OpenCV。
* Coding in Assembly
為了逼出效能，但比較複雜。
#### SIMD 困難的地方
* Finding Parallelism in Algorithm
要能夠找出演算法中能夠被平行化處理的地方。
* Portability between different intrinsics
在不同平台上就要使用不同的 intrinscis，可攜性是個問題。
* Boundary handling
資料邊界的對齊與填充。以 AVX 為例，每次處理 4 個 double，也就是 32 bytes。
* Divergence
>> 這個不太了解 [name=吳勃興]
>>> 要記得將問題寄到課程信箱歐，課程助教關心您~[name=劉亮谷]
* Register Spilling
在電腦中因為 register 的數量有限，所以變數會對應到 register 或 memory 上。而因為 register 不足而要對應到 memory 上的變數就稱為 「Spilling Variable」。
* Non-Regular Access/Processing Pattern/Dependency
>> 這個不太了解 [name=吳勃興]
* Unsupported Operations
比較高階的函數，例如數學函數等等。
* Floating-Point
浮點數運算跨裝置上的相容性問題。
#### SIMD 中重要的地方
* ISA Design
* SuperScaler vs. VLIW (Very Long Instruction Word)
* Vector Register Design
* ALU
* Inter-Lane
* Multiply
* Memory Access
* Scalar ↔ Vector
* Memory Model
從主記憶體抓資料到 register 的延遲很高。所以資料的快取會分為下面幾種方式。
* Buffer between Host Processor and SIMD Processor
* TCM (Tightly Coupled Memory)
TCM 是一個固定大小的 RAM，緊密地耦合至處理器中，提供與 cache 相當的效能。
相較於 cache，TCM 的優點是，程式碼可以精確地控制函數或程式碼該放在哪個位置中。
除此之外，cache 屬於統計性的快取，所以被快取起來的資料可能會被取代，但 TCM 並不會。
* Cache
* Mixed
### [Modern Microprocessors (A 90-Minute Guide!)](http://www.lighterra.com/papers/modernmicroprocessors/)
在文章中提及現代的設計以及各種議題。雖然文章很長，但是看過之後可以補足在學校「計算機組織」中的不足。
#### More Than Just Megahertz
以一份簡潔的分數測試報告來說明時脈不代表效能，真正的效率取決於「在一個 clock cycle 中能做多少事情」。
#### Pipelining & Instruction-Level Parallelism
將 CPU 處理資料的部份分為數個 stage，藉由這種設計可以讓處理的效率更好，因為每個 stage 在任意時間都有在工作。
而各個 stage 間是利用 latch 來傳遞資料給下一個 stage。
除此之外，因為資料的相依性，所以會從 Execute 或 Writeback 之後拉一條線到 Execute 之前，這樣可以減少不必要的等待。
再來就是，Execute 階段中其實是由好幾組邏輯運算單元組成。
#### Multiple Issue – Superscalar
如同上一部份所說，Execute 中有好幾組邏輯運算單元，一條指令中不一定都會用到全部的運算單元，所以我們可以多讀取指令，依照所需分配到不同路徑。
利用上面 pipeline 的圖案呈現出來就像這樣
#### Explicit Parallelism – VLIW
VLIW 也就是 **Very Long Instruction Word**。表示一條指令中可以執行多種操作。
好處是不用檢查資料相依性。壞處是遇到 cache miss 的話，處理器就要在那邊空等。
#### Instruction Dependencies & Latencies
既然 pipeline 可以讓 CPU 使用地更有效率，那我們只要把 stage 跟的更細，效能就會變得更好？從文章中得到的答案是否定的。
在文中的例子，Line 2 必須等待 Line 1 運算的結果，如果 stage 很多，就表示所需要等待的時間可能會更長。
```clike=
a = b * c;
d = a + 1;
```
而當一個指令從 Execute 階段到運算的資料能夠被其他指令使用，其中所經過的時間就叫 Instruction Latency。
#### Branches & Branch Prediction
當遇到 branch instruction 時，CPU 不知道到底要抓下一個指令，還是<s>跳轉</s> 跳躍後的那一個指令，所以 CPU 只能去預測。
>> jump 的繁體中文翻譯是「跳躍」，不是「跳轉」，後者為對岸用語 [name=jserv]
>>> 寫的時候沒有注意到，以後會改進的！ [name=吳勃興]
預測的方法分為兩種，第一種是靜態的預測，也就交給 compiler 來做個 mark。第二種則是由 CPU 來根據過往的紀錄來進行預測。
文中也以 Pentium Pro/II/III 舉例，再怎麼聰明的 predictor 也只有 90% 的正確率，而預測失敗時會損失 30% 的效能。換句話說，Pentium Pro/II/III 有三分之一的時間根本沒做到什麼事，只在那邊說「糟糕~ 錯了」。
為了避免 branch instruction，所以有些平台會提供 conditional move instruction。
#### Instruction Scheduling, Register Renaming & OOO
這一個區段主要的概念就是重新排序指令避免各種 hazard 跟 latency。
根據重新排序的方式可以分為靜態與動態。
* 靜態：讓 compiler 來重新排序。
* 動態：在 runtime 時，由 CPU 來往後看幾個指令，進行排序。又稱為 Out-of-Order (OOO)，優點是有些指令在 runtime 時才能夠更準確的去排，但缺點是 OOO 所需要的功耗較高。
#### The Power Wall & The ILP Wall
* The Power Wall
當增加 20% 的 clock speed，功耗就增加更多，如 50%。
為了提升 clock speed 而必須要提供更多的電力以及改善散熱能力，並不那個簡單，所以在這邊就遇到了一個瓶頸，稱之為 The Power Wall。
* The ILP Wall
因為程式中的 load latency、cache miss、branch prediction 等問題，讓程式沒辦法有效得平行化，導致所謂的 The ILP Wall。
#### What About x86?
在現今的 x86 架構中，會把原先的 x86 指令轉換成類似 RISC 的指令才進行處理。那些類 RISC 的指令又稱為 micro ops。
#### Threads – SMT, Hyper-Threading & Multi-Core
* SMT (Simultaneous Multi-Threading)
在傳統的狀況下，當有 thread 空閒時，會切換至其他 thread，但如此一來，資源就無法更有效的被利用。
而 SMT 簡單來說就是在 CPU 中同時執行兩個 thread。等於把 thread level parallelism 轉換成 instruction level parallelism。
* Multi-Core
將多個核心封裝至一個 chip 中。
#### More Cores or Wider Cores?
SMT 的核心通常會比較大一點，在相同大小的情況下，可以放入較多的普通核心。
那哪一種會比較好？端看程式的用途。
* 普通核心：適合比較活躍但受限於 memory latency 的應用程式，如資料庫系統、3D 圖形渲染等。因為 SMT 核心會花較多的時間在等待記憶體上。
* SMT 核心：對於大部分的應用程式都適用，因為單執行緒的效能會比較重要。
#### Memory & The Memory Wall
為了從記憶體當中載入資料，會花費許多時間，導致效能受到限制，這種情況就叫 The Memory Wall。
所以在現今的設計中都會使用 cache 來進行快取。
#### Caches & The Memory Hierarchy
cache 是一個緊鄰處理器，速度快但容量小的記憶體。
因為容量小，一定不可能把需要的資料都快取起來，所以採用階層式的概念來快取資料。
如 L1 cache、L2 cache、L3 cache，速度由快到慢，大小由小到大。
另外，根據不同的設計，可以分為 direct-mapped cache、N-way set associative cache。可以參考 [淺談memory cache « EngineC's Blog](http://enginechang.logdown.com/posts/249025-discussion-on-memory-cache)。
## 以 AVX 改寫 Prefetcher
### 閱讀 SSE 版本
**用到的 SSE 函式**
在 SSE 版本中，主要透過以下函數達成目標。
根據 Intel Intrinsics Guide，我們可以知道函式的內部操作為何。
* \_mm_unpacklo_epi32()
```=
_mm_unpacklo_epi32(src1[127:0], src2[127:0]) {
dst[31:0] := src1[31:0]
dst[63:32] := src2[31:0]
dst[95:64] := src1[63:32]
dst[127:96] := src2[63:32]
return dst
}
```
* \_mm_unpackhi_epi32()
```=
_mm_unpackhi_epi32(src1[127:0], src2[127:0]) {
dst[31:0] := src1[95:64]
dst[63:32] := src2[95:64]
dst[95:64] := src1[127:96]
dst[127:96] := src2[127:96]
return dst
}
```
* \_mm_unpacklo_epi64()
```=
_mm_unpacklo_epi64(src1[127:0], src2[127:0]) {
dst[63:0] := src1[63:0]
dst[127:64] := src2[63:0]
return dst
}
```
* \_mm_unpackhi_epi64()
```=
_mm_unpackhi_epi64(src1[127:0], src2[127:0]) {
dst[63:0] := src1[127:64]
dst[127:64] := src2[127:64]
return dst
}
```
**理解實作想法**
首先，在載入資料後，資料的分佈如下
```
0 32 64 96 128
+-------+-------+-------+-------+
I0 | I00 | I01 | I02 | I03 |
+-------+-------+-------+-------+
I1 | I10 | I11 | I12 | I13 |
+-------+-------+-------+-------+
I2 | I20 | I21 | I22 | I23 |
+-------+-------+-------+-------+
I3 | I30 | I31 | I32 | I33 |
+-------+-------+-------+-------+
```
透過 `_mm_unpacklo_epi32()` 與 `_mm_unpackhi_epi32()` 操作後，可以得到
```
0 32 64 96 128
+-------+-------+-------+-------+
T0 | I00 | I10 | I01 | I11 |
+-------+-------+-------+-------+
T1 | I20 | I30 | I21 | I31 |
+-------+-------+-------+-------+
T2 | I02 | I12 | I03 | I13 |
+-------+-------+-------+-------+
T3 | I22 | I32 | I23 | I33 |
+-------+-------+-------+-------+
```
最後使用 `_mm_unpacklo_epi64()` 與 `_mm_unpackhi_epi64()`
```
0 32 64 96 128
+-------+-------+-------+-------+
I0 | I00 | I10 | I20 | I30 |
+-------+-------+-------+-------+
I1 | I01 | I11 | I21 | I31 |
+-------+-------+-------+-------+
I2 | I02 | I12 | I22 | I32 |
+-------+-------+-------+-------+
I3 | I03 | I13 | I23 | I33 |
+-------+-------+-------+-------+
```
這樣就完成轉至的動作了。
### 實作 AVX 版本
依樣畫葫蘆，依照 SSE 版本的想法來擴展成 AVX 版本。
一開始，一樣是先載入資料
```
0 32 64 96 128 160 192 224 256
+-------+-------+-------+-------+-------+-------+-------+-------+
I0 | I00 | I01 | I02 | I03 | I04 | I05 | I06 | I07 |
+-------+-------+-------+-------+-------+-------+-------+-------+
I1 | I10 | I11 | I12 | I13 | I14 | I15 | I16 | I17 |
+-------+-------+-------+-------+-------+-------+-------+-------+
I2 | I20 | I21 | I22 | I23 | I24 | I25 | I26 | I27 |
+-------+-------+-------+-------+-------+-------+-------+-------+
I3 | I30 | I31 | I32 | I33 | I34 | I35 | I36 | I37 |
+-------+-------+-------+-------+-------+-------+-------+-------+
I4 | I40 | I41 | I42 | I43 | I44 | I45 | I46 | I47 |
+-------+-------+-------+-------+-------+-------+-------+-------+
I5 | I50 | I51 | I52 | I53 | I54 | I55 | I56 | I57 |
+-------+-------+-------+-------+-------+-------+-------+-------+
I6 | I60 | I61 | I62 | I63 | I64 | I65 | I66 | I67 |
+-------+-------+-------+-------+-------+-------+-------+-------+
I7 | I70 | I71 | I72 | I73 | I74 | I75 | I76 | I77 |
+-------+-------+-------+-------+-------+-------+-------+-------+
```
經過 `_mm256_unpacklo_epi32()` 與 `_mm256_unpackhi_epi32()` 後
```
0 32 64 96 128 160 192 224 256
+-------+-------+-------+-------+-------+-------+-------+-------+
T0 | I00 | I10 | I01 | I11 | I04 | I14 | I05 | I15 |
+-------+-------+-------+-------+-------+-------+-------+-------+
T1 | I20 | I30 | I21 | I31 | I24 | I34 | I25 | I35 |
+-------+-------+-------+-------+-------+-------+-------+-------+
T2 | I40 | I50 | I41 | I51 | I44 | I54 | I45 | I55 |
+-------+-------+-------+-------+-------+-------+-------+-------+
T3 | I60 | I70 | I61 | I71 | I64 | I74 | I65 | I75 |
+-------+-------+-------+-------+-------+-------+-------+-------+
T4 | I02 | I12 | I03 | I13 | I06 | I16 | I07 | I17 |
+-------+-------+-------+-------+-------+-------+-------+-------+
T5 | I22 | I32 | I23 | I33 | I26 | I36 | I27 | I37 |
+-------+-------+-------+-------+-------+-------+-------+-------+
T6 | I42 | I52 | I43 | I53 | I46 | I56 | I47 | I57 |
+-------+-------+-------+-------+-------+-------+-------+-------+
T7 | I62 | I72 | I63 | I73 | I66 | I76 | I67 | I77 |
+-------+-------+-------+-------+-------+-------+-------+-------+
```
再經過 `_mm256_unpacklo_epi64()` 與 `_mm256_unpackhi_epi64()` 後
```
0 32 64 96 128 160 192 224 256
+-------+-------+-------+-------+-------+-------+-------+-------+
I0 | I00 | I10 | I20 | I30 | I04 | I14 | I24 | I34 |
+-------+-------+-------+-------+-------+-------+-------+-------+
I1 | I01 | I11 | I21 | I31 | I05 | I15 | I25 | I35 |
+-------+-------+-------+-------+-------+-------+-------+-------+
I2 | I40 | I50 | I60 | I70 | I44 | I54 | I64 | I74 |
+-------+-------+-------+-------+-------+-------+-------+-------+
I3 | I41 | I51 | I61 | I71 | I45 | I55 | I65 | I75 |
+-------+-------+-------+-------+-------+-------+-------+-------+
I4 | I02 | I12 | I22 | I32 | I06 | I16 | I26 | I36 |
+-------+-------+-------+-------+-------+-------+-------+-------+
I5 | I03 | I13 | I23 | I33 | I07 | I17 | I27 | I37 |
+-------+-------+-------+-------+-------+-------+-------+-------+
I6 | I42 | I52 | I62 | I72 | I46 | I56 | I66 | I76 |
+-------+-------+-------+-------+-------+-------+-------+-------+
I7 | I43 | I53 | I63 | I73 | I47 | I57 | I67 | I77 |
+-------+-------+-------+-------+-------+-------+-------+-------+
```
稍微調整順序，比較好對照
```
0 32 64 96 128 160 192 224 256
+-------+-------+-------+-------+-------+-------+-------+-------+
I0 | I00 | I10 | I20 | I30 | I04 | I14 | I24 | I34 |
+-------+-------+-------+-------+-------+-------+-------+-------+
I1 | I01 | I11 | I21 | I31 | I05 | I15 | I25 | I35 |
+-------+-------+-------+-------+-------+-------+-------+-------+
I4 | I02 | I12 | I22 | I32 | I06 | I16 | I26 | I36 |
+-------+-------+-------+-------+-------+-------+-------+-------+
I5 | I03 | I13 | I23 | I33 | I07 | I17 | I27 | I37 |
+-------+-------+-------+-------+-------+-------+-------+-------+
I2 | I40 | I50 | I60 | I70 | I44 | I54 | I64 | I74 |
+-------+-------+-------+-------+-------+-------+-------+-------+
I3 | I41 | I51 | I61 | I71 | I45 | I55 | I65 | I75 |
+-------+-------+-------+-------+-------+-------+-------+-------+
I6 | I42 | I52 | I62 | I72 | I46 | I56 | I66 | I76 |
+-------+-------+-------+-------+-------+-------+-------+-------+
I7 | I43 | I53 | I63 | I73 | I47 | I57 | I67 | I77 |
+-------+-------+-------+-------+-------+-------+-------+-------+
```
最後透過 `_mm256_permute2x128_si256()` 重新整理一下
```
0 32 64 96 128 160 192 224 256
+-------+-------+-------+-------+-------+-------+-------+-------+
T0 | I00 | I10 | I20 | I30 | I40 | I50 | I60 | I70 |
+-------+-------+-------+-------+-------+-------+-------+-------+
T1 | I01 | I11 | I21 | I31 | I41 | I51 | I61 | I71 |
+-------+-------+-------+-------+-------+-------+-------+-------+
T2 | I02 | I12 | I22 | I32 | I42 | I52 | I62 | I72 |
+-------+-------+-------+-------+-------+-------+-------+-------+
T3 | I03 | I13 | I23 | I33 | I43 | I53 | I63 | I73 |
+-------+-------+-------+-------+-------+-------+-------+-------+
T4 | I04 | I14 | I24 | I34 | I44 | I54 | I64 | I74 |
+-------+-------+-------+-------+-------+-------+-------+-------+
T5 | I05 | I15 | I25 | I35 | I45 | I55 | I65 | I75 |
+-------+-------+-------+-------+-------+-------+-------+-------+
T6 | I06 | I16 | I26 | I36 | I46 | I56 | I66 | I76 |
+-------+-------+-------+-------+-------+-------+-------+-------+
T7 | I07 | I17 | I27 | I37 | I47 | I57 | I67 | I77 |
+-------+-------+-------+-------+-------+-------+-------+-------+
```
### 初步比較效能
| Version | Execution Time |
| ----------- | --------------: |
| naive | 248612 us |
| sse | 123132 us |
| sse_prefetch | 67011 us |
| avx | 65545 us |
| avx_prefetch | 63032 us |
> uncompleted
## 參考資料
* [对ARM紧致内存TCM的理解 转](http://blog.csdn.net/sergeycao/article/details/6030226)
* [Register allocation - Wikipedia](https://en.wikipedia.org/wiki/Register_allocation)
* [Intel Intrinsics Guide](https://software.intel.com/sites/landingpage/IntrinsicsGuide/)
Sign in via Facebook
Sign in via X(Twitter)
Sign in via GitHub
Sign in via Dropbox
Sign in with Wallet
Connect another wallet