2016q3 Homework1 (compute-pi)

開發環境

OS:Lubuntu 16.04 LTS
Memory: 8 GB
CPU:
- Name:
  - Intel® Core™ i5-4200H CPU @ 2.80GHz
- Cache:
  - L1d Cache： 32K
  - L1i Cache： 32K
  - L2 Cache： 256K
  - L3 Cache： 3072K

Leibniz formula for π

其他取得π值的方法：
(1)黎曼ζ函數 ζ(2)=π²/6;
(2)沃利斯乘積
(3)高斯積分
(4)…

Makefile

一開始完全不知道程式要怎麼產生想要的資料，所以觀察了一下Makefile，發現比起phonebook，又多一些看不懂的東西。





gencsv: default
    for i in `seq 100 5000 25000`; do \
    printf "%d," $$i;\
    ./benchmark_clock_gettime $$i; \
    done > result_clock_gettime.csv

原來Makefile也可以用迴圈，而seq 100 5000 20000代表起始值100，等差5000，20000代表結束，其將作benchmark_clock_gettime的argv[1]，printf與benchmark_clock_gettime將匯入result_clock_gettime.csv。

觀察

在benchmark_clock_gettime.c中，每種方式都執行了25次，並且將其紀錄於表格中，如果將表格以.txt開啟，或是觀察printf輸出格式，可以發現到格式其實是以逗號分隔：

100,0.000026,0.000072,0.000061,0.000021,0.000011
5100,0.001253,0.000599,0.000637,0.000517,0.000460
10100,0.002174,0.001128,0.001122,0.001019,0.000891
15100,0.003443,0.001682,0.003035,0.001511,0.001016
20100,0.004341,0.002275,0.002194,0.002971,0.001194

因此在做圖時，script需要set datafile separator ","，gnuplot才能區分每一行。

花了很久時間才寫好script

reset

set datafile separator ","
set title "compute-pi(25 rounds)"
set xlabel 'N'
set ylabel 'time(sec)'
set terminal png size 1000,800 enhanced font 'Verdana,14'
set output 'plot.png'

plot "result_clock_gettime.csv" u 1:2  w lp title "Baseline",\
"result_clock_gettime.csv" u 1:3 w lp title "OpenMP with 2 threads",\
"result_clock_gettime.csv" u 1:4 w lp title "OpenMP with 4 threads",\
 "result_clock_gettime.csv" u 1:5 w lp title "AVX SIMD" ,\
 "result_clock_gettime.csv" u 1:5 w lp  title "AVX SIMD + Loop unrolling" ,\

圖片：

我發現每次執行都有落差(尤其是OpenMP(4))，可能時間短得不明顯又很少次，所以我把25次改為10000次

這次有了比較一致的答案：
效率上AVX+LR > AVX >>> OMP(2) > OMP(4) >>> Baseline

接著，Loop數不變，將N放大

在N比較小的情況下，OpenMP(4)有機會比Baseline效率還低，OpenMP(4)整體來說似乎不太穩定。
OpenMP(2)在9e5~1e6間也出現了明顯的升高，但在另一張圖沒有出現，對此沒有結論。
…

了解改進方法

OpenMP

平行化需要注意到的問題，就是變數的存取，不同執行緒對共享變數做修改/讀取，可能會產生不可預期的結果，OpenMP提供了很多方法來讓我們決定變數要怎麼運作。
參考OpenMP變數的平行化歸納以下幾個常用的：
private:每個執行緒有各自的變數(但不會初始化值！)。
firstprivate:同private，但變數值為執行緒前的變數值。
lastprivate:同private，但原變數值會改為執行緒結束時的值。
atomic：防止多個執行緒修改。
reduction：每個執行緒有各自的變數(值為單位元素)，最後在合併。

AVX SIMD

在raytracing時有使用過，但不是很理想。
在這裡充分的運用，ymm0~2為係數，ymm3作為運算，ymm4儲存運算結果

AVX SIMD + loop unrolling

利用到更多的avx暫存器，可以減少迴圈的數量，一個迴圈處理16個double，每個都多了原本的ymm2、ymm3、ymm4，等於一個迴圈中用了5+3+3+3=14個暫存器。

關於time

xtime vs jiffies

cpu time

作業說明中有提到CPU time是每條執行緒的時間加總，為了觀察到這個結果，我把每一種方法個別執行

petermouse@pm-X550JK:~/ws/compute-pi$ time ./time_test_baseline
N = 400000000 , pi = 3.141593

real	0m3.360s
user	0m3.356s
sys	0m0.000s
petermouse@pm-X550JK:~/ws/compute-pi$ time ./time_test_openmp_2
N = 400000000 , pi = 3.141593

real	0m2.287s
user	0m4.556s
sys	0m0.000s
petermouse@pm-X550JK:~/ws/compute-pi$ time ./time_test_openmp_4SIMD register load/store
N = 400000000 , pi = 3.141593

real	0m1.772s
user	0m7.032s
sys	0m0.000s

可以發現到user time與real time的關係，與執行緒的數量密切相關

參考資料

Makefile 語法簡介
 使用gnuplot科學作圖
 Visual C++ OpenMP doc
OpenMP變數的平行化
 clock_gettime
knowing the current time