2016q3 Homework1 (compute-pi)

contributed by <nekoneko>

tags: `nekoneko` `homework`

硬體資訊

Architecture:          x86_64
CPU op-mode(s):        32-bit, 64-bit
Byte Order:            Little Endian
CPU(s):                4
On-line CPU(s) list:   0-3
Thread(s) per core:    2
Core(s) per socket:    2
Socket(s):             1
NUMA node(s):          1
Vendor ID:             GenuineIntel
CPU family:            6
Model:                 37
Model name:            Intel(R) Core(TM) i3 CPU       M 330  @ 2.13GHz
Stepping:              2
CPU MHz:               933.000
CPU max MHz:           2133.0000
CPU min MHz:           933.0000
BogoMIPS:              4256.27
Virtualization:        VT-x
L1d cache:             32K
L1i cache:             32K
L2 cache:              256K
L3 cache:              3072K
NUMA node0 CPU(s):     0-3
Flags:                 fpu vme de pse tsc msr pae mce cx8 apic sep mtrr pge mca cmov pat pse36 clflush dts acpi mmx fxsr sse sse2 ss ht tm pbe syscall nx rdtscp lm constant_tsc arch_perfmon pebs bts rep_good nopl xtopology nonstop_tsc aperfmperf pni dtes64 monitor ds_cpl vmx est tm2 ssse3 cx16 xtpr pdcm sse4_1 sse4_2 popcnt lahf_lm tpr_shadow vnmi flexpriority ept vpid dtherm arat

SIMD AVX

emulator: Intel SDE

Install

$ mkdir ~/bin && mv sde-external-7.49.0-2016-07-07-lin .

.profile

PATH="$PATH:$HOME/bin/sde-external-7.49.0-2016-07-07-lin"

$ source .profile

若在Ubuntu 10以上要關掉yama

$ sudo i
$ echo 0 > /proc/sys/kernel/yama/ptrace_scope && exit

Run
- Emulate Everything Mode
  預設bash shell都接到sde64上執行
```
$ sde64 -- /bin/bash
```

作業資料筆記

Wall-clock time
- xtime
- jiffies
CPU time
- Real time
- User CPU time
- System CPU time
- real - cpu-time(user + sys)
clock_gettime()

Compute-pi

$ make check
$ make gencsv

到makefile可以知道make gencsv做什麼





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

之後增加資料點的話，改seq

seq:

       seq [OPTION]... LAST
       seq [OPTION]... FIRST LAST
       seq [OPTION]... FIRST INCREMENT LAST

原始LibreOffice輸出

make check

time ./time_test_baseline
N = 400000000 , pi = 3.141593
229.57user 0.44system 3:50.18elapsed 99%CPU (0avgtext+0avgdata 39988maxresident)k
0inputs+0outputs (0major+36347minor)pagefaults 0swaps
time ./time_test_openmp_2
N = 400000000 , pi = 3.141593
234.88user 0.11system 1:58.07elapsed 199%CPU (0avgtext+0avgdata 41556maxresident)k
0inputs+0outputs (0major+39560minor)pagefaults 0swaps
time ./time_test_openmp_4
N = 400000000 , pi = 3.141593
355.82user 0.35system 1:38.23elapsed 362%CPU (0avgtext+0avgdata 41324maxresident)k
0inputs+0outputs (0major+40143minor)pagefaults 0swaps
time ./time_test_avx
N = 400000000 , pi = 3.141593
134.49user 0.24system 2:14.88elapsed 99%CPU (0avgtext+0avgdata 43340maxresident)k
0inputs+0outputs (0major+37336minor)pagefaults 0swaps
time ./time_test_avxunroll
N = 400000000 , pi = 3.141593
114.62user 0.44system 1:55.14elapsed 99%CPU (0avgtext+0avgdata 44384maxresident)k
0inputs+0outputs (0major+40273minor)pagefaults 0swaps

參考同學的筆記和上網查，得知elapsed為real time

CPU percentage 代表意思還要查cheng hung lin

type	user	sys	elapsed	-
baseline	229.57	0.44	3:50.18(230.18)	x
openmp_2	234.88	0.11	1:58.07(118.07)	cpu bound
openmp_4	355.82	0.35	1:38.23(98.23)	cpu bound
avx	134.49	0.24	2:14.88(134.88)	x
avxunroll	114.62	0.44	1:55.14(115.14)	x

作業說明提到user time是"每條thread的時間加總"

man time有解釋到default output。此外elapsed格式為[hours:]mins:seconds

clock_gettime()

環境: 在Intel的模擬下跑
~~先取1~1000，看看變化是否真的不準確~~
N 取 1的時候bench_clock_gettime似乎不會結束

考量到gencsv總共會花多少時間，分別下time取N = 100, 1000, 10000, 100000, 1000000, 10000000的測試時間。其中real time分別是1.052, 1.073, 1.456, 5.256, 47.048, 7:3.214。
~~產生的測資1000到1000000，其中間隔為1000，seq 1000 1000 1000000~~ 應該太耗時間，先取seq 1000 10000 1000000

因為不會用LibreOffice先改用gnumeric

因為使用sde64 模擬器跑，所以先將max值降低和增加N樣本間去縮小，跑seq 1000 1000 100000

