Try   HackMD

2017q1 Homework1 (raytracing)

contributed by <csielee>

Reviewed by yanang

  • 關於 thread vs openmp，可以參考 去年的共筆整理 最後一段所展示的 thread 與 openmp 在四核處理器下共同使用將會競爭使用核心，導致效能降低。
THREAD OPENMP
# Rendering scene
Done!
Execution time of raytracing() : 1.791940 sec

POSIX THREAD
# Rendering scene
Done!
Execution time of raytracing() : 1.636069 sec

OPENMP
# Rendering scene
Done!
Execution time of raytracing() : 1.656069 sec
  • 另外將各種方式 ( LOOP-UNROOLING 、Force Inline、MACRO、Remove Assert ) 搭配 thread 和 openmp ，所得出的最佳結果。

  • 以及最後將 -Ofast 也加入使用的最佳化結果。
# Rendering scene
Done!
Execution time of raytracing() : 0.268195 sec

開發環境

OS: ubuntu 16.04 LTS
Architecture: x86_64
CPU 作業模式： 32-bit, 64-bit
Byte Order: Little Endian
CPU(s): 4
Model name: Intel® Core™ i5-5200U CPU @ 2.20GHz
CPU MHz： 2500.109
CPU max MHz: 2700.0000
CPU min MHz: 500.0000
L1d 快取： 32K, 8-way Set-associative
L1i 快取： 32K, 8-way Set-associative
L2 快取： 256K, 8-way Set-associative
L3 快取： 3072K, 12-way Set-associative
記憶體： 8G

嘗試運作未優化版本

./raytracing 
# Rendering scene
Done!
Execution time of raytracing() : 6.660908 sec

正確得到圖形

利用gprof找出效能瓶頸

在編譯和連結時加上 -pg ，可以產生 gmon.out 讓gprof可以分析
執行 $gprof -b raytracing gmon.out
可以得到很多分析資料

  %   cumulative   self              self     total           
 time   seconds   seconds    calls   s/call   s/call  name    
 23.44      0.52     0.52 69646433     0.00     0.00  dot_product
 20.73      0.98     0.46 56956357     0.00     0.00  subtract_vector
 11.49      1.24     0.26 31410180     0.00     0.00  multiply_vector
  7.21      1.40     0.16  4620625     0.00     0.00  ray_hit_object
  6.76      1.55     0.15 17836094     0.00     0.00  add_vector
  6.76      1.70     0.15 13861875     0.00     0.00  raySphereIntersection
  6.31      1.84     0.14 17821809     0.00     0.00  cross_product
  4.51      1.94     0.10 10598450     0.00     0.00  normalize
  4.51      2.04     0.10  1048576     0.00     0.00  ray_color
  3.61      2.12     0.08 13861875     0.00     0.00  rayRectangularIntersection
  1.80      2.16     0.04        1     0.04     2.22  raytracing
  1.13      2.18     0.03  4221152     0.00     0.00  multiply_vectors

從上面的分析得知，花費時間最多的是 dot_product 這個函數
佔據了23.44%的時間
subtract_vector multiply_vector 也花費不少
從這些地方下手，預期能夠有效改善效能

利用gprof2dot讓graphviz產生圖

參考hugikun999共筆得知，可以利用這些工具得到函數呼叫的路徑圖

先安裝

$sudo apt install python python-pip
$sudo pip install --upgrade pip
$sudo pip install gprof2dot

後執行

$gprof ./raytracing | gprof2dot | dot -T png -o output.png

就能得到

真是太強大了，不禁覺得佩服

使用loop unrolling

藉由gprof，發現在 math-toolkit.h 的很多熱點函數都有簡單的 for loop 存在
藉由展開迴圈可以減少 branch 執行預測上的損失，以及還要多讀取一個變數的記憶體時間

所謂的 空間換取時間

static inline
void add_vector(const double *a, const double *b, double *out)
{
	out[0] = a[0] + b[0];
	out[1] = a[1] + b[1];
	out[2] = a[2] + b[2];
}

static inline
void subtract_vector(const double *a, const double *b, double *out)
{
	out[0] = a[0] - b[0];
	out[1] = a[1] - b[1];
	out[2] = a[2] - b[2];
}

static inline
void multiply_vectors(const double *a, const double *b, double *out)
{
	out[0] = a[0] * b[0];
	out[1] = a[1] * b[1];
	out[2] = a[2] * b[2];
}

static inline
void multiply_vector(const double *a, double b, double *out)
{
	out[0] = a[0] * b;
	out[1] = a[1] * b;
	out[2] = a[2] * b;
}

static inline
double dot_product(const double *v1, const double *v2)
{
    double dp = 0.0;
	dp += v1[0]*v2[0] + v1[1]*v2[1] + v1[2]*v2[2];
    return dp;
}

展開後嘗試執行，時間縮短到 5.705232 sec

# Rendering scene
Done!
Execution time of raytracing() : 5.705232 sec

使用POSIX thread

參考yanang共筆
在不更動 main.c 的情況，並利用前置處理加入Pthread版本

編譯的失誤

使用 $make pthread 編譯

