# 2017q1 Homework1 (compute_pi)
contributed by <`yangyang95`>

## Reviewed by `PeterTing`

* 嘗試對蒂卡羅算法進行優化，像是用 OpenMP , SIMD 等等。
* 可以嘗試計算 error rate 並進行分析。
* 可以對不同的時間函數進行研究。
* 要對圖表進行分析，不然放出來只是好看的

###### tags: `sysprog2017` `HW1` `yangyang95`
電腦規格看 [這裡](https://hackmd.io/s/HJ2c_XYKx)
github page 看 [這裡](https://github.com/yangyang95/compute-pi)
## 分析程式
N = 400000000 , pi = 3.141593

./time_test_baseline
3.61user 0.00system 0:03.61elapsed 99%CPU (0avgtext+0avgdata 1740maxresident)k
0inputs+0outputs (0major+79minor)pagefaults 0swaps

./time_test_openmp_2
3.78user 0.01system 0:01.90elapsed 199%CPU (0avgtext+0avgdata 1840maxresident)k
0inputs+0outputs (0major+86minor)pagefaults 0swaps

./time_test_openmp_4
7.40user 0.01system 0:01.90elapsed 390%CPU (0avgtext+0avgdata 1784maxresident)k
0inputs+0outputs (0major+86minor)pagefaults 0swaps

./time_test_avx
1.57user 0.00system 0:01.57elapsed 99%CPU (0avgtext+0avgdata 1708maxresident)k
0inputs+0outputs (0major+77minor)pagefaults 0swaps

./time_test_avxunroll
1.44user 0.00system 0:01.44elapsed 100%CPU (0avgtext+0avgdata 1832maxresident)k
0inputs+0outputs (0major+82minor)pagefaults 0swaps

試着做一些分析
- CPU 時間 = CPU 時脈週期 * 週期時間 = CPU 時脈週期 / 頻率
- system time ： kernel mode 所花費的 CPU 時間 (e.g. system calls)
- user time ： user mode 所花費的 CPU 時間
- real time ： 可以看成"當程式開始時看一次手錶,結束時再看一次,兩者的時間差"
- user time + system time > real time --> multi-thread
- user time + system time < real time --> interrupt
- %CPU - CPU 使用率，可大於 100 % （多核心使用）

先來看看 **baseline 版本** 的執行時間
user time：3.61 s
system time：0.00
elapsed time：3.61 s
可以看出 real (elapsed) time = user time + system time ，是單執行緒且沒有發生中斷。

再來是 **openmp_2 版本**
user time：3.78 s
system time：0.01 s
elapsed time：1.90 s
real time < user time + system time ，果然是多執行緒程式。

**openmp_4 版本**
user time：7.40 s
system time：0.01 s
elapsed time：1.90 s
user time 相對兩個執行緒增加大約兩倍，但實際執行時間卻沒有差異。

**AVX SIMD (Single instruction, multiple data) 版本**
註：圖內的 PU 指的是 Process Unit

是單指令流多資料流，也就是說採用一個控制器來控制多個處理器，同時對一組資料（又稱「資料向量」）中的每一個分別執行相同的操作。

現代處理器加入 SIMD 是為了提升多媒體資料的使用效能。

由數據可以看出 CPU 使用率並沒有超過 100% ，卻能平行處理資料。是故可以觀察出 SIMD 使用的是資料平行來增加效能，而非 OpenMP 使用的任務平行。

從執行時間也可以看出同樣結論：
user time：1.57 s
system time：0.00
elapsed time：1.57 s
並沒有使用到系統時間，也就是沒有進到內核去分配執行緒。

最後，除了時間資訊跟 CPU 使用率，後面那一堆資料意味不明 XD

參考資料：
- [CPU Time](https://chi_gitbook.gitbooks.io/personal-note/content/cpu_time.html)
- [vic85821 HackMD 筆記](https://hackmd.io/s/rkgYN0P6#)
- [Understanding %CPU while running top command](http://unix.stackexchange.com/questions/145247/understanding-cpu-while-running-top-command)
- [SIMD](https://en.wikipedia.org/wiki/SIMD)
- [Data parallelism](https://en.wikipedia.org/wiki/Data_parallelism)
- [Task parallelism](https://en.wikipedia.org/wiki/Task_parallelism)

## 實驗數據繪圖
使用`$ make gencsv`來產生數據並匯入 csv 檔

gencsv: default
    for i in `seq 100 100 25000`; do \
        printf "%d," $$i;\
        ./benchmark_clock_gettime $$i; \
    done > result_clock_gettime.csv	

修改程式增加資料點，以 100 的間隔從 0 到 25000 。

再加入 gnuplot 的 script

reset
set xlabel 'N'
set ylabel 'time(sec)'
set grid
set title 'Comput pi time'
set term png enhanced font 'Verdana,10'
set datafile separator ','
set output 'runtime.png'

plot [:20100][:]'result_clock_gettime.csv' using 1:2 smooth csplines title 'baseline' lw 3, \
'' using 1:3 smooth csplines title 'openmp2' lw 3, \
'' using 1:4 smooth csplines title 'openmp4' lw 3, \
'' using 1:5 smooth csplines title 'avx' lw 3, \
'' using 1:6 smooth csplines title 'avxunroll' lw 3

以 cubic spline 的曲線來進行繪圖，得到以下結果：

參考資料：
- [Smooth](http://gnuplot.sourceforge.net/docs_4.2/node124.html)
- [談談 gnuplot（三十九）：數據平滑](http://blog.sciencenet.cn/blog-373392-528809.html)

## Monte Carlo
在 computepi.c 中加入蒙地卡羅的實作

double compute_pi_MonteCarlo(size_t N)
{
    int sum = 0;
    srand((unsigned)time(NULL));
    for(size_t i = 0; i < N; i++) {
        double x = (double)rand() / (double)RAND_MAX;
        double y = (double)rand() / (double)RAND_MAX;

        if((x * x + y * y) <= 1)
            sum++;
    }
    return 4.0 * sum / N;
}

> 註：時間竟然有負的，看來時間量測的方法真的蠻重要的XD

執行蒙蒂卡羅算法來測定執行時間：

$ time ./time_test_monte_carlo

N = 400000000 , pi = 3.141602
./time_test_monte_carlo  9.54s user 0.00s system 99% cpu 9.546 total

可以看出蒙蒂卡羅耗費相當長的時間，且結果有一定程度的誤差。

參考資料：
- [Estimating Pi using Monte Carlo Simulation - youtube](https://www.youtube.com/watch?v=VJTFfIqO4TU)
- [CheHsuan HackMD 筆記](https://hackmd.io/s/BkbydgVa)