2016q3 Homework1 (compute-pi)
===
>標題打錯了
>改完把我刪掉 ^^
>[name=洪正皇][color=#ed76e9]

contributed by <`PerterTing`>
### Reviewed by `changyuanhua`
* 這裡有 [commit 錯誤](https://github.com/PeterTing/compute-pi/commit/ced7d67fed214b5e0326939975d97f15c60bf5b0) 標題字數最多 50。因為標題字數超過 50 在 github 上會被隱藏到 … 裡面，需要額外點開才能完整知道這個 commit 在做什麼。並且超過 50 字可能就不是一個精簡的標題
* 這裡有 [commit 錯誤](f1a339c3de4212e65039d80874a23fa5b8900277) 標題結尾不要句點
* ns 應該是奈秒吧？！
* 可以在嘗試其他數學運算，像是 Nilakantha
* 可以運用[廖健富學長的筆記](https://hackpad.com/Hw1-Extcompute_pi-geXUeYjdv1I)中的 error rate 分析精準度
## 開發環境

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
型號：              61
Model name:            Intel(R) Core(TM) i5-5250U CPU @ 1.60GHz
製程：              4
CPU MHz：             1941.699
CPU max MHz:           2700.0000
CPU min MHz:           500.0000
BogoMIPS:              3200.29
虛擬：              VT-x
L1d 快取：          32K
L1i 快取：          32K
L2 快取：           256K
L3 快取：           3072K

## 時間函數比較
參考資料： [四種函數比較](http://www.cnblogs.com/krythur/archive/2013/02/25/2932647.html)
clock()函數的精確度是10毫秒(ms)
times()函數的精確度是10毫秒(ms)
gettimofday()函數的精確度是微秒(μs)
clock_gettime()函數的計量單位為十億分之一，也就是纳秒(ns)

**clock()**:
ANSI clock有三個問題:
1)如果超過一個小時,將要導致溢出.
2)函數clock沒有考慮CPU被子進程使用的情況.
3)也不能區分用戶空間和内核空間.

**times()**：
原型如下：
clock_t times(struct tms *buf);

tms 結構體如下:
strace tms{
clock_t tms_utime;
clock_t tms_stime;
clock_t tms_cutime;
clock_t tms_cstime;
}

tms_utime紀錄的是進程執行用戶代碼的時間.
tms_stime紀錄的是進程執行内核代碼的時間.
tms_cutime紀錄的是子進程執行用互代碼的時間.
tms_cstime紀錄的是子進程執行内核代碼的時間.

* clock_t times(struct tms *buf);返回值是過去一段時間内時鐘滴答的次數.
* times()函數返回值也是一个相對時間.

**clock_gettime()**:

在POSIX1003.1中增了這個函數,它的原型如下：
int clock_gettime(clockid_t clk_id, struct timespec *tp);

1)它也有一個時間結構體:timespec ,timespec計算時間次數的單位是十億分之一秒.
strace timespec{
time_t tv_sec;
long tv_nsec;
}

2)clockid_t是確定哪個時鐘類型.

CLOCK_REALTIME: 標準POSIX實時時鐘
CLOCK_MONOTONIC: POSIX時鐘,以恆定速率運行;不會複位和調整,它的取值和CLOCK_REALTIME是一樣的.

**gettimeofday()**:
1)概述:
gettimeofday()可以獲得當前系统的时间,是一个绝对值

原型如下：
int gettimeofday ( struct timeval * tv , struct timezone * tz )

timeval結構體的原型如下:
struct timeval {
time_t tv_sec;
suseconds_t tv_usec;
};

所以它可以精確到微秒

* time 和 gettimeofday 不適合當作 benchmark 因為他們都是計算真實時間，可能會受到其他程序的影響。
* clock ,clock_gettime, times 之返回值是進程所使用之CPU時間
* clock_gettime 可以選擇要使用 REALTIME 或是 MONOTONIC ，使用前者的話，當系統的時鐘源被改變，或是系統管理員重製時間的話，就會受到影響。後者只受 jiffies 值的影響，較穩定。
## 開發紀錄

