# 2017q1 Homework1 (compute-pi)
contributed by< `claaaaassic` >
### Reviewed by <`hugikun999`>
* 透過信賴區間的方法降低發生極值的發生，讓 baseline 振盪幅度變小。
* AVX 在實作上有缺失造成 error rate 會有固定的跳動現象。
* 解釋在 Leibniz formula for π 中，為何 baseline 會有不尋常的跳動現象。
* error rate 可以比較所有版本，而非只有其中一些。
* 解釋為何切換視窗只對 openMP4 產生較大的影響，可以針對執行序數目做分析。
## 作業環境
```shell
Architecture: x86_64
CPU 作業模式： 32-bit, 64-bit
Byte Order: Little Endian
CPU(s): 4
On-line CPU(s) list: 0-3
每核心執行緒數：2
每通訊端核心數：2
Socket(s): 1
NUMA 節點： 1
供應商識別號： GenuineIntel
CPU 家族： 6
型號： 42
Model name: Intel(R) Core(TM) i5-2410M CPU @ 2.30GHz
製程： 7
CPU MHz： 892.962
CPU max MHz: 2900.0000
CPU min MHz: 800.0000
BogoMIPS: 4589.57
虛擬： VT-x
L1d 快取： 32K
L1i 快取： 32K
L2 快取： 256K
L3 快取： 3072K
NUMA node0 CPU(s): 0-3
```
## 作業要求
* 在 GitHub 上 fork [compute-pi](https://github.com/sysprog21/compute-pi)，嘗試重現實驗，包含分析輸出
* 注意: 要增加圓周率計算過程中迭代的數量，否則時間太短就看不出差異
* 詳閱廖健富提供的[詳盡分析](https://hackpad.com/Hw1-Extcompute_pi-geXUeYjdv1I)，研究 error rate 的計算，以及為何思考我們該留意後者
* 用 [phonebok](/s/S1RVdgza) 提到的 gnuplot 作為 `$ make gencsv` 以外的輸出機制，預期執行 `$ make plot` 後，可透過 gnuplot 產生前述多種實做的效能分析比較圖表
* 可善用 [rayatracing](/s/B1W5AWza) 提到的 OpenMP, software pipelining, 以及 loop unrolling 一類的技巧來加速程式運作
* 詳閱前方 "Wall-clock time vs. CPU time"，思考如何精準計算時間
* 除了研究程式以外，請證明 [Leibniz formula for π](https://en.wikipedia.org/wiki/Leibniz_formula_for_%CF%80)，並且找出其他計算圓周率的方法
* 請詳閱[許元杰的共筆](https://embedded2015.hackpad.com/-Ext1-Week-1-5rm31U3BOmh)
* 將你的觀察、分析，以及各式效能改善過程，並善用 gnuplot 製圖，紀錄於「[作業區](https://hackmd.io/s/Hy2rieDYe)」
## 時間處理與 time 函式使用
### 時間處理
首先閱讀完成[作業解說](https://hackmd.io/s/HkiJpDPtx#)先來作個筆記
通常在計算 **During time** 我們所指的是 **wall-clock time** 或 **cpu time**，這兩個的差異是前者經由 kernel 中的 xtime 來取得時間，後者是計算程序在 CPU 上運行所消耗的時間，根據這兩種我們可以計算出程序在 CPU 以外所耗費的時間，進一步可以分析程式適不適合使用平行處理來加速，想要改善程式可以從計算時間下手。
可利用 real 跟 user time 的比較來思考是否須使用平行處理
- real < user: 表示程式是 CPU bound，使用平行處理有得到好處，效能有提昇。
- real ≒ user: 表示程式是 CPU bound，即使使用平行處理，效能也沒有明顯提昇，常見的原因有可能是其實計算量沒有很大，生成、處理、結束多執行緒的 overhead 吃掉所有平行處理的好處，或是程式相依性太高，不適合拿來作平行處理。
- real > user: 表示程式是 I/O bound，成本大部分為 I/O操作，使得平行處理無法帶來顯著的效能提昇 ( 或沒有提昇)。
### time 函式使用
有個同學整理的不錯 [2016q3 TempoJiJi](https://hackmd.io/s/Hy7tssw6#)
- clock()
- 回傳 clock_t 格式的 cpu time , 如果要以秒為單位要除 CLOCK_PER_SEC
- 每 72 分鐘會回傳相同的值 , 超過 72 分鐘會 wrap around
- 主要以 clock_gettime() 實做，使用 CLOCK_PROCESS_CPUTIME_ID 為 clock
- clock_gettime()
- 這個就有很多種參數可以選擇了
- CLOCK_MONOTONIC_RAW : 從 raw hareware-base time 取得時間
- CLOCK_PROCESS_CPUTIME_ID : Per-process CPU-time clock ( 會計算所有執行緒時間的總和 )
- time()
- time() returns the time as the number of seconds since the Epoch, 1970-01-01 00:00:00 +0000 (UTC).
- gettimeofday()
- 它在取得時間時可以避免日光節約時間或是時區轉換的誤差，不過它只有計算到 microsecond 也就是 10^-6
## 嘗試重現實驗
有一點不知道怎麼開始，先來讀 Makefile 的輸入輸出好了，看到一個有趣的東西 **benchmark_clock_gettime.c**
參數 n 的大小它會計算 25 次各種 compute_pi 的時間，就拿他來改成重現實驗的工具
首先從 Makefile 上面觀察到製作 gencsv 會用到 benchmark_clock_gettime.c
可以使用這個來改成輸出圖片的工具
第一張圖要計算 real time，它使用 clock_gettime 來取得時間，參考 `$ man clock_gettime`，我把參數換成 CLOCK_PROCESS_CPU_TIME_ID
```
./time_test_baseline 6.34s user 0.00s system 99% cpu 6.347 total
./time_test_openmp_2 6.66s user 0.00s system 199% cpu 3.337 total
./time_test_openmp_4 13.18s user 0.00s system 393% cpu 3.348 total
./time_test_avx 2.01s user 0.00s system 99% cpu 2.019 total
./time_test_avxunroll 2.24s user 0.00s system 99% cpu 2.244 total
```
第二三張圖不知道他是用哪種 style，這邊參考[0xff07](https://hackmd.io/s/H1MV8APKg#)同學的筆記使用 `lines + logscale x 10`
計算 real time 使用 clock_gettime(CLOCK_MONOTONIC_RAW, timespec)
計算 cpu time 使用，clock_gettime(CLOCK_PROCESS_CPU_TIME_ID, timespec)
最後是 error rate
這裡看到[同學](https://hackmd.io/s/By-W1PZcl#)的圖都是圓滑的曲線，趕緊來找一下[相關資料](http://gnuplot.sourceforge.net/docs_4.2/node124.html)
使用 `smooth cspline` 來畫出平滑的曲線
### 分析
第一張圖使用 OpenMP 加速，在使用兩個執行緒與四個執行緒時 user time 分別是 real time 的兩倍與四倍，因為在 user time 會計算所有執行緒的時間，所以兩倍與四倍是很合理的。
- cpu time OpenMP 4 一開始時間比別人多，應該是因為在很少的運算量還要分配給多個執行緒，反而會變比較慢
- 為什麼使用 clock_gettime() 結果飄忽不定？
我想應該是因為執行緒會因為其他系統正在執行的程式分配到較少資源，下面實驗一下測試時不切換視窗以及切換視窗看影片的差異
- 無切換視窗
- 有切換視窗
- 為什麼 time() 跟 gettimeofday() 不適合當作 benchmark？
在 man 裡面有寫，它可能因為程式執行中系統時間改變而變得不準
```
NOTES
The time returned by gettimeofday() is affected by discontinuous jumps in the system time (e.g., if the system administrator
manually changes the system time).
```
## Leibniz formula for π
這是他的簡式 參考自 [Wikipedia](https://en.wikipedia.org/wiki/Leibniz_formula_for_%CF%80)
寫成 code 長這樣
```shell
double compute_pi_leibniz(size_t N)
{
double pi = 0.0;
double tmp = -1.0;
for (int i = 0; i < N; i++) {
tmp *= -1.0;
pi += tmp / ( 2.0 * (double)i + 1.0);
}
return pi * 4.0;
}
```
### 效能
### error rate
## Leibniz + OpenMP
code
```shell
double compute_pi_leibniz_openmp(size_t N, int threads){
double pi = 0.0;
double tmp = -1.0;
#pragma omp parallel for num_threads(threads) private(tmp) reduction(+:pi)
for (int i = 0; i < N; i++){
tmp *= -1.0;
pi += tmp / ( 2.0 * (double)i + 1.0);
}
return pi * 4.0;
}
```
第一次這樣行不通，出來一直結果是 0 ，後來做了一些修改
```shell
double compute_pi_leibniz_openmp(size_t N, int threads)
{
double pi = 0.0;
double tmp = -1.0;
#pragma omp parallel for num_threads(threads) private(tmp) reduction(+:pi)
for (int i = 0; i < N; i++){
tmp = (i % 2) ? -1.0 : 1.0;
pi += tmp / ( 2.0 * (double)i + 1.0);
}
return pi * 4.0;
}
```
### 效能
### error rate
## 參考資料
[作業解說](https://hackmd.io/s/HkiJpDPtx#)
[Gnuplot smooth](http://gnuplot.sourceforge.net/docs_4.2/node124.html)
[2016q3 TempoJiJi](https://hackmd.io/s/Hy7tssw6#)
[廖健富](https://hackpad.com/Hw1-Extcompute_pi-geXUeYjdv1I)
[許元杰的共筆](https://embedded2015.hackpad.com/-Ext1-Week-1-5rm31U3BOmh)
[Wikipedia](https://en.wikipedia.org/wiki/Leibniz_formula_for_%CF%80)
Sign in with Wallet
Connect another wallet