# 2016q3 Homework1 (compute-pi)
contributed by <`RayPan`>

### 開發環境
* Ubuntu 16.04 LTS
* CPU

Architecture:          x86_64
CPU op-mode(s):        32-bit, 64-bit
Byte Order:            Little Endian
CPU(s):                4
On-line CPU(s) list:   0-3
Thread(s) per core:    2
Core(s) per socket:    2
Socket(s):             1
NUMA node(s):          1
Vendor ID:             GenuineIntel
CPU family:            6
Model:                 60
Model name:            Intel(R) Core(TM) i5-4200H CPU @ 2.80GHz
Stepping:              3
CPU MHz:               2869.015
CPU max MHz:           3400.0000
CPU min MHz:           800.0000
BogoMIPS:              5587.49
Virtualization:        VT-x
L1d cache:             32K
L1i cache:             32K
L2 cache:              256K
L3 cache:              3072K
NUMA node0 CPU(s):     0-3

---
### 開發目標
* 透過離散微積分求圓周率
* Riemann integral
* Leibniz
* 透過SIMD指令做效能最佳化

---

### AVX（Advanced Vector Extensions）
* 指令集
任何程式最後都要編成一條條的指令讓CPU辨識並執行，每一指令對應一個操作，指令集為CPU能執行的所有指令的集合。

* 簡介
是Intel和AMD x86架構處理器中的指令集，借鏡AMD SSE5設計思路，為一套新一代的完整SIMD指令集規範。

* 使用方法
* 需`#define <immintrin.h>`
* `__attribute__`機制，可以用來設置函數屬性（Function Attribute）、變數(Variable)屬性和類型(Type)屬性。
* `aligned`規定變數或結構最小對齊格式，以byte為單位。
---
### Duration Time
計算程式的`duration time`通常可能是指`wall-clock time`或`CPU time`

* #### wall-clock time
現實生活實際經過的時間，由kernel內的xtime紀錄，系統每次啟動時會先從設備上的Real Time Clock(RTC)讀取xtime。

* #### CPU time
程式在CPU上運行消耗的時間，若有多條thread，則是計算每條thread的使用時間加總。
很多時候只計算CPU time不夠，因為執行時間還包括I/O time,communication channel delay,synchronization overhead等等。
* 在Unix系統存在兩個time指令，一是系統所提供/usr/bin/time，為了Bourne shell所寫的工具，另一個是C shell內建指令`$ time`
* `$ time`會報告實際時間（程式從開始到結束經歷時間），還會計算程式使用處理器時間量。
1.`real time`:即wall-clock time。
2.`user time`：程式在user mode佔用所有CPU time總和。
3.`sys time`：程式在kernel mode佔用所有CPU time總和。
* CPU bound/ I/O bound
* CPU bound:程式需要大量CPU computation（對CPU time需求大），相比之下僅需少量I/O operation，效能取決於CPU速度。
* I/O bound：程式需要大量I/O operation，僅需少量CPU computation，效能取決於I/O device速度。
* `real` < `user`：CPU bound，使用平行處理有得到好處，效能提升。
* `real` ≒ `user`：表示程式是 CPU bound，即使使用平行處理，效能也沒有明顯提昇，常見的原因有可能是其實計算量沒有很大，生成、處理、結束多執行緒的 overhead 吃掉所有平行處理的好處，或是程式相依性太高，不適合拿來作平行處理。
* `real` > `user`: 表示程式是 I/O bound，成本大部分為 I/O操作，使得平行處理無法帶來顯著的效能提昇 ( 或沒有提昇)。

---
### Gnuplot
>> 在繪圖中遇到了`Skipping data file with no valid points`
花了半小時debug
發現原因出在`result_clock_gettime.csv`
每筆資料間都用逗號隔開
所以必須在`runtime.gp`內加入`set datafile separator ","` [name=RayPan]

---

### 原始程式效能測試
`$ make check`

time ./time_test_baseline
N = 400000000 , pi = 3.141593
3.34user 0.00system 0:03.34elapsed 99%CPU (0avgtext+0avgdata 1796maxresident)k
0inputs+0outputs (0major+86minor)pagefaults 0swaps
time ./time_test_openmp_2
N = 400000000 , pi = 3.141593
3.42user 0.00system 0:01.71elapsed 199%CPU (0avgtext+0avgdata 1772maxresident)k
0inputs+0outputs (0major+88minor)pagefaults 0swaps
time ./time_test_openmp_4
N = 400000000 , pi = 3.141593
6.77user 0.00system 0:01.71elapsed 395%CPU (0avgtext+0avgdata 1740maxresident)k
0inputs+0outputs (0major+91minor)pagefaults 0swaps
time ./time_test_avx
N = 400000000 , pi = 3.141593
0.97user 0.00system 0:00.97elapsed 99%CPU (0avgtext+0avgdata 1796maxresident)k
0inputs+0outputs (0major+86minor)pagefaults 0swaps
time ./time_test_avxunroll
N = 400000000 , pi = 3.141593
0.94user 0.00system 0:00.94elapsed 99%CPU (0avgtext+0avgdata 1760maxresident)k
0inputs+0outputs (0major+85minor)pagefaults 0swaps

此為baseline的時間消耗（未做openmp)

real	0m3.344s
user	0m3.340s
sys	0m0.000s

此為做了openmp2的時間消耗（可以發現為CPU bound,使用平行處理效能提升）

real	0m1.714s
user	0m3.420s
sys	0m0.000s

此為做了openmp4的時間消耗,效果更為明顯

real	0m1.833s
user	0m7.084s
sys	0m0.016s

---

### 改善過程

#### 1.使用Leibniz

double compute_pi_leibniz(size_t N)
{
    double pi = 0;
    double tmp;
    for(size_t i = 124 < N; i++){
        if(i%2 == 0)
            tmp = 1;
        else
            tmp = -1;
        pi += tmp / (2*(double)i+1);
    }
    return pi * 4.0;
}

可以發現做了Leibniz的效能
比做openmp2及openmp4略好一些

#### 2.使用Leibniz AVX及 AVX unroll


可以發現做leibniz的avx及avx unroll都可以明顯提升效能
但仍是baseline版本的avx unroll最佳。

---
加工中

---
作業詳細資訊：[A03:compute-pi](https://hackmd.io/s/rJARexQT)
###### tags:`RayPan` `A03:Compute-pi`