# 2017q1 Homework1 (raytracing) contributed by <`yangyang95`> ###### tags: `sysprog2017` `HW1` `yangyang95` 電腦規格看 [這裡](https://hackmd.io/s/HJ2c_XYKx) github page 看 [這裡](https://github.com/yangyang95/raytracing) ### Reviewed by <`claaaaassic`> * commit [f1f5dc634704b34c8bfaa3a288e9fb530a19fb69](https://github.com/yangyang95/raytracing/commit/f1f5dc634704b34c8bfaa3a288e9fb530a19fb69) 這個 commit 是錯誤的，可以使用 `git rebase` 修改內容，也可以省下下一個 fix typo 的 commit * OpenMP 可以嘗試使用 schedule 決定多執行緒如何分配迴圈，或許可以更加改善效能 ## 程式編譯 先執行一次測定執行時間 ``` $ ./raytracing (without profiling) # Rendering scene Done! Execution time of raytracing() : 2.923696 sec ``` 再來加入 Proflie ``` $./raytracing (with profiling) # Rendering scene Done! Execution time of raytracing() : 6.183047 sec ``` 這裡值得一提的是，再加入 Profile 的指令 `$ make PROFILE=1` 之前 記得先清理之前編譯完的檔案 `$ make clean` 不然會出現以下訊息 `make: Nothing to be done for 'all'.` 使用 gprof 分析時竟然沒有輸出，見鬼了 = = 嘗試 make clean 重來也不行... 先來查查資料。 ``` $ gprof -b raytracing gmon.out | less Flat profile: Each sample counts as 0.01 seconds. % cumulative self self total time seconds seconds calls Ts/call Ts/call name ^L Call graph granularity: each sample hit covers 2 byte(s) no time propagated index % time self children called name ^L Index by function name (END) ``` 上面的錯誤，經過搜尋還有 [FB 討論區](https://www.facebook.com/groups/system.software2017/permalink/1325126694219363) 版友的幫忙成功找到問題。 為 gcc-6 版本的 bug ，因為 --enabled-default-pie 的選項不同以往，在 gcc-6 是預設開啟，所以導致了沒有結果產生。在 CFLAGS 的部分加入` -no-pie` 參考資料： - [Debian Bug report logs - binutils: GCC 6's --enable-default-pie breaks gprof](https://bugs.debian.org/cgi-bin/bugreport.cgi?bug=854704) - [How to activate gcc 4.7 version?](http://askubuntu.com/questions/269257/how-to-activate-gcc-4-7-version) ## gporf & perf 分析 於是我使用 gcc-6.2.0 跟 -no-pie 的編譯選項重新比較一次結果。 之後的結果也以這邊為比較基準。 ``` $ ./raytracing (without profiling) # Rendering scene Done! Execution time of raytracing() : 2.920220 sec ``` ``` $ ./raytracing (with profiling) # Rendering scene Done! Execution time of raytracing() : 6.788265 sec ``` ``` $ ./raytracing (使用 -O1 編譯器優化) # Rendering scene Done! Execution time of raytracing() : 0.802728 sec ``` gprof 分析結果： ``` Flat profile: Each sample counts as 0.01 seconds. % cumulative self self total time seconds seconds calls s/call s/call name 22.53 0.64 0.64 69646433 0.00 0.00 dot_product 17.56 1.13 0.50 56956357 0.00 0.00 subtract_vector 10.11 1.42 0.29 31410180 0.00 0.00 multiply_vector 8.52 1.66 0.24 13861875 0.00 0.00 rayRectangularIntersection 8.34 1.89 0.24 10598450 0.00 0.00 normalize 6.92 2.09 0.20 13861875 0.00 0.00 raySphereIntersection 5.50 2.24 0.16 17836094 0.00 0.00 add_vector 5.32 2.39 0.15 4620625 0.00 0.00 ray_hit_object 3.19 2.48 0.09 1048576 0.00 0.00 ray_color 3.02 2.57 0.09 17821809 0.00 0.00 cross_product 3.02 2.65 0.09 4221152 0.00 0.00 multiply_vectors 1.60 2.70 0.05 2110576 0.00 0.00 localColor 1.06 2.73 0.03 3838091 0.00 0.00 length 1.06 2.76 0.03 2110576 0.00 0.00 compute_specular_diffuse 0.71 2.78 0.02 2520791 0.00 0.00 idx_stack_top 0.71 2.80 0.02 1 0.02 2.82 raytracing 0.35 2.81 0.01 1241598 0.00 0.00 refraction 0.35 2.82 0.01 113297 0.00 0.00 fresnel 0.18 2.82 0.01 1 0.01 0.01 delete_sphere_list 0.00 2.82 0.00 2558386 0.00 0.00 idx_stack_empty 0.00 2.82 0.00 1241598 0.00 0.00 protect_color_overflow 0.00 2.82 0.00 1241598 0.00 0.00 reflection 0.00 2.82 0.00 1204003 0.00 0.00 idx_stack_push 0.00 2.82 0.00 1048576 0.00 0.00 idx_stack_init 0.00 2.82 0.00 1048576 0.00 0.00 rayConstruction 0.00 2.82 0.00 37595 0.00 0.00 idx_stack_pop 0.00 2.82 0.00 3 0.00 0.00 append_rectangular 0.00 2.82 0.00 3 0.00 0.00 append_sphere 0.00 2.82 0.00 2 0.00 0.00 append_light 0.00 2.82 0.00 1 0.00 0.00 calculateBasisVectors 0.00 2.82 0.00 1 0.00 0.00 delete_light_list 0.00 2.82 0.00 1 0.00 0.00 delete_rectangular_list 0.00 2.82 0.00 1 0.00 0.00 diff_in_second 0.00 2.82 0.00 1 0.00 0.00 write_to_ppm ``` 接下來試試 perf 分析： ``` 64.75% libc-2.24.so [.] _mcount 9.51% raytracing [.] multiply_vector 6.07% raytracing [.] dot_product 3.44% raytracing [.] raytracing 3.01% libc-2.24.so [.] __mcount_internal 3.01% raytracing [.] subtract_vector 2.63% raytracing [.] normalize 2.63% raytracing [.] cross_product 2.63% raytracing [.] multiply_vectors 2.30% raytracing [.] idx_stack_push 0.00% raytracing [.] raySphereIntersection 0.00% [kernel] [k] nmi 0.00% raytracing [.] localColor 0.00% raytracing [.] ray_hit_object 0.00% raytracing [.] add_vector 0.00% [kernel] [k] irq_work_run 0.00% [kernel] [k] native_sched_clock 0.00% [kernel] [k] native_write_msr ``` 在 [這篇](https://hackmd.io/s/ByDd4h8T#) 看到非常詳盡的程式碼分析。 ## 強制 inline 將所有函式加入強制 inline 的 attribute `__attribute__((always_inline))` 來讓編譯器使用 inline 因為使用 inline 只能 **建議** 編譯器將函式的本體在使用到該函式的位置直接展開。 得到的執行時間是： 2.775253 sec ，快了大約 0.145 秒。 ## Loop Unrolling gprof 分析結果中 dot_product 函式佔 22.53% 的總時間，所以是第一個需要改善的函式。 ```C== static inline __attribute__ ((always_inline)) double dot_product(const double *v1, const double *v2) { double dp = 0.0; for (int i = 0; i < 3; i++) dp += v1[i] * v2[i]; return dp; } ``` 嘗試把裡面的 for 迴圈展開，看看效能的變化。 ```C== double dot_product(const double *v1, const double *v2) { return v1[0] * v2[0] + v1[1] * v2[1] + v1[2] * v2[2]; } ``` 得到執行時間： 2.395486 sec ，又快了 0.38 秒。 接下來把向量處理的數學函式都進行 loop unrolling 處理。 得到的執行時間是： 1.838528 sec ，相較沒有 unrolling 的結果，快了大約 1 秒。 重新執行一次 gprof ``` % cumulative self self total time seconds seconds calls s/call s/call name 32.04 0.49 0.49 13861875 0.00 0.00 rayRectangularIntersection 16.02 0.74 0.25 2110576 0.00 0.00 compute_specular_diffuse 15.69 0.98 0.24 13861875 0.00 0.00 raySphereIntersection 12.42 1.17 0.19 1048576 0.00 0.00 ray_color ``` 可以看出佔用多數時間的已經變成 raytracing.c 內的函式。 ## 多執行緒編程 對多執行緒沒有接觸過，因此先來讀點資料。 查看之前的共筆時看到很多 POSIX Thread 跟 OpenMP 的實作，所以來查查兩者有何不同。 - POSIX Thread (PThread)：作為POSIX標準的擴展，Pthreads可以提供使用者層級(User-level)或是核心階層(Kernel-level)的多執行緒庫。為底層的執行緒 API ，需要較熟練的執行緒管理。 - OpenMP：誇平台的多執行緒實現，為上層的執行緒函式庫。 參考資料： - [Pthreads vs. OpenMP](http://stackoverflow.com/questions/3949901/pthreads-vs-openmp) - [多執行緒 (Multi-thread)](https://sls.weco.net/node/21324) - [POSIX執行緒](https://zh.wikipedia.org/wiki/POSIX%E7%BA%BF%E7%A8%8B) ## OpenMP 這裡稍微介紹一下語法，OpenMP 的句子分成三個部分： - Directives (編譯程式定向) : 程式人員加入，用以提示編譯器如何編譯的字句 - Clauses (子句) - Functions (函式) 語法參考： `#pragma omp directive [clause]` 舉例來說： `#pragma omp parallel for` 參考資料： - [Directive - wiki](https://en.wikipedia.org/wiki/Directive_(programming)) - [簡易的程式平行化](https://kheresy.wordpress.com/2006/06/09/%E7%B0%A1%E6%98%93%E7%9A%84%E7%A8%8B%E5%BC%8F%E5%B9%B3%E8%A1%8C%E5%8C%96%E6%96%B9%E6%B3%95%EF%BC%8Dopenmp%EF%BC%88%E4%B8%80%EF%BC%89%E7%B0%A1%E4%BB%8B/) - [OpenMP 函式庫](https://msdn.microsoft.com/en-us/library/tt15eb9t.aspx) 針對 raytracing 函式進行平行化處理，在函式內的 for 迴圈加入 OpenMP 語法： `#pragma omp parallel for num_threads(64) private(stk), private(d),private(object_color)` 以 64 個執行緒，來讓 for 迴圈增加效能。同時需把迴圈內會被改變的變數改為 private 。 得到執行時間： 0.724710 sec ，到這裡已經成功比編譯器優化來的快了。 參考資料： - [ktvexe HackMD 筆記](https://hackmd.io/s/Sygsi6X6) - [jkrvivian HackMD 筆記](https://hackmd.io/s/ByDd4h8T#) - [baimao8437 HackMD 筆記](https://hackmd.io/s/rkVjtkkcl) ## gnuplot 製圖 最後利用 gnuplot 來將結果製圖，試了好久才成功 XD output.txt ： ``` Original 2.920220 inline 2.775253 unrolling 1.838528 -O1 0.802728 OpenMP 0.724710 ``` runtime .gp ： ```C== reset set ylabel 'time(sec)' set style fill solid set title 'perfomance comparison' set term png enhanced font 'Verdana,10' set output 'runtime.png' set key above plot [:][0:3.5]'output.txt' using 2:xticlabel(1) with histogram notitle, \ '' using ($0+0.2):($2+0.1):2 with labels notitle ``` 參考資料： - [gnuplot 語法解說和示範](https://hackmd.io/s/Skwp-alOg) - [Chapter 6. Input, Output](http://dsec.pku.edu.cn/dsectest/dsec_cn/gnuplot/plot-6.html) - [gnuplot demo script](http://gnuplot.sourceforge.net/demo_cvs/datastrings.html) ## 結論： 將各種實作方法繪圖後，可看出比 -O1 編譯器優化來的快速。 ![](https://i.imgur.com/VQ9nF2l.png) 註：後面的優化方法是根據前面方法再進行優化，也就是說 OpenMP 實作也包含 inline, unrolling 提供的優化。
Last changed by  
 
Weng Jerry
367
Published on HackMD