time ./time_test_baseline
N = 400000000 , pi = 3.141593
1.46user 0.00system 0:01.46elapsed 99%CPU (0avgtext+0avgdata 1776maxresident)k
0inputs+0outputs (0major+84minor)pagefaults 0swaps
time ./time_test_openmp_2
N = 400000000 , pi = 3.141593
1.67user 0.00system 0:00.84elapsed 198%CPU (0avgtext+0avgdata 1868maxresident)k
0inputs+0outputs (0major+86minor)pagefaults 0swaps
time ./time_test_openmp_4
N = 400000000 , pi = 3.141593
3.44user 0.00system 0:01.00elapsed 345%CPU (0avgtext+0avgdata 1728maxresident)k
0inputs+0outputs (0major+91minor)pagefaults 0swaps
time ./time_test_avx
N = 400000000 , pi = 3.141593
1.10user 0.00system 0:01.11elapsed 99%CPU (0avgtext+0avgdata 1800maxresident)k
0inputs+0outputs (0major+85minor)pagefaults 0swaps
time ./time_test_avxunroll
N = 400000000 , pi = 3.141593
0.82user 0.00system 0:00.82elapsed 99%CPU (0avgtext+0avgdata 1760maxresident)k
0inputs+0outputs (0major+84minor)pagefaults 0swaps

跑完之後發現有三種時間
分別是在[作業說明](https://hackmd.io/s/HkiJpDPtx#)中所提到的：

real time : 也就是 Wall-clock time，當然若有其他程式同時在執行，必定會影響到。
user time (elapsed): 表示程式在 user mode 佔用所有的 CPU time 總和。
sys time : 表示程式在 kernel mode 佔用所有的 CPU time 總和 ( 直接或間接的系統呼叫 )。

接下來使用 make gencsv:

$ make gencsv

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

接下來準備將資料做成圖表，使用 `make plot` （scripts 參考[laochanlam的共筆](https://hackmd.io/s/H1TUAblqg#)）產生以下分析圖：


增加迭代數量：

$ make gencsv

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


可以發現 OpenMP 的情況非常不穩定，不論是2條或是4條 threads
## Leibniz formula for π

在資料夾內新建兩個檔案：LeibnizPi.c 以及 LeibnizPi.h，在 LeibnizPi.c 中實作 baseline, OpenMP 以及 avx 和 avx_unrolling 來比較不同方法所得到的不同效能之間的差異

Baseline:

double compute_pi_leibniz(size_t N)
{
    double pi = 0.0;
    for(size_t i = 0; i < N; i++) {
        int sign = i % 2 == 0 ? 1 : -1;
        pi +=  (sign / (2.0 * (double) i + 1.0));
    }

    return pi * 4.0;
}

對實作 Leibniz formula 之各種方法進行測試：

time ./time_test_baseline
N = 400000000 , pi = 3.141593
1.64user 0.00system 0:01.65elapsed 99%CPU (0avgtext+0avgdata 1708maxresident)k
0inputs+0outputs (0major+82minor)pagefaults 0swaps
time ./time_test_openmp_2
N = 400000000 , pi = 3.141593
1.68user 0.00system 0:00.85elapsed 198%CPU (0avgtext+0avgdata 1796maxresident)k
0inputs+0outputs (0major+85minor)pagefaults 0swaps
time ./time_test_openmp_4
N = 400000000 , pi = 3.141593
3.49user 0.00system 0:00.91elapsed 384%CPU (0avgtext+0avgdata 1808maxresident)k
0inputs+0outputs (0major+91minor)pagefaults 0swaps
time ./time_test_avx
N = 400000000 , pi = 3.141593
0.96user 0.00system 0:00.96elapsed 99%CPU (0avgtext+0avgdata 1704maxresident)k
0inputs+0outputs (0major+84minor)pagefaults 0swaps
time ./time_test_avxunroll
N = 400000000 , pi = 3.141593
0.78user 0.00system 0:00.79elapsed 99%CPU (0avgtext+0avgdata 1760maxresident)k
0inputs+0outputs (0major+84minor)pagefaults 0swaps

跟原始方法比較起來，此 baseline 的速度慢了 0.0016 s。
而 OpenMP 不論是4條抑或是2條 Threads 運行速度都差在0.0006秒附近，而且 4 條的速度比2條的慢了 0.0006s ! 4條速度比較慢的原因推估是因為主要的時間花費不是再計算，而是在等待。
avx_unrolling 兩者之間也只差了0.0003s，avx 就相差比較多，有0.0015s，這兩種優化方式都是 Leibniz formula 勝。

分析圖：

## 結論

我們可以從兩種不同 pi 的計算方式之分析圖發現，OpenMP 再這兩者當中都是最不穩定的方法，推估是因為 thread 之執行速度每次都不盡相同，若電腦工作多的時候速度會變慢，因為要和電腦程序爭 CPU time。