Try   HackMD

2016q3 Homework1 (compute-pi)

contributed by <Jing Zhou>

開發環境

ubuntu 16.04

準備工作

計算圓周率pi

  • 黎曼積分
  • Leibniz formula for π

方法

  • Baseline
  • AVX SIMD
  • AVX SIMD + Unroll looping
  • OpenMP

Wall-clock time vs. CPU time

  • Wall-clock time
    現實世界中實際經過的時間，Wall-clock time不一定是單調遞增，但量測過程中沒有涉及到 NTP、時區改變之類的問題，所以經過的 system time (elapsed time) 基本上會等於真實走過的時間

  • CPU time
    CPU 上面運行消耗 (佔用) 的時間，每條 thread 的使用時間加總

  • time 指令返回值

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

  • CPU bound 與 I/O bound

    • CPU bound，對 CPU time 需求量大，僅需少量的 I/O operation
    • I/O bound，需要大量 I/O operation，僅需少量的 CPU computation

  • 判斷效能
    效能提昇表示平行處理有得到好處

    • real < user: 程式為CPU bound，效能有提昇。
    • real ≒ user: 程式為CPU bound，效能沒有明顯提昇。
    • real > user: 程式為I/O bound，效能提昇不顯著或無。

計時精準度

  • clock()
    精準度為毫秒 10-3，傳回以 1/CLOCKS_PER_SEC 測量的時間(
    1/1000)
  • clock_gettime()
    精準度為奈秒 10-9，可設定取出monotonic的時間
    #define CLOCK_ID CLOCK_MONOTONIC_RAW
  • time() 精度只到秒，不準
  • gettimeofday() 精準度為微秒 10-6
    原型int gettimeofday(struct timeval*tv,struct timezone *tz )
    其中timezone 結構定義為： 
    ​struct  timezone{
​		int tz_minuteswest;/*和greenwich 時間差了多少分鐘*/
​		int tz_dsttime;/*type of DST correction*/
​}
    量測程式時間不需要用到，非單調遞增

compute-pi實做

$ git clone https://github.com/sysprog21/compute-pi
$ cd compute-pi
$ make check
  • 結果，使用 treads 的 openmp_2 和 openmp_4 時間 real < user，效能有明顯提升
time ./time_test_baseline
N = 400000000 , pi = 3.141593
1.04user 0.00system 0:01.04elapsed 99%CPU (0avgtext+0avgdata 1784maxresident)k
0inputs+0outputs (0major+85minor)pagefaults 0swaps

time ./time_test_openmp_2
N = 400000000 , pi = 3.141593
1.12user 0.00system 0:00.56elapsed 198%CPU (0avgtext+0avgdata 1808maxresident)k
0inputs+0outputs (0major+88minor)pagefaults 0swaps

time ./time_test_openmp_4
N = 400000000 , pi = 3.141593
1.14user 0.00system 0:00.28elapsed 398%CPU (0avgtext+0avgdata 1836maxresident)k
0inputs+0outputs (0major+90minor)pagefaults 0swaps

time ./time_test_avx
N = 400000000 , pi = 3.141593
0.50user 0.00system 0:00.51elapsed 99%CPU (0avgtext+0avgdata 1768maxresident)k
0inputs+0outputs (0major+84minor)pagefaults 0swaps

time ./time_test_avxunroll
N = 400000000 , pi = 3.141593
0.36user 0.00system 0:00.36elapsed 99%CPU (0avgtext+0avgdata 1816maxresident)k
0inputs+0outputs (0major+87minor)pagefaults 0swaps

  • 使用clock_gettime()執行
    Bash的迴圈用法：r i in $(seq [初始] [增值] [上界]);
    Makefile中改為for i in `seq 100 100 50000`;

  • 使用gnuplot產生圖表
    修改Makefile和新增plot.gp，使用gencsv產生的csv來繪製圖檔

    ​# plot.gp
​reset
​set ylabel 'Time(sec)'
​set xlabel 'N'
​set style data lines
​set title 'Wall-clock time - using clock _gettime()'
​set datafile separator ","
​set terminal png enhanced font 'Verdana,10'
​set output 'runtime.png'

​plot [0:][0:0.01]'result_clock_gettime.csv' using 1:2 title 'Baseline', \
​'' using 1:3 title 'OpenMP (2 threads)', \
​'' using 1:4 title 'OpenMP (4 threads)', \
​'' using 1:5 title 'AVX', \
​'' using 1:6 title 'AVX + Unroll looping'

    執行

    結果，OpenMP因為使用4個treads的關係，效能比AVX SIMD + Unroll looping還好

  • clock_gettime() 與 clock() 比較
    benchmark_clock.c中clock()使用以下算法

    ​clock_t start=0, end=0;
​
​# 略
​
​start = clock();
​​​​for(i = 0; i < loop; i++) {
​​​​    compute_pi_baseline(N);
​​​​}
​end = clock();
​​​​printf("%lf,", ((double) (end - start)) / CLOCKS_PER_SEC);

    使用clock()結果圖，發現讀取時間的效能比gettime()還差
    初步懷疑跟monotonic有關

Last changed by 
 
ChunJing Zhou
0
526
Published on HackMD