2017q1 Homework1 (raytracing)

# 2017q1 Homework1 (raytracing) contributed by <`csielee`> ### Reviewed by `yanang` * 關於 thread vs openmp，可以參考 [去年的共筆整理](https://embedded2016.hackpad.com/ep/pad/static/f5CCUGMQ4Kp) 最後一段所展示的 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 ，所得出的最佳結果。 ![](https://hackpad-attachments.s3.amazonaws.com/embedded2016.hackpad.com_f5CCUGMQ4Kp_p.575390_1462192518484_plot.png) * 以及最後將 -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(R) Core(TM) 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 ``` 正確得到圖形 ![](https://i.imgur.com/bjPMzsB.png) ## 利用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共筆](https://hackmd.io/s/HyHhgcv6#)得知，可以利用這些工具得到函數呼叫的路徑圖先安裝 ``` $sudo apt install python python-pip $sudo pip install --upgrade pip $sudo pip install gprof2dot ``` 後執行 ``` $gprof ./raytracing | gprof2dot | dot -T png -o output.png ``` 就能得到 ![](https://i.imgur.com/TiV6DXt.png) 真是太強大了，不禁覺得佩服 ## 使用loop unrolling 藉由gprof，發現在 `math-toolkit.h` 的很多熱點函數都有簡單的 for loop 存在藉由展開迴圈可以減少 branch 執行預測上的損失，以及還要多讀取一個變數的記憶體時間所謂的 **空間換取時間** ```clike 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共筆](https://hackmd.io/s/H1caWe7cx#) 在不更動 `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 ``` :::danger 這裡有很大的問題，是編譯的方法錯了因為我是用前置處理器去加入pthread的版本，所以編譯的時候如果拿已經轉成 .o 檔的檔案來linker是不會有我寫的code進去原因在下面的圖 ::: ```flow st=>start: gcc編譯 .c 檔 e=>end: 得到執行檔 h=>operation: 標頭檔(.h) op1=>operation: 前置處理器(preprocesser) 處理 # 符號 op2=>operation: 編譯器(compiler) 產生 .s 檔 op3=>operation: 組譯器(assembler) 產生 .o 檔 op4=>operation: 連結器(linker) 連結 .o 檔生成執行檔 st->op1->op2->op3->op4->e ``` 因此如果我利用前置處理器去判斷是否要使用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共筆](https://hackmd.io/s/BJsz9RZqx#) 加入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 ``` :::danger 也是編譯上的問題，因此時間才沒有變化很大 ::: ### 重新寫過重新編譯並執行 ``` 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在這部份非常的好用 > 因為不用額外多加很多變數的宣告跟賦值 > 就能完成變數的設定[name=東霖] ### 呼叫API跟使用編譯指示要使用 **Pthread** 需要去呼叫其API 而如果該台裝置沒有支援的函式庫就會無法進行編譯並且使用執行緒需要額外寫函數給執行緒呼叫 **openMP** 則是利用 `#pragma` 的編譯指示指示編譯器在編譯的時候需要額外做些事情藉由這個如果編譯器可以了解要做的事情，就會去執行(幫你寫好code放進去) 如果不了解也不會失敗，頂多沒有執行 **個人評論** > 老實說，我在寫openMP版本花不到幾分鐘 > 但Pthread卻寫了一陣子還出現bug > 我認為如果沒有需要特別操作執行緒的行為 > 其實openMP就很好用 > 而且時間就是金錢，又快又有效[name=東霖] ### 執行緒的排程在 **Pthread** 需要自己去設計執行緒的排程並考慮實作方法而 **openMP** 則不需要，可以利用schedule去設定排程 **個人評論** > 有設計好的排程當然好 > 但也未必就不用思考本身平行化的排程選擇 > 在openMP預設的排程模式(auto) > 發揮的效能比設計過的排程(cyclic)還要差 > 這邊就顯示出不管工具如何 > 開發者都要足夠了解要優化效能的特性[name=東霖] ### 小小總結用個比喻來結束這個總結 :::success Pthread就像沒組好的機器，要自己組裝 openMP就像組好的機器，只要會用就好 ::: ## 參考資料 [hugikun999共筆](https://hackmd.io/s/HyHhgcv6#) [高性能计算的线程模型：Pthreads 还是 OpenMP？](https://software.intel.com/zh-cn/articles/threading-models-for-high-performance-computing-pthreads-or-openmp) [yangang共筆](https://hackmd.io/s/H1caWe7cx#) [ryanwang522共筆](https://hackmd.io/s/BJsz9RZqx#)