# 2016q3 Homework 3 ( compute-pi )
contributed by <`ierosodin`>
## 開發環境
作業系統 : CentOS 7
`$ lscpu`
Architecture: x86_64
CPU op-mode(s): 32-bit, 64-bit
Byte Order: Little Endian
CPU(s): 12
On-line CPU(s) list: 0-11
Thread(s) per core: 2
Core(s) per socket: 6
Socket(s): 1
NUMA node(s): 1
Vendor ID: GenuineIntel
CPU family: 6
Model: 45
Model name: Genuine Intel(R) CPU @ 3.30GHz
Stepping: 5
CPU MHz: 1277.976
BogoMIPS: 6600.19
Virtualization: VT-x
L1d cache: 32K
L1i cache: 32K
L2 cache: 256K
L3 cache: 15360K
NUMA node0 CPU(s): 0-11
## 軟體安裝
```
$ git clone https://github.com/sysprog21/compute-pi
$ cd compute-pi
$ make check
$ make gencsv
```
## 重現實驗
`$ time ./time_test_baseline`
```
N = 400000000 , pi = 3.141593
real 0m6.979s
user 0m6.978s
sys 0m0.001s
```
`$ time ./time_test_openmp_2`
```
N = 400000000 , pi = 3.141593
real 0m3.568s
user 0m7.131s
sys 0m0.002s
```
`$ time ./time_test_openmp_4`
```
N = 400000000 , pi = 3.141593
real 0m1.886s
user 0m7.536s
sys 0m0.001s
```
`$ time ./time_test_avx`
```
N = 400000000 , pi = 3.141593
real 0m3.340s
user 0m3.331s
sys 0m0.003s
```
`$ time ./time_test_avxunroll`
```
N = 400000000 , pi = 3.141593
real 0m2.030s
user 0m2.028s
sys 0m0.002s
```
## 折線圖
嘗試利用result_clock_gettime.csv畫折線圖, 卻發現25000次所花費的時間有點長, 進入benckmark_clock_gettime.c才發現, 時間是25次的, 為了得到一次的時間, 先將loop次數改成1.
```
set title 'compute-pi'
set xlabel "N"
set ylabel "time(sec)"
set xrange [100:25000]
set terminal png
set output 'output_plot.png'
plot "result_clock_gettime.csv" using 1:2 w lp pt 7 lc 1 title 'baseline', "result_clock_gettime.csv" using 1:3 w lp pt 7 lc 2 title 'openmp_2', "result_clock_gettime.csv" using 1:4 w lp pt 7 lc 3 title 'openmp_4', "result_clock_gettime.csv" using 1:5 w lp pt 7 lc 4 title 'avx', "result_clock_gettime.csv" using 1:6 w lp pt 7 lc 5 title 'avxunroll'
```
※ 寫成`gnuplot.gp` 執行`$ gnuplot gnuplot.gp`
發現data似乎在飄動, 嘗試增加data的資料數量:
修該Makefile中的
```
for i in `seq 100 100 25000`; do \
printf "%d " $$i;\
./benchmark_clock_gettime $$i; \
done > result_clock_gettime.csv
```
詳細用法 : `$ man seq`
可以觀察出時間與分割的大小呈線性關係, 但折線圖仍不完美, 有許多不適用的data, 嘗試利用95%信賴區間重寫程式.
## 95%信賴區間
重寫benchmark_clock_gettime.c中的程式碼, 取樣100次後找出95%的信賴區間, 再刪除不適當的資料後取平均.
結果似乎沒有很明顯的差異, 將取樣次數拉到10000次:
10000次:
不過10000次需要消耗相當多的時間, 於是嘗試平行化這部份
### 平行化程式
```
#pragma omp parallel default (shared) private(j) num_threads(12) reduction(+:suma, sumb)
#pragma omp for schedule(static)
```
#### 平行化結果
(前面數字代表第i個迴圈)
(begin為迴圈開始時間, last為結束時間, data為時間差)
未平行化的前幾筆結果
```
0 begin:23899.487297
0 last:23899.513484
0 data:0.026187
1 begin:23899.513515
1 last:23899.533334
1 data:0.019819
2 begin:23899.533366
2 last:23899.553033
2 data:0.019668
3 begin:23899.553059
3 last:23899.572796
3 data:0.019737
4 begin:23899.572828
4 last:23899.592506
4 data:0.019678
```
平行化後前幾筆結果
```
92 begin:23956.224151
0 begin:23956.224150
44 begin:23956.224157
52 begin:23956.224152
9 begin:23956.224151
68 begin:23956.224155
27 begin:23956.224154
36 begin:23956.224152
84 begin:23956.224148
60 begin:23956.224149
18 begin:23956.224153
76 begin:23956.224149
0 last:23956.256244
0 data:0.032094
1 begin:23956.256301
18 last:23956.260785
18 data:0.036632
```
解讀:整體速度變快了, 但資料的正確性有待商榷.
#### 提出的疑惑
發現平行化後, 雖然整體執行速度很快, 但單個迴圈的時間變長了(data值變大了)
如平行化後第i = 0的迴圈, data為0.032094
然而未平行化前的迴圈時間僅0.026187
##### 猜想一:誤差小, 可能是合理範圍
但經過100次迴圈後得到的結果, 未平行化得到的平均data值為0.019701, 而平行化後的平均值為0.030313, 差距似乎無法忽略
##### 猜想二:是否在平行化的過程, 資料有相依的問題
每個迴圈的時間應該都是獨立的, 不會有資料相依的問題.
##### 猜想三:檢查assembly
還在解讀Q
## OPENMP threads = 12
嘗試將效能開到硬體的最大
發現openmp_12比avx_unroll還要快, 但嘗試在avx_unroll中的for迴圈加入omp, 卻沒有得到理想的結果
## OPENMP Threads數量對效能影響
當Thread數 = Thread(s) per Core * Core(s) per Socket時, 效能最好
(N = 400000000)
Threads 12 vs 16 (N = 100~25000)
## ERROR
為了檢視五個function所得出的結果是否正確, 多新增了error.c, 比對實驗值與標準值的差異
>>參考[王紹華的共筆](https://hackmd.io/KYQwjARgZgTArAZgLQgJwAYpICyoMYAmSAHJiEggGzzqQEIDsqYQA===#)
發現其中四條曲線重疊, 唯獨avxunroll會不斷的飄動(擺動週期為N = 16）, 原因為avxunroll中每一次for迴圈為16筆資料, 然而實驗的N並非16的倍數, 因此會產生數值錯誤的問題(餘數的部份不會算到）.
例如N = 100, 在avxunroll中就只會算x = 0 ~ 95
### 修正:
分別在avx與avxunroll之中, 增加了檢查N並非4的倍數與16的倍數, 並加以修正, 得到以下的結果圖.
## 參考資料
[王紹華的共筆](https://hackmd.io/KYQwjARgZgTArAZgLQgJwAYpICyoMYAmSAHJiEggGzzqQEIDsqYQA===#)
[信賴區間與信心水準的解讀](http://web.cc.ntnu.edu.tw/~494402345/CI/CI.pdf)
Sign in with Wallet
Connect another wallet