# 2017q1 Homework1 (compute-pi)
contributed by < `ryanwang522` >
---

### Reviewed by `Cayonliow`
* openmp_4 因爲不穩定所以圖會有波動， 可以透過將執行的次數調高然後取平均來消除， 可以看看[我的共筆](https://hackmd.io/s/B1pNFkLql#), 我是使用 gnuplot 制圖
## 開發環境
* OS: ubuntu 16.04 LTS
* L1d cache： 32K
* L1i cache： 32K
* L2 cache： 256K
* L3 cache： 3072K
* Architecture：x86_64
* CPU op-mode(s)： 32-bit, 64-bit
* Byte Order： Little Endian
* CPU(s)： 4
* Model name: Intel(R) Core(TM) i5-4200H CPU @ 2.80GHz

## 原始版本
### 進行實驗
* 先執行原本的程式碼，並且熟悉一下 LibreOffice 的操作。
* __loop = 25__
* 發現 openmp 在四個執行序的狀況下，相較於其他方法有比較不尋常的波動，不過覺得取樣空間分得太開，先將 loop 次數提高以及增加取樣次數看看會有什麼結果。

* __loop = 50，取樣間隔調整為 2500__
* 仍然有些波動影響直觀的比較，在增加取樣以及平均的次數。
* __loop = 250, 取樣間隔調整為 1000__
* 避免圖形難於觀察，取消點的顯示。
* 由 loop = 250，取樣間隔 1000 的圖不難觀察出執行時間的差異
* AVX > Openmp > Baseline
* Openmp 在 4 threads 的情況下比較不穩定，認為是 omp 在進行 Reduction 時，每個 thread 的執行速度差異互相等待，所造成的 overhead。

### Error Rate
* loop = 250 , N = 100 : 5000 : 25000
* loop = 250 , N = 100 : 1000 : 25000
* 可以看出除了 AVX unroll 的版本在 N 不夠大時會有較大的誤差以及不太穩定，其他方法的誤差隨著 N 的遞增都很快地趨近於 0。
* 目前對於 avx unroll 為何會波動較大還想不太到解釋。

## Leibniz Method
* 參考 [Leibniz formula for π](https://en.wikipedia.org/wiki/Leibniz_formula_for_%CF%80)
* 
* 實作

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

* 這裡再實作一個 Openmp 的版本來進行比較
* 因為 Leibniz 需要正負相間的運算，所以利用 `schedule(static, 1)` 去明確指定每個 thread 所要負責的迴圈部份。
* 計時方法依然使用 `clock_gettime()`。

double compute_pi_Leibniz_omp(size_t N, int threads)
{
    double pi = 0.0;
    #pragma omp parallel for num_threads(threads) \
        reduction(+:pi) schedule(static, 1)
    for (size_t i = 0; i < N; i++) {
        if (omp_get_thread_num() % 2 == 0)
            pi += 1.0 / (2.0 * (double)i + 1.0);
        else
            pi += -1.0 / (2.0 * (double)i + 1.0);
    }   
    return (4 * pi);
}

* Leibniz 的原始版本好像就比黎曼和快了不少！
* Error Rate 比較，依然只有 AVX Unroll 較不穩定。
* 補上 gnuplot
* 寫 `runtime.gp` 一直遇到 `x range is invalid` 的錯誤訊息，後來發現是 gnuplot 預設用空白來切分數據。
* 加上 `set datafile separator ","` 就可以正常畫圖了！
* 這裡可以看到 OpenMP 在某些 N 值會有執行時間莫名增加的狀況，而其他方法都還算穩定，可以推斷是 thread 之間運作的 Overhead。

## Monte Carlo Method

## Reference
[GNUPLOT 讀取逗號分隔的數據文件](http://fanli7.net/a/bianchengyuyan/C__/20130118/293215.html)
[Leibniz formula for π - wikipedia](https://en.wikipedia.org/wiki/Leibniz_formula_for_%CF%80)