2016q3 Homework3 (mergesort-concurrent)

contribute by <kevinbird61>

tags: kevinbird61 sysprog

閱讀資料-SIMD

SIMD = Single Instruction Multiple Data，主要把原本一個指令中的數值分成多個部份，分配給多個執行緒執行完後再統整程最後結果，加速執行速度

SIMD 優化

• Auto/Semi-Auto method
  • 讓compiler來做vectorization處理（ex: #pragma）
  • 把原本serial的執行變成平行化處理的方式
  • IR Optimization: 對中間語言(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中加上原本的字串資料