cc -DIMPL="\"raytracing_pthread.h\"" -o raytracing_pthread objects.o raytracing.o main.o -lm -lpthread

執行後的時間

./raytracing_pthread 
# Rendering scene
Done!
Execution time of raytracing() : 5.199946 sec

這裡有很大的問題，是編譯的方法錯了
因為我是用 前置處理器去加入pthread的版本，所以編譯的時候如果拿已經轉成 .o 檔的檔案來linker是不會有我寫的code進去
原因在下面的圖

Created with Raphaël 2.2.0gcc編譯 .c 檔前置處理器(preprocesser)處理 # 符號編譯器(compiler)產生 .s 檔組譯器(assembler)產生 .o 檔連結器(linker)連結 .o 檔 生成 執行檔得到執行檔

因此如果我利用前置處理器去判斷是否要使用pthread版本
必須重新編譯 .c 檔產生 .o 檔
不能直接拿舊 .o 檔直接編譯

重新寫過之後

使用 $make pthread 編譯

cc -DPTHREAD=1 -o raytracing_pthread objects.o raytracing.c main.o -lm -lpthread

此時出現一些pthread使用上的bug
我才確定我真的有在編譯新的pthread版本
de掉這些bug後重新執行

./raytracing_pthread 
# Rendering scene
Done!
Execution time of raytracing() : 0.941404 sec

天阿！這才是pthread的威力阿

使用openMP

參考ryanwang522共筆
加入openMP

編譯的錯誤

使用 $make openmp 編譯

cc -DOMP=1 -o raytracing_openmp objects.o raytracing.o main.o -lm -fopenmp

執行後的時間

./raytracing_openmp 
# Rendering scene
Done!
Execution time of raytracing() : 5.023935 sec

也是編譯上的問題，因此時間才沒有變化很大

重新寫過

重新編譯並執行

make openmp 
cc -DOMP=1 -o raytracing_openmp objects.o main.o raytracing.c -lm -fopenmp
./raytracing_openmp 
# Rendering scene
Done!
Execution time of raytracing() : 1.045033 sec

時間上感覺比pthread來的久
因為openMP預設排程模式是 auto 的原因
把openMP的排程設定調整一下，用成一樣的模式 schedule(static, 1)
因為我們只有平行最外層的for，因此設定成1就可以跟pthread是一樣的分工模式
時間也可以差不多

./raytracing_openmp 
# Rendering scene
Done!
Execution time of raytracing() : 0.940617 sec

太棒惹，輕鬆完成雙版本

openMP V.S. Pthread

看到很多共筆都將平行化使用在raytracing的函數當中的for迴圈
就是將圖分程不同區塊讓不同執行緒運算，讓整張圖能夠平行且並行的進行預算

因為是使用執行緒實現並行的運算，所以可以有效能上的增進
但令我好奇的是，有 openMP 跟 Pthread 兩套API
究竟是哪一個好，或是各有優缺?

影響的可能性如下

  • 執行處理器的核心數
  • 能夠創建的執行緒數量
  • 呼叫API跟使用編譯指示是否有差別
  • 執行緒的排程

而不變的條件如下

  • 每個pixel運算個別獨立
  • 需使用私有變數
  • 需使用共同變數

兩者變數的設定使用

在 Pthread 的使用上，因為只能夠傳入一個指標
因此如果有多個變數要傳入就需要另外設計一個結構去儲存
而且要使用共同變數就要宣告全域變數

而 openMP 的使用上，只有私有變數需要進行設定
其他已經宣告的變數都會變成全域變數

個人評論

我覺得openMP在這部份非常的好用
因為不用額外多加很多變數的宣告跟賦值
就能完成變數的設定東霖

呼叫API跟使用編譯指示

要使用 Pthread 需要去呼叫其API
而如果該台裝置沒有支援的函式庫就會無法進行編譯
並且使用執行緒需要額外寫函數給執行緒呼叫

openMP 則是利用 #pragma 的編譯指示
指示編譯器在編譯的時候需要額外做些事情
藉由這個如果編譯器可以了解要做的事情，就會去執行(幫你寫好code放進去)
如果不了解也不會失敗，頂多沒有執行

個人評論

老實說，我在寫openMP版本花不到幾分鐘
但Pthread卻寫了一陣子還出現bug
我認為如果沒有需要特別操作執行緒的行為
其實openMP就很好用
而且時間就是金錢，又快又有效東霖

執行緒的排程

在 Pthread 需要自己去設計執行緒的排程
並考慮實作方法

而 openMP 則不需要，可以利用schedule去設定排程

個人評論

有設計好的排程當然好
但也未必就不用思考本身平行化的排程選擇
在openMP預設的排程模式(auto)
發揮的效能比設計過的排程(cyclic)還要差
這邊就顯示出不管工具如何
開發者都要足夠了解要優化效能的特性東霖

小小總結

用個比喻來結束這個總結

Pthread就像沒組好的機器，要自己組裝
openMP就像組好的機器，只要會用就好

參考資料

hugikun999共筆
高性能计算的线程模型：Pthreads 还是 OpenMP？
yangang共筆
ryanwang522共筆

Last changed by 
 
李東霖
0
713
Published on HackMD