# 2017q1 Homework1 (computepi)
contributed by<`jack81306`>
### Review by `kintaxxs`
- 每張圖的x軸與y軸都沒有標題
- commit [4eafa7fd06079329b0b48f6cc5836acf4f2b3112](https://github.com/jack81306/compute-pi/commit/4eafa7fd06079329b0b48f6cc5836acf4f2b3112) 建議分成多次commit，另外簡述一下commit內容
### Review by `PeterTing`
* 可以嘗試測量 error rate 並做分析
* 可以用取信賴區間 95% 來剔除不在信賴範圍內的值
* 可以嘗試使用 gnuplot 來畫圖
###### tags:`jack81306`
## 開發環境
```
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
型號： 60
Model name: Intel(R) Core(TM) i5-4210M CPU @ 2.60GHz
製程： 3
CPU MHz： 2463.049
CPU max MHz: 3200.0000
CPU min MHz: 800.0000
BogoMIPS: 5187.96
虛擬： VT-x
L1d 快取： 32K
L1i 快取： 32K
L2 快取： 256K
L3 快取： 3072K
NUMA node0 CPU(s): 0-3
```
## 事前準備
* 閱讀 simd 相關資料
* [ simd 簡介](http://share.onlinesjtu.com/mod/tab/view.php?id=303)
* [ simd 基本教學](https://www.csie.ntu.edu.tw/~r89004/hive/sse/page_1.html)
* [ simd 指令手冊](https://software.intel.com/sites/landingpage/IntrinsicsGuide/#techs=AVX2)
---
* 進行 simd 測試,使用得程式碼為 1 到 100000 的平方(使用 avx 指令集)
* 測試結果（無使用 avx）
```
support avx2!
0.000306
```
* 測試結果2（使用 avx 指令集加速）
```
support avx2!
0.000182
```
## 首次測試
* <big>原始結果</big>
```
N = 400000000 , pi = 3.141593
3.62user 0.00system 0:03.62elapsed 99%CPU (0avgtext+0avgdata 1808maxresident)k
0inputs+0outputs (0major+83minor)pagefaults 0swaps
time ./time_test_openmp_2
N = 400000000 , pi = 3.141593
3.66user 0.00system 0:01.84elapsed 198%CPU (0avgtext+0avgdata 1764maxresident)k
0inputs+0outputs (0major+85minor)pagefaults 0swaps
time ./time_test_openmp_4
N = 400000000 , pi = 3.141593
6.81user 0.00system 0:01.86elapsed 365%CPU (0avgtext+0avgdata 1888maxresident)k
0inputs+0outputs (0major+90minor)pagefaults 0swaps
time ./time_test_avx
N = 400000000 , pi = 3.141593
1.07user 0.00system 0:01.08elapsed 99%CPU (0avgtext+0avgdata 1716maxresident)k
0inputs+0outputs (0major+82minor)pagefaults 0swaps
time ./time_test_avxunroll
N = 400000000 , pi = 3.141593
1.03user 0.00system 0:01.03elapsed 99%CPU (0avgtext+0avgdata 1700maxresident)k
0inputs+0outputs (0major+83minor)pagefaults 0swaps
```
* <big>原始程式碼的運行結果</big>
* 觀察這個圖可以發現 openmp4 資料似乎是怪怪的,現在沒辦法確定時間提升的原因究竟是因為速度下降或者是資料錯誤.接著再來試著把取樣頻率提高試試看.
* <big>原始程式碼運行結果（取樣頻率提高）</big>
* 觀察這個圖我們可以看到說 openMp 4Thread 的優化似乎不太穩定,運行時間跳動非常的多,接著再來測試大範圍以及高取樣頻率的結果.
* <big>原始程式碼運行結果（範圍以及取樣頻率提高）</big>
* 觀察這個圖可以發現說,除了openmp 4 thread 不太穩定外,openmp 2 thread 也是不太穩定的,況且這兩種優化方式均較 avx 慢,因此再這程式裡,似乎avx是最好的優化方式？
## Leibniz formula
* 下邊的展式是一個無窮級數，被稱為萊布尼茨級數，這個級數收斂到 pi/4。
* 
* 我使用了 Leibniz 公式實作了計算 pi ,並使用了與原程式相同的四種優化方式對 Leibniz 計算 pi 的程式碼進行優化,以下式優化後的結果.
* <big>優化結果</big>
```
N = 400000000 , pi = 3.141593
1.77user 0.00system 0:01.77elapsed 100%CPU (0avgtext+0avgdata 1716maxresident)k
0inputs+0outputs (0major+84minor)pagefaults 0swaps
time ./time_test_openmp_2
N = 400000000 , pi = 3.141593
1.81user 0.00system 0:00.91elapsed 198%CPU (0avgtext+0avgdata 1864maxresident)k
0inputs+0outputs (0major+86minor)pagefaults 0swaps
time ./time_test_openmp_4
N = 400000000 , pi = 3.141593
3.52user 0.00system 0:00.91elapsed 385%CPU (0avgtext+0avgdata 1836maxresident)k
0inputs+0outputs (0major+91minor)pagefaults 0swaps
time ./time_test_avx
N = 400000000 , pi = 3.141593
1.32user 0.00system 0:01.33elapsed 99%CPU (0avgtext+0avgdata 1712maxresident)k
0inputs+0outputs (0major+82minor)pagefaults 0swaps
time ./time_test_avxunroll
N = 400000000 , pi = 3.141593
1.26user 0.00system 0:01.27elapsed 99%CPU (0avgtext+0avgdata 1856maxresident)k
0inputs+0outputs (0major+85minor)pagefaults 0swaps
```
* 從優化結果可以看的出來, baseline 和 openmp 的運行速度變快了,但是 avx 的速度根前一個演算法相比卻是變慢 !!!???
* 造成 avx 優化方式速度下降的可能原因有,過於頻繁的訪問記憶體,或者是常常中斷 avx 的運算,跳去計算一般的數字.
* <big>Leibniz 運行結果</big>
* 這個結果就根前一個演算法一樣, openmp4 的速度最為奇怪,甚至比一般沒經過優化還慢？？
* <big>Leibniz 運行結果（增加採樣頻率）</big>
* 觀察這個圖表可以知道, openmp4 的速度非常不穩定,且不穩定的程度較第一個演算法來的大.
* <big>Leibniz 運行結果（增加採樣頻率及範圍,有開youtube）</big>
* <big>Leibniz 運行結果（增加採樣頻率及範圍,沒開youtube）</big>
* youtube 會嚴重的影響 openmp 阿阿阿阿阿阿阿！！！！
* youtube 對 avx影響較小.
* 再回圈數變大的時候, avx 的速度將會超過 openmp 的速度.
* 最後,我們可以知道說, openmp2 和 openmp4 的差異似乎不大,而 avx 和 avxunroll 雖然也差異不大,但是似乎可以用增加 unroll 的範圍再進行加速.
## 參考資料
[libnize公式](https://zh.wikipedia.org/wiki/%CE%A0%E7%9A%84%E8%8E%B1%E5%B8%83%E5%B0%BC%E8%8C%A8%E5%85%AC%E5%BC%8F)
[intel simd手冊](https://software.intel.com/sites/landingpage/IntrinsicsGuide/#techs=AVX2)
Sign in with Wallet
Connect another wallet