# 2017q1 Homework1 (compute-pi)
contributed by <`ryanpatiency`>
>請在作業區補上 github 連結 [name=課程助教][color=red]

### Reviewed by `kintaxxs`
- 可以多實作其他優化的方法，並繪圖比較各方法的差異。

## 目標

作業要求 [B03: compute-pi](https://hackmd.io/CwDgjArAJgZhCcBaEBmEAmRwBGZPYDYBjFRCMAU3mygEMKB2AgioA===?both)
* 在 GitHub 上 fork [compute-pi](https://github.com/sysprog21/compute-pi)，嘗試重現實驗，包含分析輸出
* 詳閱廖健富的[分析](https://hackpad.com/Hw1-Extcompute_pi-geXUeYjdv1I)，研究 error rate 的計算，以及思考我們為何該留意後者
* 用 gnuplot 作為 `$ make gencsv` 以外的輸出機制，預期執行 `$ make plot` 後，可透過 gnuplot 產生前述多種實做的效能分析比較圖表
* 善用 OpenMP, software pipelining, 以及 loop unrolling 一類的技巧來加速程式運作
* 思考如何精準計算時間
* 證明 [Leibniz formula for π](https://en.wikipedia.org/wiki/Leibniz_formula_for_%CF%80)，並且找出其他計算圓周率的方法
## 觀察
實驗目的：比較`computepi.c`中的四個程式的準確值和執行時間。
但是因為知道浮點數是二進制，大部分的小數點都沒有辦法表示。以下實驗可証明：

int main(){
    long double ldpi = 3.1415 9265 3589 7932 384626;
    double dpi       = 3.1415 9265 3589 7932 384626;
}

gdb 的結果：

1: ldpi = 3.1415 9265 3589 7931 159979634685441852
2: dpi  = 3.1415 9265 3589 7931

發現 long double 和 double 的精確度到了小數點下十二位後都產生誤差，且誤差值幾乎一樣。

## 實驗過程
### 實作一：
程式碼：簡單的積分

static long num_steps = 1000000000;
double sum = 0, x, pi, dx = 1 / (double)num_steps;

for (int k = 0; k < num_steps; k++) {
    x = (k+0.5) * dx;
    sum = sum + 4 / (x * x + 1);
}
pi = sum * dx;

結果

$time ./pi
pi is 3.14159265358997075

real	0m5.285s
user	0m5.280s
sys	0m0.000s

>time 指令的單位是 ms
>real 的時間是指 wall-clock, 也就是系統真正走過的時間。
>user 的時間是指在 user space 中 cpu 中所有 threads 的時間加總

程式執行時間約五秒多，而且 user time 等於 real time ，代表沒有好好利用 multi threads
### 實作二 - openMP：
使用 multi threads
`$ export OMP_NUM_THREADS=4`

程式碼

double sum = 0, pi, dx = 1 / (double)num_steps;

#pragma omp parallel
{
    double x, partial_sum = 0;
    int num_threads = omp_get_num_threads();
    int threads_id = omp_get_thread_num();
    int lower_bound = num_steps * threads_id / num_threads;
    int upper_bound = num_steps * (threads_id + 1) / num_threads;
    for (int k = lower_bound; k < upper_bound; k++) {
        x = (k + 0.5) * dx;
        partial_sum += 4 / (x * x + 1);
    }

    sum += partial_sum;
}
pi = sum * dx;

結果

$time ./pi
pi is 3.14159265358982109

real	0m3.016s
user	0m11.492s
sys	0m0.012s

程式執行時間約三秒，比之前快了 1.5 倍，而且 user time 約等於 real time 的四倍 ，代表使用了四個 threads 加速。
### gnuplot

## 參考資料
* [Wikipedia](https://en.wikipedia.org/wiki/Leibniz_formula_for_%CF%80)
* [共筆](https://hackmd.io/s/H1TUAblqg#)
* [openmp tutorial](https://computing.llnl.gov/tutorials/openMP/)
* [parallel programming](https://computing.llnl.gov/tutorials/parallel_comp/)
* [openmp youtube channel](https://www.youtube.com/user/OpenMPARB)