---
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 的範例。

        #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 很多，就表示所需要等待的時間可能會更長。

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/)