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
Last changed by 
 
施雨妏
0
783
Published on HackMD