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

### Reviewed by <`rayleigh0407`>
* 建議可以簡單說明一下關於 AVX 的背景知識及語法 , 或是一些連結
* 可以試試看用 LaTeX 語法表示數學式 , 可參考 [LaTeX](http://meta.math.stackexchange.com/questions/5020/mathjax-basic-tutorial-and-quick-reference) 或是 [我的筆記](https://hackmd.io/MYEwDAHAZmCcBMBaApgdkogLMGiCGAjKIgGwDMBm8IyJeyZArEA=?both#leibniz-formula-proof)
---

## 開發環境

illusion030@illusion030-X550LD:~/Desktop/2017sysprog/compute-pi$ lscpu
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
型號：              69
Model name:            Intel(R) Core(TM) i5-4200U CPU @ 1.60GHz
製程：              1
CPU MHz：             1479.754
CPU max MHz:           2600.0000
CPU min MHz:           800.0000
BogoMIPS:              4588.93
虛擬：              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)

$ git clone https://github.com/illusion030/compute-pi
$ cd compute-pi

* 執行看看

$ make check

* 得到五組結果分別為 baseline、使用 2 個 threads 的 OpenMP、使用 4 個 threads 的 OpenMP、使用 AVX、使用 AVX 配合 Unroll looping

time ./time_test_baseline
N = 400000000 , pi = 3.141593
4.47user 0.00system 0:04.47elapsed 99%CPU (0avgtext+0avgdata 1812maxresident)k
0inputs+0outputs (0major+84minor)pagefaults 0swaps

time ./time_test_openmp_2
N = 400000000 , pi = 3.141593
4.91user 0.00system 0:02.46elapsed 199%CPU (0avgtext+0avgdata 1796maxresident)k
0inputs+0outputs (0major+85minor)pagefaults 0swaps

time ./time_test_openmp_4
N = 400000000 , pi = 3.141593
9.35user 0.00system 0:02.46elapsed 380%CPU (0avgtext+0avgdata 1812maxresident)k
0inputs+0outputs (0major+89minor)pagefaults 0swaps

time ./time_test_avx
N = 400000000 , pi = 3.141593
1.27user 0.00system 0:01.27elapsed 99%CPU (0avgtext+0avgdata 1792maxresident)k
0inputs+0outputs (0major+83minor)pagefaults 0swaps

time ./time_test_avxunroll
N = 400000000 , pi = 3.141593
1.22user 0.00system 0:01.23elapsed 99%CPU (0avgtext+0avgdata 1704maxresident)k
0inputs+0outputs (0major+83minor)pagefaults 0swaps

* 把比較圖畫出來看看

Makefile 裡統計資料的程式碼

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

for 迴圈裡是指從 100 開始，每次 +5000，加到 25000，所以會畫 100、5100、10100、15100、20100 總共五次
* 用 libre office 畫出來
* 用 gnuplot 畫出來
發現 openmp的數值不太穩定，研究了一下 benchmark_clock_gettime.c ，他計算時間的方式是把 i 傳入當作 N 值，並且計算跑 loop 次的時間
* 試著把 loop 變多看看(loop=500)
OpemMP 用 4 個 threads 跑的值還是不穩定
* 再增加 loop(loop=5000)
跑出來的值變得比較穩定了
* 試著增加測資看看(N=100:2500:50000)
效率：avx+unroll > avx > openmp(2threads) > openmp(4threads) > baseline， openmp(4threads) 和 openmp(2threads) 較不穩定，有時後 openmp(4threads) 的效率會比 baseline 差
>請修改 X label 排版，參考[美圖欣賞第三張](https://hackmd.io/s/Skwp-alOg#美圖欣賞)
---

## Error Rate

* 參考廖健富提供的[詳盡分析](https://hackpad.com/Hw1-Extcompute_pi-geXUeYjdv1I#:h=Compute-Pi)

* error rate = | Approximate Value − Exact Value | / |Exact Value|
* 用 N=100:5000:50000 畫出 perfomance 跟 error rate 的比較
發現 anx+unroll 的 error rate 會浮動
* 再看細一點
用 baseline 的 error rate 小於 0.0001

---

## Leibniz formula for π
* 公式和證明在 [Leibniz formula for π](https://en.wikipedia.org/wiki/Leibniz_formula_for_%CF%80) 就有了
* 公式
* 證明
* 後項的積分為 0
* 最後得出
* 寫成程式

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

* 跑跑看

time ./time_test_leibniz
N = 400000000 , pi = 3.141593
2.18user 0.00system 0:02.18elapsed 99%CPU (0avgtext+0avgdata 1716maxresident)k
0inputs+0outputs (0major+82minor)pagefaults 0swaps

時間比 baseline 還快
* 畫出比較圖
時間還比 baseline 用 openmp 還快
error rate 跟除了 anx+unroll 一樣
* 用 AVX 加速

double compute_pi_leibniz_avx(size_t N)
{
    double pi = 0.0;
    register __m256d ymm0, ymm1, ymm2, ymm3, ymm4, ymm5;
    ymm0 = _mm256_set1_pd(2.0);
    ymm1 = _mm256_set1_pd(1.0);
    ymm2 = _mm256_set_pd(1.0, -1.0, 1.0, -1.0);
    ymm4 = _mm256_setzero_pd();
    ymm5 = _mm256_set_pd(0.0, 1.0, 2.0, 3.0);

    for(size_t i = 0; i <= N - 4; i += 4) {
        ymm3 = _mm256_set1_pd(i);
        ymm3 = _mm256_add_pd(ymm3, ymm5);
        ymm3 = _mm256_mul_pd(ymm3, ymm0);
        ymm3 = _mm256_add_pd(ymm3, ymm1);
        ymm3 = _mm256_div_pd(ymm2, ymm3);
        ymm4 = _mm256_add_pd(ymm4, ymm3);
    }   

    double tmp[4] __attribute__((aligned(32)));
    _mm256_store_pd(tmp, ymm4);
    pi += tmp[0] + tmp[1] + tmp[2] + tmp[3];

    return pi * 4.0;
}           

* 跑跑看

time ./time_test_leibniz_avx
N = 400000000 , pi = 3.141593
1.22user 0.00system 0:01.22elapsed 100%CPU (0avgtext+0avgdata 1720maxresident)k
0inputs+0outputs (0major+82minor)pagefaults 0swaps

速度增快了
* 畫出比較圖
leibniz+avx 的時間跟 baseline 用 avx+unroll 幾乎一樣
error rate 也是跟其他五個一樣