Try   HackMD

2016q3 Homework1(Compute-pi)

作業要求

  • 在 GitHub 上 fork compute-pi,嘗試重現實驗,包含分析輸出
    • 注意: 要增加圓周率計算過程中迭代的數量,否則時間太短就看不出差異
  • 詳閱廖健富提供的詳盡分析,研究 error rate 的計算,以及為何思考我們該留意後者
  • phonebok 提到的 gnuplot 作為 $ make gencsv 以外的輸出機制,預期執行 $ make plot 後,可透過 gnuplot 產生前述多種實做的效能分析比較圖表
  • 可善用 rayatracing 提到的 OpenMP, software pipelining, 以及 loop unrolling 一類的技巧來加速程式運作
  • 詳閱前方 "Wall-clock time vs. CPU time",思考如何精準計算時間
  • 除了研究程式以外,請證明 Leibniz formula for π,並且找出其他計算圓周率的方法
  • 將你的觀察、分析,以及各式效能改善過程,並善用 gnuplot 製圖,紀錄於「作業區

開發環境

  • Ubuntu 14.04
  • CPU model:
    • model: 78
    • name: Intel® Core m3-6Y30 CPU @ 0.90GHz
  • cpu MHz : 499.570
  • Cache
    • L1d 快取: 32K

    • L1i 快取: 32K

    • L2 快取: 256K

    • L3 快取: 4096K

      指令:
      $ uname -a
      $ lscpu
      $ cat /proc/cpuinfo

重現實驗

先照著跑跑看~

$ 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裡面介紹的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 TempoJiJi同學筆記What do 'real', 'user' and 'sys' mean in the output of time(1)

再來看benchmark,

$ make gencsv

用gnuplot製圖:

這裡卡了很久, 撰寫注意事項有:

  1. 參考Petermouse同學 因為資料是以逗號分隔, 所以需要加上

    ​​ set datafile separator ","
    
  2. \後面不要有空隔

gnuplot:

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理解Makefile

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中加上

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?

我的理解如下:

  1. time()的時間精度是1秒,這次的實驗的數據多半在毫秒左右所以不適合。
  2. getrusage():在linux x86是一個system call
  3. clock()在資料裡面提到約2^32 ticks的時候會wrap around(存取周遭)
  4. clock_gettime(CLOCK_MONOTONIC_RAW,)可以以monotonic的方式執行, 不會wrap around。不過我在What is the difference between CLOCK_MONOTONIC & CLOCK_MONOTONIC_RAW?看到有人提及因為clock_gettime是提供一個offset來使他不會被改變, 當clock發生變化的時候他可能沒辦法調整好,頻率產生變化。
  5. getrusage():這個是寫這篇評論的人相當推薦的函式,分別印出user time和system time不過精度只有到ms on linux。

我在想clock_gettime雖然有monotonic而且精度比較高(nano),可是他包含了程式以外的時間; getrusage 則是比較精準的提供我們實驗所需的user time和system time相加, 不確定哪一個較好。在這裡先用getrusage試試看。

先修正原本的圖, 看到王紹華同學的筆記才發現在benchmark_clock_gettime.c中的clock_gettime包含了整個loop。

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。

寫的程式如下:

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 ProcessorsWhat are threads, and what do they do in the processor?

參考資料

tags: Ruby 2016_Autumn HW1 computepi