2017q1 Homework1 (compute-pi)

contributed by < ryanwang522 >

Reviewed by Cayonliow

• openmp_4 因爲不穩定所以圖會有波動， 可以透過將執行的次數調高然後取平均來消除， 可以看看我的共筆, 我是使用 gnuplot 制圖

開發環境

• OS: 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® Core™ i5-4200H CPU @ 2.80GHz

原始版本

進行實驗

• 先執行原本的程式碼，並且熟悉一下 LibreOffice 的操作。

• loop = 25
  

  • 發現 openmp 在四個執行序的狀況下，相較於其他方法有比較不尋常的波動，不過覺得取樣空間分得太開，先將 loop 次數提高以及增加取樣次數看看會有什麼結果。

• loop = 50，取樣間隔調整為 2500
  

  • 仍然有些波動影響直觀的比較，在增加取樣以及平均的次數。

• loop = 250, 取樣間隔調整為 1000
  

  • 避免圖形難於觀察，取消點的顯示。

• 由 loop = 250，取樣間隔 1000 的圖不難觀察出執行時間的差異

  • AVX > Openmp > Baseline
  • Openmp 在 4 threads 的情況下比較不穩定，認為是 omp 在進行 Reduction 時，每個 thread 的執行速度差異互相等待，所造成的 overhead。

Error Rate

• loop = 250 , N = 100 : 5000 : 25000
  
• loop = 250 , N = 100 : 1000 : 25000
  
  • 可以看出除了 AVX unroll 的版本在 N 不夠大時會有較大的誤差以及不太穩定，其他方法的誤差隨著 N 的遞增都很快地趨近於 0。
  • 目前對於 avx unroll 為何會波動較大還想不太到解釋。

Leibniz Method

• 參考 Leibniz formula for π
• • 實作

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

• 這裡再實作一個 Openmp 的版本來進行比較
  • 因為 Leibniz 需要正負相間的運算，所以利用 schedule(static, 1) 去明確指定每個 thread 所要負責的迴圈部份。
  • 計時方法依然使用 clock_gettime()。

double compute_pi_Leibniz_omp(size_t N, int threads)
{
    double pi = 0.0;
    #pragma omp parallel for num_threads(threads) \
        reduction(+:pi) schedule(static, 1)
    for (size_t i = 0; i < N; i++) {
        if (omp_get_thread_num() % 2 == 0)
            pi += 1.0 / (2.0 * (double)i + 1.0);
        else
            pi += -1.0 / (2.0 * (double)i + 1.0);
    }   
    return (4 * pi);
}

• Leibniz 的原始版本好像就比黎曼和快了不少！
• Error Rate 比較，依然只有 AVX Unroll 較不穩定。
  
• 補上 gnuplot
  • 寫 runtime.gp 一直遇到 x range is invalid 的錯誤訊息，後來發現是 gnuplot 預設用空白來切分數據。
  • 加上 set datafile separator "," 就可以正常畫圖了！
  • 這裡可以看到 OpenMP 在某些 N 值會有執行時間莫名增加的狀況，而其他方法都還算穩定，可以推斷是 thread 之間運作的 Overhead。
    

Monte Carlo Method

Reference

GNUPLOT 讀取逗號分隔的數據文件
Leibniz formula for π - wikipedia