輸出: sde64的模擬器下跑
1000 ~ 100000, 每間隔10000取一次，共10筆資料
1000 ~ 100000, 每間隔1000取一次，共100筆資料
1000 ~ 100000，每隔間隔100取一次，共1000筆資料

最後一組數據才1000筆就跑了40多分鐘，決定avx版本分開跑!!cheng hung lin

不考慮使用Intel SDE

1000 ~ 100000, 間隔:10000，10筆
1000 ~ 100000, 間隔:1000，100筆
1000 ~ 100000, 間隔:100，1000筆

小結

使用Intel SDE跑確實有比較慢
在本機(i3 330M)是雙核行，四執行緒，openmp 2條和 4條的執行結果是一樣的。但是在Intel SED下可以看出來，openmp四條執行的時間序確實比較兩條執行序來的少。

clock()

man clock的資訊提到，glibc 2.18之後，是實做於clock id為CLOCK_PROCESS_CPUTIME_ID，clock_gettime()之上。2.17之前都是實做於times()。
wrap 的部份，在32bit的系統上面，CLOCKS_PER_SEC為1000000，會大約在每72分鐘回傳相同的值(?)

不是很懂wrap的意思cheng hung lin

clock 使用方式

#include <time.h>
clock_t clock(void);

1000 ~ 100000, 間隔:100，1000筆

筆電雙核虛擬四核，要再研究

Hyper Threadingcheng hung lin

Error Rate

參考廖健富學長筆記

baseline
1000000到100000000,間隔100000，共1000筆

分佈

試做將某次測量時間做m次，產生母體，做分佈圖觀察

baseline, 積分迴圈做100000，樣本取1000次。因為樣本都小於零，無法算次數，所以下圖所有時間都乘上10^5

time*10^5, count

不熟悉gnuplot，應該要畫成更能看出分佈的historgramcheng hung lin

信賴區間

還是參考同份共筆，實做第一板的信賴區間計算source
信賴區間
- 平均數
- 標準差 (這裡使用的是取樣的標準差算法)
- 正負兩個標準差之間為95%的信賴區間
其實沒有看懂信賴區間的算法，最後先直接照著算
1000 到 100000，間隔為1000，100筆資料，每筆母體樣本100筆
因為間隔為100的資料要跑很久(可能約1、2小時)，沒有下去跑。不然間隔100的資料應該會更顯現差異
除了95%信賴區間純化資料，應該也可以跑看看不使用信賴區間，單純取平均的方式

Leibniz formula for π

證明
arctan微分
公式

$\frac{π}{4} = \sum_{k = 0}^{\infty} \frac{(- 1)^{k}}{2 k + 1}$
程式碼

































double compute_pi_leibniz(size_t N)
{   
    double pi = 0.0;
    int sign = 1; 
    for (size_t i = 0;i < N; i++, sign*=(-1)) {
        pi += (double) sign / ((i<<1)+1);
    }
    return pi * 4.0;
}
double compute_pi_leibniz_unroll(size_t N)
{
    double pi = 0.0;
    int base = 0;
    for (size_t i = 0;i < N - 16; i+=16) {
        base = i<<1;
        pi += (double) 1 / (base+1);
        pi += (double) -1 / (base+3);
        pi += (double) 1 / (base+5);
        pi += (double) -1 / (base+7);
        pi += (double) 1 / (base+9);
        pi += (double) -1 / (base+11);
        pi += (double) 1 / (base+13);
        pi += (double) -1 / (base+15);
        pi += (double) 1 / (base+17);
        pi += (double) -1 / (base+19);
        pi += (double) 1 / (base+21);
        pi += (double) -1 / (base+23);
        pi += (double) 1 / (base+25);
        pi += (double) -1 / (base+27);
        pi += (double) 1 / (base+29);
        pi += (double) -1 / (base+31);
    }
}

每1000間隔所得到的資料如下

leibniz在於不用像baseline一樣做到乘法處理，時間上是有減少的，但leibniz unroll 16 時間上並沒有減少很多。

timer

撰寫時間量測程式前，先評估情況，問問自己幾個問題：

使用什麼 clock 測量？(Real, User, System, Wall-clock…?)
clock 的精確度？(s, ms, µs, or faster ?)
需要多久時間你的 clock 會 wrap around？有什麼方法可以避免或處理？
clock 是不是 monotonic (單調遞增)？還是會隨著系統時間改變 (NTP, time zone, daylight savings time, by the user…?)
使用的函式使否已經過時、或不是標準函式庫？

Measure time in Linux - time vs clock vs getrusage vs clock_gettime vs gettimeofday vs timespec_get?
文章中提到的幾種clock(大部分有看沒有很懂，之後在多查資料)
- time()
  wall-time from OS, precision is second
- clock()
  - clock wrap通常發生在每2^32 ticks之後，以CPU frequency 2.13 GHz來算，約2s就會發生一次
- clock_gettime(CLOCK_MONOTONIC,....)
- getrusage()
- gettimeofday()
- mach_absolute_time()

gnu plot

xtic(N): 設定 x axis每N筆資料顯示一次
set format y %.6f: 設定ytic的label數字的顯示到小數點第六位
set xrange [min:max]
plot … with boxes
plot … with impulses
plot sin(x) linetytpe 4 # set as color 4
plot sin(x) lt rgb "#FFFFFF"
plot sin(x) lt rgb "violet"
gnuplot> show colorname(s) #顯示color name