# 2016q3 Homework1(Compute-pi)
## 作業要求
* 在 GitHub 上 fork [compute-pi](https://github.com/sysprog21/compute-pi)，嘗試重現實驗，包含分析輸出
* 注意: 要增加圓周率計算過程中迭代的數量，否則時間太短就看不出差異
* 詳閱廖健富提供的[詳盡分析](https://hackpad.com/Hw1-Extcompute_pi-geXUeYjdv1I)，研究 error rate 的計算，以及為何思考我們該留意後者
* 用 [phonebok](/s/S1RVdgza) 提到的 gnuplot 作為 `$ make gencsv` 以外的輸出機制，預期執行 `$ make plot` 後，可透過 gnuplot 產生前述多種實做的效能分析比較圖表
* 可善用 [rayatracing](/s/B1W5AWza) 提到的 OpenMP, software pipelining, 以及 loop unrolling 一類的技巧來加速程式運作
* 詳閱前方 "Wall-clock time vs. CPU time"，思考如何精準計算時間
* 除了研究程式以外，請證明 [Leibniz formula for π](https://en.wikipedia.org/wiki/Leibniz_formula_for_%CF%80)，並且找出其他計算圓周率的方法
* 請詳閱[許元杰的共筆](https://embedded2015.hackpad.com/-Ext1-Week-1-5rm31U3BOmh)
* 將你的觀察、分析，以及各式效能改善過程，並善用 gnuplot 製圖，紀錄於「[作業區](https://hackmd.io/s/H1B7-hGp)」
## 開發環境
* Ubuntu 14.04
* CPU model:
* model: 78
* name: Intel(R) Core(TM) m3-6Y30 CPU @ 0.90GHz
* cpu MHz : 499.570
* Cache
* L1d 快取： 32K
* L1i 快取： 32K
* L2 快取： 256K
* L3 快取： 4096K
指令：
$ uname -a
$ lscpu
$ cat /proc/cpuinfo
## 重現實驗
先照著跑跑看～
```shell
$ make check
time ./time_test_baseline
N = 400000000 , pi = 3.141593
2.23user 0.00system 0:02.23elapsed 99%CPU (0avgtext+0avgdata 1760maxresident)k
0inputs+0outputs (0major+86minor)pagefaults 0swaps
time ./time_test_openmp_2
N = 400000000 , pi = 3.141593
2.88user 0.00system 0:01.44elapsed 199%CPU (0avgtext+0avgdata 1768maxresident)k
0inputs+0outputs (0major+88minor)pagefaults 0swaps
time ./time_test_openmp_4
N = 400000000 , pi = 3.141593
5.44user 0.00system 0:01.41elapsed 385%CPU (0avgtext+0avgdata 1740maxresident)k
0inputs+0outputs (0major+91minor)pagefaults 0swaps
time ./time_test_avx
N = 400000000 , pi = 3.141593
0.98user 0.00system 0:00.98elapsed 100%CPU (0avgtext+0avgdata 1684maxresident)k
0inputs+0outputs (0major+84minor)pagefaults 0swaps
time ./time_test_avxunroll
N = 400000000 , pi = 3.141593
0.72user 0.00system 0:00.73elapsed 99%CPU (0avgtext+0avgdata 1764maxresident)k
0inputs+0outputs (0major+84minor)pagefaults 0swaps
```
一執行就有computepi五種版本花的時間。time顯示了三種時間, 分別是user time, system time和elapsed time。這邊花了一些時間搞懂各別的意義。
我的理解如下：
* User time: 程式在User mode的CPU time總和。程式被blokcked的時間(比如I/O)和其他程式的時間不會被算進去。
* System time: 程式在 kernel mode 的 CPU time 總和 ( 直接或間接的系統呼叫 )。
* Elapsed time: 這裡的elapsed time就是在[Wall-clock time vs. CPU time](https://hackmd.io/s/rJARexQT#wall-clock-time-vs-cpu-time)裡面介紹的real time或是 Wall-clock time。Elapsed意思是開始到結束，在這裡就是呼叫程式到結束的時間。包含程式被bloked, 需要等待I/O，其他程式或是作業系統的時間。
所以user+system的時間就是整個程式的CPU Time。
還有multithread程式在多核電腦上, user time和system time會是在不同CPU上的時間總和，會和child process的時間相加。
回頭看程式的輸出，在openmp2的 user+system是elpapsed time 的兩倍, openmp4的user+system是elapsed time的四倍左右, 可以看出多個執行序的效果。
參考[Wall-clock time vs. CPU time](https://hackmd.io/s/rJARexQT#wall-clock-time-vs-cpu-time) [TempoJiJi同學筆記](https://hackmd.io/s/Hy7tssw6) 和 [What do 'real', 'user' and 'sys' mean in the output of time(1)](http://stackoverflow.com/questions/556405/what-do-real-user-and-sys-mean-in-the-output-of-time1)
再來看benchmark,
```shell
$ make gencsv
```
用gnuplot製圖：
這裡卡了很久, 撰寫注意事項有：
1. 參考[Petermouse同學](https://hackmd.io/MwJgrAnBDGYIYFoAMB2ApgEwQFgBy+ARmACNk5cTwMNc8Ug=?both#觀察) 因為資料是以逗號分隔, 所以需要加上
set datafile separator ","
2. \後面不要有空隔
gnuplot:
```clike
reset
set xlabel 'N'
set ylabel 'time(rec)'
set datafile separator ","
set title 'performance comparison'
set term png enhanced font 'Verdana,10'
set output 'runtime.png'
plot "result_clock_gettime.csv" u 1:2 title 'baseline' w l,\
"result_clock_gettime.csv" u 1:3 t 'openmp2' w l,\
"result_clock_gettime.csv" u 1:4 t 'openmp4' w l,\
"result_clock_gettime.csv" u 1:5 t 'avx' w l,\
"result_clock_gettime.csv" u 1:6 t 'avxunroll' w l,\
```
跑出來的圖：
參考[TempoJiJi](https://hackmd.io/s/Hy7tssw6)理解Makefile
```clike
gencsv: default
for i in `seq 100 5000 25000`; do \
printf "%d," $$i;\
./benchmark_clock_gettime $$i; \
done > result_clock_gettime.csv
```
起始值為100, 之後每5000取一點, 取值要小於25000
在Makefile中加上
```clike
plot : gencsv
gnuplot runtime.gp
```
方便繪製圖。
再把間隔調小一點,也把範圍調大：
100 2500 400000 >> 每5000點取20個點
可以發現在這樣的設定下openmp4的變動很大, 我觀察某些同學的數據也有類似的情形。我的processor是physical 2 core logical 4 cores, 不知道是不是跟當中的運算有關係, 之前跑出來的CPU使用量openmp4也是最低的。
### 時間函數分析
在繼續下去以前，因為一度被數據弄的頭昏眼花～.~，想先釐清這個實驗的目的。分析改善computepi程式, 而因為要分析所以我們必須取得正確的資訊,包含分析我們時間的函式和信賴區間。
先從源頭時間的取得開始,因為這會從一開始影響整個實驗。老師介紹作業的頁面：
寫時間量測程式前，先評估情況，問問自己幾個問題：
1. 使用什麼 clock 測量？(Real, User, System, Wall-clock....?)
2. clock 的精確度？(s, ms, µs, or faster ?)
3. 需要多久時間你的 clock 會 wrap around？有什麼方法可以避免或處理？
4. clock 是不是 monotonic (單調遞增)？還是會隨著系統時間改變 (NTP, time zone, daylight savings time, by the user...?)
5. 使用的函式使否已經過時、或不是標準函式庫？
下去搜尋後發現的資料：[Measure time in Linux - time vs clock vs getrusage vs clock_gettime vs gettimeofday vs timespec_get?](http://stackoverflow.com/questions/12392278/measure-time-in-linux-time-vs-clock-vs-getrusage-vs-clock-gettime-vs-gettimeof)
我的理解如下：
1. time()的時間精度是1秒,這次的實驗的數據多半在毫秒左右所以不適合。
2. getrusage()：在linux x86是一個system call
3. clock()在資料裡面提到約2^32 ticks的時候會wrap around(存取周遭)
3. clock_gettime(CLOCK_MONOTONIC_RAW,)可以以monotonic的方式執行, 不會wrap around。不過我在[What is the difference between CLOCK_MONOTONIC & CLOCK_MONOTONIC_RAW?](http://stackoverflow.com/questions/14270300/what-is-the-difference-between-clock-monotonic-clock-monotonic-raw)看到有人提及因為clock_gettime是提供一個offset來使他不會被改變, 當clock發生變化的時候他可能沒辦法調整好,頻率產生變化。
4. getrusage()：這個是寫這篇評論的人相當推薦的函式,分別印出user time和system time不過精度只有到ms on linux。
我在想clock_gettime雖然有monotonic而且精度比較高(nano),可是他包含了程式以外的時間; getrusage 則是比較精準的提供我們實驗所需的user time和system time相加, 不確定哪一個較好。在這裡先用getrusage試試看。
先修正原本的圖, 看到[王紹華](https://hackmd.io/s/BJdYsOPa)同學的筆記才發現在benchmark_clock_gettime.c中的clock_gettime包含了整個loop。
```clike=
int i, loop = 1;
// Baseline
for(i = 0; i < loop; i++) {
clock_gettime(CLOCK_ID, &start);
compute_pi_baseline(N);
clock_gettime(CLOCK_ID, &end);
}
printf("%lf,", (double) (end.tv_sec - start.tv_sec) +
(end.tv_nsec - start.tv_nsec)/ONE_SEC);
```
現在還不是很懂為什麼要把他寫進去for loop中, 先把loop設為1。順便把range再調大, 100 5000 2000000
再執行一次：
瘋狂的data
來看看getrusage, 從我們剛執行的make check我發現只有user time(沒解讀錯的話),所以這裡直接用ru_utime。
使用時要include:
#include <sys/time.h>
#include <sys/resource.h>
程式描述：
int getrusage(int who, struct rusage *usage);
這裡int who使用RUSAGE_SELF, 被呼叫程式使用資源總和, 包含threads。
寫的程式如下：
```clike=
struct rusage start;
struct rusage end;
struct timeval sutime,eutime;
if (argc < 2) return -1;
int N = atoi(argv[1]);
int i, loop = 1;
// Baseline
for(i = 0; i < loop; i++) {
getrusage(RUSAGE_SELF, &start);
compute_pi_baseline(N);
getrusage(RUSAGE_SELF, &end);
}
sutime = start.ru_utime;
eutime = end.ru_utime;
printf("%lf,", (double) (eutime.tv_sec - sutime.tv_sec) +
(eutime.tv_usec - sutime.tv_usec)/ONE_SEC);
```
跑出了悲劇的結果：
orz
不是很懂為什麼...
### 信賴區間
先回去做clock_gettime的信賴區間
### 補充筆記
突然發現自己對於thread觀念還是很不了解, 我的電腦只有四核, 用openmp4可以跑出四個thread的結果,可是在pthread或是raytracing把thread number設很高的話, 那概念似乎就不太一樣。
我好像把core還有processor的觀念搞混了,目前理解是：
* 我的電腦是一個processor with multi-cores
* Core count是physical cores數
* hyper-threading可以讓logical提高
參考：[Difference Between Cores and Processors](http://superuser.com/questions/168809/difference-between-cores-and-processors?rq=1)[What are threads, and what do they do in the processor?](http://superuser.com/questions/329904/what-are-threads-and-what-do-they-do-in-the-processor)
## 參考資料
* [What are the Meanings of Intel Processor Suffixes?](http://www.howtogeek.com/223020/what-are-the-meanings-of-intel-processor-suffixes/)
* https://magiclen.org/linux-view-cpu/
###### tags: `Ruby` `2016_Autumn` `HW1` ` computepi`
Sign in with Wallet
Connect another wallet