# 2016q3 Homework3 (mergesort-concurrent)
contribute by <`kevinbird61`>
###### tags: `kevinbird61` `sysprog`

## 閱讀資料-[SIMD](https://docs.google.com/presentation/d/1LeVe7EAmZvqD3KN7p4Wynbd36xPOk9biBCFrdmsqzKs/edit#slide=id.p3)
SIMD = Single Instruction Multiple Data，主要把原本一個指令中的數值分成多個部份，分配給多個執行緒執行完後再統整程最後結果，加速執行速度

### SIMD 優化

- Auto/Semi-Auto method
- 讓compiler來做vectorization處理（ex: #pragma）
- 把原本serial的執行變成平行化處理的方式
- [IR Optimization](https://web.stanford.edu/class/archive/cs/cs143/cs143.1128/lectures/14/Slides14.pdf): 對中間語言(intermediate representation)的優化
- 為何選擇IR? reason 1: 在從高階語言轉換產生IR後，時常會有一些冗餘的計算，這時候就會成為優化的對象
- 為何選擇IR? reason 2: 由於使用者會使用for loop來做一些型式類似並且多次的運算，減少所寫的code數量。而有時compiler就會做loop unrolling的動作來優化。
- Compiler Intrinsics
- 類似函數，主要差別在於compiler編譯時，會被直接編譯成組合語言
- Specific Framework/Infrastructure
- Data Parallel Framework，主要設計就是為了平行化的目的
- Ex: Apple Accelerate、OpenCV、ffmpeg/x264(影音串流服務的格式，OBS裡頭就有看過)、fftw/Ne10
- Coding in Assembly
- 能夠達到最極致的最佳化的方式（但困難

### SIMD 優化 - 困難部份
- Finding Parallelism in Algorithm(找出原本程式中可以做平行運算的部份)
- Portability between different intrinsics（不同架構中的轉換；Ex: sse -> neon \ neon -> sse）
- Boundary handling
- 提到Padding、Predication、Fallback，但不是很懂
- Divergence
- 提到Predication、Fallback to scalar，也不是很懂
- `Branch Divergence` : occurs when threads inside warps branch to different execution paths.
- 
- Register Spilling
- 編譯產生組合語言時，所使用的variable數量 > register的數量的情況發生稱之
- Non-Regular Access/Processing Pattern/Dependency
- Unsupported Operations
- Floating-Point

# 作業要求
- 使原本mergesort能夠讀取phonebook的資料，我必須改變原本資料儲存的方式、讀入的參數、儲存時的動作
- 原本的開頭字母作為sorting值
- 再structure中加上原本的字串資料