# SIMD Programing Introduction 演講筆記
contributed by <Yen-Kuan Wu>

###### tag `Champ` `Yen-Kuan` `SIMD` `half-done`

演講標題: SIMD Programming Introduction
演講者: Champ Yen
演講日期: Oct 14, 2016
投影片連結: [SIMD Programming Introduction](https://goo.gl/Rc8xPE)==記得搭配原來的 PPT歐==

# SIMD Mode vs Scalar Mode [P.3]
* SIMD 即是 Single instruction Mutiple data，一次能做多個運算，而 Scalar 則是我們一般循序漸進的算法。
> SIMD 並不是萬能的，在之後能看到他不是 support 所有的運算 [name=Yen-Kuan Wu]

----

# SIMD 的應用 [P.5]

1. **CPU**(MMX/SSE/AVX)
2. **GPU**
3. **DSP**
>SIMD 已經應用在上述的裝置中 [name=Yen-Kuan Wu]

----

# SIMD Optimization [P.10]
主要分類如下:
1. Auto/Semi-Auto Method
2. Compiler Intrinsics
3. Specific Framework/Infrastructure
4. Coding in Assembly
>我個別舉了幾個例子出來[name=Yen-Kuan Wu]

## Auto/Semi-Auto Method [P.11]
> 這邊使用 OpenMp，不用動原本的 code 只需要加上 '#pragma omp simd'，OpenMP 就會把你的向量運算轉換成 SIMD!!!，可是記得要符合 OpenMP 的一些條件 [name=Yen-Kuan Wu]
> - [ ]OpenMP的限制?

---
## Compiler Intrinsics [P.13]

* Intel SSE/AVX
* ARM NEON/MIPS ASE
> instrinsic 是編譯器透過函式形式，提供開發者得以指定硬體指令的機制，往往直接對應到機械碼[name=jserv]

>上圖解釋了一簡很重要的事情，就是讀 column 和 row 所帶來的 latency 是有極大差異的，cache 依次是讀進一個 line 的，所以讀column，會需要抓 4 個 line，反之 row 只需要一個 line[name=Yen-Kuan Wu]
>再來是線性代數，我們可以全部使用 row 的方式算出矩陣乘法，最後是挑選 4\*4 是有意義的，首先就是跟 SIMD 的 register 的大小，再來是很多大型的矩陣運算都能拆成很多 4\*4 的矩陣運算在合起來[name=Yen-Kuan Wu]

---
## Data Parallel Frameworks [P.14]

* ==OpenCL/Cuda==/C++AMP
* ==OpenVX/Halide==
* SIMD-Optimized Libraries
* Apple Accelerate
* OpenCV
* ffmpeg/x264
* fftw/Ne10
>在 OpenCV 及 ffmpeg ...等，能夠找到 SIMD 優化的 flag[name=Yen-Kuan Wu]

---
## Coding in Assembly [P.15]
### 我們可以看到 assembly 的 code 會有更好的效能，但是為什麼呢?
>assembly 讓我們能精準地控制 code 的 size 和 cycle 和 register 的使用 [name=Yen-Kuan Wu]
>> 有做過 HW3 prefetch 的同學就會知道，`Prefetch Distance`的計算會需要有整個 loop 的 cycle，如果還不太清楚的記得去看 [When Prefetching Works, When It Doesn’t, and Why](http://www.cc.gatech.edu/~hyesoon/lee_taco12.pdf)，他整理的非常清楚! [name=Yen-Kuan Wu]

---

# The difficult parts in SIMD [P.16]

* Finding Parallelism in Algorithm
> 好的平行演算法才能發揮出 SIMD 該有的性能。[name=Yen-Kuan Wu]
* Boundary handling
> 由於 SIMD 都是一次讀取多個 word，所以 alignment 是個很重要的議題。[name=Yen-Kuan Wu]
* Divergence
> 沒有支援一次把四個 int 加起來 return。[name=Yen-Kuan Wu]
* Register Spilling
> 當使用超過 SIMD 專用的 register 時，就必須要存到 stack 去，這個的 overhead 是非常大的。[name=Yen-Kuan Wu]
* Unsupported Operations
> SIMD 沒有支援除法，可能原因也是除法器不太好做而且也很耗時間。[name=Yen-Kuan Wu]
> - [ ] 除法 clz SIMD

# 影響 SIMD 的重要因素 [P.17 18]

   /\     -> Architecture
  /  \    -> ILP Programming
 /    \   -> TLP Programming
/      \  -> Data Parallel Algorithm
--------

* Data Parellel Alogrithm
> 我們得要選擇一個有較多平行化空間的演算法，來發揮 SIMD 真正的功用。
* Thread Level Parallelism
* Instruction Level Parallelism[Wikipedia](https://en.wikipedia.org/wiki/Instruction-level_parallelism)
> 直接舉例較常見的技術: Instruction piplining, Superscalar, VLIW, Out-of-order execution ...
* Architecture

## ISA design

* SuperScalar vs VLIW
> SuperScalar 講簡單一點就是指令的並行(ILP)數量增加，主要是讓 CPU 能夠充分使用 resource ，舉個例子，一顆 CPU 裡面可以做多個 ALU，所以現在有兩個指令都進到 ALU stage，那麼他們就有機會能同步執行，所以 SuperScalar 主要是讓現在可以用的 resourse 都充分運用。
> - [ ] VLIW
* Memory Hierarchy
> Scatter 是指寫入不連續的記憶體，Gather 則是說讀入不連續的記憶體，這兩者都會讓 cache overhead 很高。[name=Yen-Kuan Wu]

## Memory Hierarchy

>首先，先釐清 L1 vs L2 vs DRAM 的 access time
>L1 => Register 1 cycle
>L2 => Register 3-5 cycle
>DRAM=>Register 100up cycle
>>所以我們就知道，有效的 cache 使用會增進的效能可以很多的。[name=Yen-Kuan Wu]

## Thread / Execution Model

# Q&A

> Q: 使用 prefetch 到底可不可以減少 cache-miss 呢?
>> A:

> Q: 該如何驗證我的 prefetch 有沒有正確使用到呢?
>> A:這牽扯很多部分，

> Q: 我使用 i7-8core 的 CPU，並且使用了 muti-thread 的方式來跑 SIMD，為什麼 8 個 thread 的時間跟 4 個thread 的時間差不多呢?
>
>> A: 目前的 i7 其實只有四核，那為什麼說自己有 8 核呢? 因為 Hyper Threading，簡單說明一下，Hyper Threading 其實一個 core 裡面支援可以跑兩個 thread，這個想法式建構在我們有多的 resource 也是有多個 ALU agent(或者其他的)，所以在某些情況下是有可能讓兩個 thread 一起跑的，但是其實 SIMD agent 每個 core 都只有一個，更何況 SIMD 專用的 register 也是只有一組，所以我們是沒有辦法平行的跑 SIMD的，這也是為什麼 8 個 thread 不會有更好的效能(就真的只有四倍)。[name=Yen-Kuan Wu]

# 我是零碎筆記區
instrinsics = 給 compiler 用的特殊指令及，他會生成比較好的 machine code
P1 執的事 lane

cache line

L1 > register 1
L2 3 - 5
main 100 -

p13

till base
考慮 mulitple

p14
Halide 很重要 可以快速複習 computer architecture
slide window 把計算過的東西存進 mem，最不要

computing
/ |
/ |
-----|
data data(slide window)

練神功了 P15

Extreme Performance

register bill: register 滿了 存到 stack 去

p16
boundary hand
> padding 補齊

Divergence
>predication 32 做if 32做 else

都不支援除法

floating point 常不支援

有什麼辦法，控制 cycle ？ disassembly 或是 asm

P17

SIMD = 在 ILP

TLP = thread level parallel

architecture 不 friendly ?

p19
**SuperScalar** vs **VLIW**
vector register
accumulator 依連串的加法，再做除法
Inter-Lane - ex: 在 lane 裡挑出最大的執 or 全部加在一起給我一個結果
Memory Access
- Scatter 寫出去的不是連續 Gather 讀的不是連續的
- LUT: look up table
- DMA

p20

data： MEM > REG

hardware prefetch:
software prefetch:

Buffer sharing
- GPU mem CPU mem

TCM
- scratch mem (DMA)
-

Cache
- transparent 透明的
- portable

p21
trigger overhead 要 GPU去算 也要考慮搬過去
mem 移到 GPU 會有 overhead