changed 6 years ago  
Linked with GitHub

2017q1 Homework1 (compute-pi)

contributed by < etc276 >

tags: 嵌入式

Reviewed by yangyang95

  • 不是超連結的文字 ( eg. link text )，不要使用超連結符號，可用 粗體
  • 第一張 error rate 的圖形不清楚，且範圍需修改
  • binary file 不要一起送上 github ，可在 .gitignore 中加入 *.png *.txt 來忽略特定檔案格式
  • 程式碼還可以在稍微精簡一點點，並注意 coding style 小括號左方要留有空白










double compute_pi_leibniz (size_t N)
{
    double pi = 0.0;
    int tmp = 1;
    for (size_t i = 0; i < N; i++) {
        pi += tmp / (2.0 * (double)i + 1.0);
        tmp *= (-1);
    }
    return 4 * pi;
}

開發環境

  • Ubuntu 16.10 (64bit)
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:                 61
Model name:            Intel(R) Core(TM) i7-5500U CPU @ 2.40GHz
Stepping:              4
CPU MHz:               2400.878
CPU max MHz:           3000.0000
CPU min MHz:           500.0000
BogoMIPS:              4788.90
Virtualization:        VT-x
L1d cache:             32K
L1i cache:             32K
L2 cache:              256K
L3 cache:              4096K
NUMA node0 CPU(s):     0-3

作業要求

  • 在 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 製圖，紀錄於「作業區」

開發紀錄

重現實驗

  • $ make check 後查看各版本時間
$ time ./time_test_baseline
N = 400000000 , pi = 3.141593
real    0m1.388s
user    0m1.376s
sys     0m0.004s

$ time ./time_test_openmp_2
N = 400000000 , pi = 3.141593
real    0m1.324s
user    0m2.632s
sys     0m0.000s

$ time ./time_test_openmp_4
N = 400000000 , pi = 3.141593
real    0m0.770s
user    0m2.768s
sys     0m0.000s

$ time ./time_test_avx
N = 400000000 , pi = 3.141593
real    0m0.922s
user    0m0.920s
sys     0m0.000s

$ time ./time_test_avxunroll
N = 400000000 , pi = 3.141593
real    0m0.721s
user    0m0.712s
sys     0m0.004s
  • 分析 real, user, sys 的不同
    1. real time :
      也就是 Wall-clock time，當然若有其他程式同時在執行，必定會影響到。
    2. user time : 表示程式在 user mode 佔用所有的 CPU time 總和。
    3. sys time : 表示程式在 kernel mode 佔用所有的 CPU time 總和 ( 直接或間接的系統呼叫 )。

增加迭代

  • 查看 Makefile 發現以下程式碼





gencsv: default
        for i in `seq 100 5000 25000`; do \
                printf "%d," $$i;\
                ./benchmark_clock_gettime $$i; \
        done > result_clock_gettime.csv
  • 而這段程式碼可理解為


for (i=100; i<=25000; i+=5000)
    compute_pi(i);
  • 增加迭代前的圖 (i<=25000)
  • 增加迭代後的圖 (i<=250000)
  • 可發現 OpenMP (4 Thread)的時間漂浮有點大，晚點再來想原因

研究 error rate

  • 查看 Makefile 發現用來產生圖檔的資料 csv 檔是由 benchmark_clock_gettime 輸出，因此修改此 .c 檔，再輸出 error。後改為寫一個 out.pg，並在 Makefile 新增 plot :以產生兩種圖檔。

  • 產生圖檔的過程遇到一個困難是，csv 檔的資料分隔是用逗號(，)所以一開始想用 "%lf,%lf,%lf,%lf,%lf,%lf" 的方式撰寫 out.pg，後來才發現可以使用 set datafile separator ","

  • 用 gnuplot 畫出來的 error rate

  • 在 out.pg 加上 set logscale xy ，看的細一點

Leibniz formula for π

參考 shelly4132的共筆

考慮以下分解：
image alt

對兩邊從0到1去做積分

當時，除積分項以外的項收斂到萊布尼茨級數。同時，積分項收斂到0：

所以這便證明了萊布尼茨公式。












double compute_pi_leibniz(size_t N)
{
    double pi = 0.0;
    int tmp = 1;
    for (size_t i =0; i < N; i++) {
        pi += tmp / (2.0 * (double)i + 1.0);
        tmp *= (-1);
    }
    pi *= 4; 
    return pi;
}
  • 補圖


其他計算圓周率的方式如 蒙地卡羅、尤拉等等 (待補實作code)

Select a repo