# 2017q1 Homework1 (compute-pi)
contributed by < `etc276` >
###### tags: `嵌入式`

### Reviewed by `yangyang95`
- 不是超連結的文字 ( eg. [link text](https:// "title") )，不要使用超連結符號，可用 **粗體**
- 第一張 error rate 的圖形不清楚，且範圍需修改
- binary file 不要一起送上 github ，可在 .gitignore 中加入 *.png *.txt 來忽略特定檔案格式
- 程式碼還可以在稍微精簡一點點，並注意 coding style 小括號左方要留有空白

double compute_pi_leibniz (size_t N)
{
    double pi = 0.0;
    int tmp = 1;
    for (size_t i = 0; i < N; i++) {
        pi += tmp / (2.0 * (double)i + 1.0);
        tmp *= (-1);
    }
    return 4 * pi;
}

## 開發環境
- Ubuntu 16.10 (64bit)

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:                 61
Model name:            Intel(R) Core(TM) i7-5500U CPU @ 2.40GHz
Stepping:              4
CPU MHz:               2400.878
CPU max MHz:           3000.0000
CPU min MHz:           500.0000
BogoMIPS:              4788.90
Virtualization:        VT-x
L1d cache:             32K
L1i cache:             32K
L2 cache:              256K
L3 cache:              4096K
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)」

## 開發紀錄

### 重現實驗
* ```$ make check``` 後查看各版本時間

$ time ./time_test_baseline
N = 400000000 , pi = 3.141593
real    0m1.388s
user    0m1.376s
sys     0m0.004s

$ time ./time_test_openmp_2
N = 400000000 , pi = 3.141593
real    0m1.324s
user    0m2.632s
sys     0m0.000s

$ time ./time_test_openmp_4
N = 400000000 , pi = 3.141593
real    0m0.770s
user    0m2.768s
sys     0m0.000s

$ time ./time_test_avx
N = 400000000 , pi = 3.141593
real    0m0.922s
user    0m0.920s
sys     0m0.000s

$ time ./time_test_avxunroll
N = 400000000 , pi = 3.141593
real    0m0.721s
user    0m0.712s
sys     0m0.004s

* 分析 real, user, sys 的不同
1. real time :
也就是 Wall-clock time，當然若有其他程式同時在執行，必定會影響到。
2. user time : 表示程式在 user mode 佔用所有的 CPU time 總和。
3. sys time : 表示程式在 kernel mode 佔用所有的 CPU time 總和 ( 直接或間接的系統呼叫 )。

### 增加迭代
* 查看 Makefile 發現以下程式碼

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

* 而這段程式碼可理解為

for (i=100; i<=25000; i+=5000)
    compute_pi(i);

* 增加迭代前的圖 (i<=25000)
* 增加迭代後的圖 (i<=250000)
* 可發現 OpenMP (4 Thread)的時間漂浮有點大，晚點再來想原因

### 研究 error rate

* 查看 Makefile 發現用來產生圖檔的資料 csv 檔是由 benchmark_clock_gettime 輸出，因此修改此 .c 檔，再輸出 error。後改為寫一個 out.pg，並在 Makefile 新增 `plot :`以產生兩種圖檔。

* 產生圖檔的過程遇到一個困難是，csv 檔的資料分隔是用逗號(，)所以一開始想用 ```"%lf,%lf,%lf,%lf,%lf,%lf"``` 的方式撰寫 out.pg，後來才發現可以使用 ```set datafile separator "," ```

* 用 gnuplot 畫出來的 error rate


* 在 out.pg 加上 ```set logscale xy``` ，看的細一點


### Leibniz formula for π

參考 [shelly4132的共筆](https://hackmd.io/s/HJrLU0dp)

考慮以下分解：

對兩邊從0到1去做積分

當時，除積分項以外的項收斂到萊布尼茨級數。同時，積分項收斂到0：


所以這便證明了萊布尼茨公式。

double compute_pi_leibniz(size_t N)
{
    double pi = 0.0;
    int tmp = 1;
    for (size_t i =0; i < N; i++) {
        pi += tmp / (2.0 * (double)i + 1.0);
        tmp *= (-1);
    }
    pi *= 4; 
    return pi;
}

* 補圖


其他計算圓周率的方式如 蒙地卡羅、尤拉等等 (待補實作code)