2016q3 Homework3 (software-pipelining)

contributed by <0140454>

閱讀資料

SIMD Programming Introduction

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

這個不太了解吳勃興

要記得將問題寄到課程信箱歐，課程助教關心您~劉亮谷

Register Spilling
在電腦中因為 register 的數量有限，所以變數會對應到 register 或 memory 上。而因為 register 不足而要對應到 memory 上的變數就稱為「Spilling Variable」。
Non-Regular Access/Processing Pattern/Dependency

這個不太了解吳勃興

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

在文章中提及現代的設計以及各種議題。雖然文章很長，但是看過之後可以補足在學校「計算機組織」中的不足。

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 不知道到底要抓下一個指令，還是跳轉跳躍後的那一個指令，所以 CPU 只能去預測。

jump 的繁體中文翻譯是「跳躍」，不是「跳轉」，後者為對岸用語 jserv

寫的時候沒有注意到，以後會改進的！吳勃興

預測的方法分為兩種，第一種是靜態的預測，也就交給 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。

以 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