2016q3 Homework1 (compute-pi)

# 2016q3 Homework1 (compute-pi) contributed by <`TempoJiJi`> ### Reviewed by `ierosodin` * 解釋為何在兩種計算π的實驗中, openmp p4的抖動幅度都是最大的 * 列出不同function之間, 計算結果與π實際值的誤差圖（理論應相同, 但實際並非） * 在使用Leibniz formula計算π時, (-1)^i^ 只有兩種結果, 不須計算pow(-1, i) * 可以比較多種thread數量對效能的影響 * avx或avx_unroll的實作, code在N的計數上是有殘缺 * openmp在不同thread對效能的影響, 會是在real time上有較明顯的差異, 可以比較多組資料後進行分析 * 對於資料的抖動問題, 可以嘗試使用95%信賴區間對資料進行分類 ## 預期目標 * 學習透過離散微積分求圓周率 * Leibniz formula for π * 積分計算圓周率π * Function * 著手透過 SIMD 指令作效能最佳化 ## 開發環境 * Ubuntu 16.04 LTS * L1d cache: 32K * L1i cache: 32K * L2 cache: 256K * L3 cache: 3072K * Architecture: x86_64 * CPU op-mode(s): 32-bit, 64-bit * Byte Order: Little Endian * CPU(s): 4 * Model name: Intel(R) Core(TM) i5-4200U CPU @ 1.60GHz >> 應該一併列出 processor model，這對解讀數據來說很重要 [name=jserv] --- ## 測試程式效能觀察程式的行爲後，在Makefile裏看見了這個編譯選項： ` -DBASELINE ` 才學到原來能在編譯動態使用#define ```shell $ make check time ./time_test_baseline N = 400000000 , pi = 3.141593 4.41user 0.00system 0:04.43elapsed 99%CPU (0avgtext+0avgdata 1792maxresident)k 0inputs+0outputs (0major+87minor)pagefaults 0swaps time ./time_test_openmp_2 N = 400000000 , pi = 3.141593 4.89user 0.00system 0:02.45elapsed 199%CPU (0avgtext+0avgdata 1784maxresident)k 0inputs+0outputs (0major+88minor)pagefaults 0swaps time ./time_test_openmp_4 N = 400000000 , pi = 3.141593 9.49user 0.00system 0:02.46elapsed 385%CPU (0avgtext+0avgdata 1736maxresident)k 0inputs+0outputs (0major+90minor)pagefaults 0swaps time ./time_test_avx N = 400000000 , pi = 3.141593 1.28user 0.00system 0:01.28elapsed 99%CPU (0avgtext+0avgdata 1704maxresident)k 0inputs+0outputs (0major+83minor)pagefaults 0swaps time ./time_test_avxunroll N = 400000000 , pi = 3.141593 1.23user 0.00system 0:01.23elapsed 99%CPU (0avgtext+0avgdata 1716maxresident)k 0inputs+0outputs (0major+84minor)pagefaults 0swaps ``` 在這裏就可以很清楚的看到每種不同的版本的執行時間（N=400000000)，這裏有3種不同的時間： * user time: 表示程式佔用CPU的總時間（在user mode下），其它的processes不算進去。如果當兩個執行在兩個CPU上運行各1秒，那麼總user time會是2秒 * system time: 表示程式在kernel mode下佔用CPU的總時間，其它的processes不算進去 * real time: 在上面爲elapsed。也就是 Wall-clock time，從程式開始到結束的總時間，如果有其它程式在運行着，會影響到這個時間。 ## CPU bound and I/O bound * CPU bound: 指的是程序需要大量的 ==CPU computation== (對 CPU time 需求量大)，相比之下僅需少量的 I/O operation，==效能取決於 CPU 速度==。 * I/O bound: ==需要大量 I/O operation== (I/O request 的頻率很高或一次 I/O request 成本很高)，但僅需少量的 CPU computation，==效能取決於 I/O device 速度==。 1. `real < user` : 表示程式是==CPU bound==，所以使用平行處理對效能提升有幫助 2. `real ≒ user` : 表示程式是==CPU bound==，但即使使用平行處理，效能也不會有明顯的提升，有可能是計算兩沒有很大，又或是程式的相依性太高 3. `real > user` : 表示程式是==I/O bound==，成本大部分爲I/O操作，所以使用平行處理並不會帶來顯著的效能提昇 (或沒有提昇) 參考資料： * [What do 'real', 'user' and 'sys' mean](http://stackoverflow.com/questions/556405/what-do-real-user-and-sys-mean-in-the-output-of-time1) --- 接下來看看make gencsv： ```shell= $ make gencsv for i in `seq 100 5000 25000`; do \ printf "%d," $i;\ ./benchmark_clock_gettime $i; \ done > result_clock_gettime.csv ``` 這裏的for相等於： ```clike= for(i = 100; i <= 25000; i+=5000) ``` 大意就是將N初始化爲100進行測試，每次加5000直到25000。然後將結果輸出到result_clock_gettime.csv裏執行`make plot`輸出結果，在Makefile裏加入： ```ruby= plot: gencsv gnuplot runtime.gp clean: rm -f $(EXECUTABLE) *.o *.s result_clock_gettime.csv runtime.png ``` 執行 ```shell= $ make plot ``` ![](https://i.imgur.com/73L9XGg.png) baseline的計算結果誤差圖： ![](https://i.imgur.com/tnWAYy8.png) --- ## 運用不同的方式計算pi ![](https://i.imgur.com/3mUF7g8.png) 上面這種方法就是目前baseline使用的 ```clike= double compute_pi_baseline(size_t N) { double pi = 0.0; double dt = 1.0 / N; // dt = (b-a)/N, b = 1, a = 0 for (size_t i = 0; i < N; i++) { double x = (double) i / N; // x = ti = a+(b-a)*i/N = i/N pi += dt / (1.0 + x * x); // integrate 1/(1+x^2), i = 0....N } return pi * 4.0; } ``` N 爲積分區間[0,1]的分段大小，理論上N分的越細（N值很大)精準度就越高，相對的計算量也很大 --- ## Leibniz formula for π ![](https://i.imgur.com/Do0jj21.png) 參考資料:[Wikipedia](https://en.wikipedia.org/wiki/Leibniz_formula_for_%CF%80) Code： ```clike= double compute_pi_leibniz(size_t N) { double pi = 0.0; for(int i=0;i<N;i++) pi += pow(-1,i) / (2*i+1); return pi * 4.0; } ``` leibniz_avx : ```clike= double leibniz_avx(size_t N) { double pi = 0.0; register __m256d ymm0,ymm1,ymm2,ymm3,ymm4; ymm0 = _mm256_set_pd(1.0,-1.0,1.0,-1.0); ymm1 = _mm256_set1_pd(1.0); ymm2 = _mm256_set1_pd(2.0); ymm4 = _mm256_setzero_pd(); for(int i=0 ; i <= N-4 ; i+=4){ ymm3 = _mm256_set_pd(i, i+1.0, i+2.0, i+3.0); // i to i+4 ymm3 = _mm256_mul_pd(ymm3 , ymm2); // 2*i (i to i+4) ymm3 = _mm256_add_pd(ymm3 , ymm1); // 2*i+1 (i to i+4) ymm3 = _mm256_div_pd(ymm0 , ymm3); // pow(-1,i) / ymm3 ymm4 = _mm256_add_pd(ymm4 , ymm3); // pi += ymm3 } double tmp[4] __attribute__((aligned(32))); _mm256_store_pd(tmp, ymm4); // move packed float64 values to 256-bit aligned memory location pi += tmp[0] + tmp[1] + tmp[2] + tmp[3]; return pi * 4.0; } ``` 查看效能： ```shell= $ make check N = 400000000 , pi = 3.141593 2.20user 0.00system 0:02.20elapsed 99%CPU (0avgtext+0avgdata 1708maxresident)k 0inputs+0outputs (0major+83minor)pagefaults 0swaps time ./time_test_leibniz_openmp_2 N = 400000000 , pi = 3.141593 2.45user 0.00system 0:01.23elapsed 199%CPU (0avgtext+0avgdata 1768maxresident)k 0inputs+0outputs (0major+86minor)pagefaults 0swaps time ./time_test_leibniz_openmp_4 N = 400000000 , pi = 3.141593 4.78user 0.00system 0:01.23elapsed 386%CPU (0avgtext+0avgdata 1788maxresident)k 0inputs+0outputs (0major+93minor)pagefaults 0swaps time ./time_test_leibniz_avx N = 400000000 , pi = 3.141593 1.35user 0.00system 0:01.36elapsed 99%CPU (0avgtext+0avgdata 1788maxresident)k 0inputs+0outputs (0major+85minor)pagefaults 0swaps time ./time_test_leibniz_avxunroll N = 400000000 , pi = 3.141593 1.71user 0.00system 0:01.71elapsed 99%CPU (0avgtext+0avgdata 1932maxresident)k 0inputs+0outputs (0major+89minor)pagefaults 0swaps ``` 在這裏觀察openmp： * openmp_2 跟 openmp_4 的real time幾乎相等，在user time上卻相差很多，可見程式本身的相依性高。但跟普通的比起來，效能卻是提升了不少以下爲leibniz各個不同實做的效能對比圖： ![](https://i.imgur.com/oNa580M.png) leibniz的計算結果誤差圖： ![](https://i.imgur.com/UfN4Nyj.png) --- ## 思考如何精準計算時間 1. [clock()](https://linux.die.net/man/3/clock) 原型： ```clike clock_t clock(void); ``` * clock() 函数的返回值类型是clock_t,它除以CLOCKS_PER_SEC来得出时间 * clock()有3個問題： * 超過一小時，會overflow * 沒有考慮CPU被子進程使用的情況 * 也不能區分user mode和kernel mode clock()測試： ```clike= #include <stdio.h> #include <stdlib.h> #include <time.h> int main( void ) { long i=1000L; clock_t start, finish; double duration; printf( "Time to do %ld empty loops is ", i ); start = clock(); while (--i){ system("cd"); } finish = clock(); duration = (double)(finish - start) / CLOCKS_PER_SEC; printf( "%f seconds\n", duration ); return 0; } ``` 執行結果： ```shell= $ time ./clock_test Time to do 1000 empty loops is 0.049815 seconds real 0m0.482s user 0m0.000s sys 0m0.052s ``` 在這裏可以看到程式使用system("cd")這個system call，結果clock()所計算出來的時間跟real time卻差很多。 --- 2. [clock_gettime()](https://linux.die.net/man/3/clock_gettime) 函式原型： ```clike int clock_gettime(clockid_t clk_id, struct timespec *tp); ``` 第一個參數clockid_t 確定要用哪個是種類型： * `CLOCK_REALTIME`: 標準POSIX即時時鐘，利用變數xtime記錄RTC的時間。會隨着系統即時時間而改變，即從 `1970/1/1 00:00:00` 開始計時，中間如果系統時間被改變，則對應的時間也會被改變 * `CLOCK_MONOTONIC`: 從系統啓動時開始計算，利用jiffies來記錄，不會受到系統時間被改變的影響，但會因爲NTP的改變而受到影響 * `CLOCK_MONOTONIC_RAW`：跟CLOCK_MONOTONIC一樣，但不會受到NTP的影響 * `CLOCK_PROCESS_CPUTIME_ID`: 記錄一個process裏所話的總CPU時間(User mode & Kernel mode)，不包含等I/O和其他資源的時間。 * `CLOCK_THREAD_CPUTIME_ID`: 記錄一個thread所花的總CPU時間有個時間結構體 `timespec`，其計時的單位是奈秒（nanosecond） ``` clike strace timespec { time_t tv_sec; /* seconds */ long tv_nsec; /* nanoseconds */ } ``` 1. xtime: 從cmos電路中取得RTC的時間 2. jiffies: 從電腦開機到目前的總共時鍾中斷(time interrupt)次數 --- 3. [time()](https://linux.die.net/man/2/time) 原型： ```clike time_t time(time_t *t); ``` Description time() returns the time as the number of seconds since the Epoch, 1970-01-01 00:00:00 +0000 (UTC). 4. [gettimeofday()](https://linux.die.net/man/2/gettimeofday) 原型： ```clike int gettimeofday ( struct timeval * tv , struct timezone * tz ) ``` 跟time()一樣，但會回傳多一個timezone，看下面這個timeval的結構： ```clike struct timeval { time_t tv_sec; /* seconds */ suseconds_t tv_usec; /* microseconds */ }; ``` ==Notes==: The time returned by gettimeofday() is affected by discontinuous jumps in the system time (e.g., if the system administrator manually changes the system time). 如果系統時間被改變，那麼gettimeofday()所回傳的值，會被不連續的跳動時間所影響 --- 1. 為什麼 time() 和 gettimeofday() 不適合拿來作 benchmark ? 在上面可以看到 ==time()== 跟 ==gettimeofday()== 都是直接回傳系統時間，所以如果系統時間在程式執行期間被改變，那麼回傳出來的值就會不準確。而且爲了要跟NTP同步，在同步的期間可能會有幾秒的誤差。 2. 爲什麼clock_gettime()結果飄忽不定？ ==clock_gettime()== 會因爲不同的進程在CPU之間切換而受到影響。解決方法就是利用clock_gettime()找出95%信賴區間，這樣得到的數據就更加精準。參考資料： * [gettimeofday() should never be used to measure time](https://blog.habets.se/2010/09/gettimeofday-should-never-be-used-to-measure-time) * [clock()、time()、clock_gettime()和gettimeofday()函数的用法和区别](http://www.cnblogs.com/krythur/archive/2013/02/25/2932647.html) * [C library function: clock_gettime](http://oyh.logdown.com/posts/231106-c-clock-gettime) * [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) * [Difference between CLOCK_REALTIME and CLOCK_MONOTONIC?](http://stackoverflow.com/questions/3523442/difference-between-clock-realtime-and-clock-monotonic) * [容易混淆LINUX時鐘的xtime和jiffies](http://www.coctec.com/docs/linux/show-post-186188.html) ###### tags: `TempoJiJi` `ComputePi` `sysprog21`

Read more

針對多執行緒環境設計的 Memory allocator

Dynamically allocate space Note

2016q3 Homework3 (mergesort-concurrent)

2016q3 Homework1 (raytracing)