# 2017q1 Homework1 (raytracing) contributed by <`ierosodin`> [github](https://github.com/ierosodin/raytracing) ### Reviewed by `janetwei` * 可以證明跟解釋爲何執行緒數量的結果差距 * 用 SIMD 來加速整個資料的處理 ## 開發環境 作業系統 : elementary OS loki `$ lscpu` Architecture: x86_64 CPU op-mode(s): 32-bit, 64-bit Byte Order: Little Endian CPU(s): 12 On-line CPU(s) list: 0-11 Thread(s) per core: 2 Core(s) per socket: 6 Socket(s): 1 NUMA node(s): 1 Vendor ID: GenuineIntel CPU family: 6 Model: 45 Model name: Genuine Intel(R) CPU @ 3.30GHz Stepping: 5 CPU MHz: 2101.558 CPU max MHz: 3900.0000 CPU min MHz: 1200.0000 BogoMIPS: 6600.00 Virtualization: VT-x L1d cache: 32K L1i cache: 32K L2 cache: 256K L3 cache: 15360K NUMA node0 CPU(s): 0-11 ## 軟體安裝 ``` $ sudo apt-get update $ sudo apt-get install graphviz $ sudo apt-get install imagemagick ``` 未優化前執行時間： ``` Execution time of raytracing() : 2.961364 sec ``` ## 使用gprof分析 ``` $ make PROFILE=1 $ ./raytracing ``` 使用 gprof 時, 執行時間會變長 ( gprof 使 gcc 在每個函数中都加入了一個 mcount ，也就是說每個函數都會調用 mcount , 增加執行時間) `Execution time of raytracing() : 5.704768 sec` ## Using gprof2dot gprof2dot 能將 gprof 或 perf 的分析結果轉成 dot 格式，裡面會描述各個節點間的關係 ``` $ git clone https://github.com/jrfonseca/gprof2dot $ gprof raytracing| ../gprof2dot/gprof2dot.py | dot -Tpng -o dot.png ``` ![](https://i.imgur.com/vii3IPj.png) ### 開始分析 `$ gprof -b raytracing gmon.out | less` ``` Flat profile: Each sample counts as 0.01 seconds. % cumulative self self total time seconds seconds calls s/call s/call name 22.82 0.52 0.52 69646433 0.00 0.00 dot_product 19.75 0.97 0.45 56956357 0.00 0.00 subtract_vector 10.97 1.22 0.25 10598450 0.00 0.00 normalize 9.66 1.44 0.22 13861875 0.00 0.00 rayRectangularIntersection 9.44 1.66 0.22 31410180 0.00 0.00 multiply_vector 7.02 1.82 0.16 13861875 0.00 0.00 raySphereIntersection 4.39 1.92 0.10 17821809 0.00 0.00 cross_product 3.73 2.00 0.09 17836094 0.00 0.00 add_vector 2.19 2.05 0.05 4620625 0.00 0.00 ray_hit_object 2.19 2.10 0.05 1048576 0.00 0.00 ray_color 1.54 2.14 0.04 4221152 0.00 0.00 multiply_vectors 1.32 2.17 0.03 1 0.03 2.27 raytracing 1.10 2.19 0.03 2520791 0.00 0.00 idx_stack_top 0.88 2.21 0.02 1241598 0.00 0.00 protect_color_overflow 0.88 2.23 0.02 1048576 0.00 0.00 rayConstruction 0.66 2.25 0.02 3838091 0.00 0.00 length 0.44 2.26 0.01 2110576 0.00 0.00 compute_specular_diffuse 0.44 2.27 0.01 2110576 0.00 0.00 localColor 0.44 2.28 0.01 1 0.01 0.01 delete_sphere_list 0.22 2.28 0.01 37595 0.00 0.00 idx_stack_pop 0.00 2.28 0.00 2558386 0.00 0.00 idx_stack_empty 0.00 2.28 0.00 1241598 0.00 0.00 reflection 0.00 2.28 0.00 1241598 0.00 0.00 refraction 0.00 2.28 0.00 1204003 0.00 0.00 idx_stack_push 0.00 2.28 0.00 1048576 0.00 0.00 idx_stack_init 0.00 2.28 0.00 113297 0.00 0.00 fresnel 0.00 2.28 0.00 3 0.00 0.00 append_rectangular 0.00 2.28 0.00 3 0.00 0.00 append_sphere ``` 從 gprof 調用表可以發現， dot_product 與 subtract_vector 被呼叫次數最多, 嘗試針對這兩項進行優化。 * baseline.ppm ![](https://i.imgur.com/Ht1ljuU.jpg) ## 優化 先試試 compiler 的優化能力吧！(目標超越它) ![](https://i.imgur.com/qDdEZhV.png) ### loop unrolling 可以發現， math-toolkit.h 是一個小迴圈，試著將這些 for 迴圈打開： ```clike= 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] * v1[2]; return dp; } ``` 再用 gprof 檢查一次，數學運算的部份所花費的時間下降了！ ``` Each sample counts as 0.01 seconds. % cumulative self self total time seconds seconds calls s/call s/call name 16.90 0.25 0.25 10598450 0.00 0.00 normalize 12.85 0.44 0.19 69646433 0.00 0.00 dot_product 10.82 0.60 0.16 13861875 0.00 0.00 rayRectangularIntersection 10.48 0.76 0.16 56956357 0.00 0.00 subtract_vector 10.14 0.91 0.15 4620625 0.00 0.00 ray_hit_object ``` * gprof2dot ![](https://i.imgur.com/phyiuzm.png) 執行時間： `Execution time of raytracing() : 2.252323 sec` ![](https://i.imgur.com/IKGEKh8.png) ### force inline inline function 只能建議編譯器，也就是說建議並不一定會被採納，可以嘗試使用 `__attribute__((always_inline))` 執行時間： `Execution time of raytracing() : 1.979259 sec` ![](https://i.imgur.com/zbtPimO.png) ### 平行化 #### OpenMP 發現rayRectangularIntersection與raySphereIntersection對程式效能有影響, 嘗試對raytracing.c進行優化。 ``` #pragma omp parallel default (shared) private(stk, d, object_color) num_threads(omp_get_max_threads()) #pragma omp for schedule(static) ``` 使用 OpenMP 時要注意變數的性質，如果是每個 thread 都各自擁有的變數，須設為 privated。 可以用 diff 來檢查結果( out.ppm )是否正確 `$ diff baseline.ppm out.ppm` * out.ppm ![](https://i.imgur.com/bAasXZ3.jpg) 使用 OpenMP 對效能有很明顯的提升 `Execution time of raytracing() : 0.398234 sec` * gprof2dot ![](https://i.imgur.com/iKnLhe2.png) ![](https://i.imgur.com/rVNmCSd.png) >光是使用 OpenMP 就超越 -Ofast 拉~~ [name=ierosodin][color=green] #### pThreads 另一種平行化的方式，可以決定將某個 function 交給 thread 去做。 * main.c ++宣告 thread id ，並分配記憶體++ ```clike pthread_t *id = (pthread_t *) malloc(THREADNUM * sizeof(pthread_t)); ``` ++宣告一個指標型態的陣列，使每一個 id 都有一個指標型態的參數( ptr[i] ),用來傳入 function ++ ```clike rays **ptr = (rays **) malloc(THREADNUM * sizeof(rays *)); ``` ++建立 thread ，參數分別是： （ thread id ， 屬性( NULL )， 要平行化的 function ， 傳入的參數）++ ```clike pthread_create(&id[i], NULL, (void *) &raytracing, (void *) ptr[i]); ``` ++用來等待該 id 的 thread 結束，第二個參數用來儲存回傳值++ ```clike pthread_join(id[i], NULL); ``` * raytracing.c ++放在 raytracing() 的最後，表示該 function 結束後， thread 關閉++ ```clike pthread_exit(0); ``` 在 THREAD_NUM = 12 的情況下，執行時間縮短到 0.315882 秒！ * gporf2dot ![](https://i.imgur.com/gS78lqZ.png) ![](https://i.imgur.com/KWaBDai.png) * 不同 THREAD_NUM 對效能的影響 ![](https://i.imgur.com/2yZlduD.png) 可以發現無止境的增加 THREAD_NUM 並不會對效能有明顯的影響，甚至會增加執行時間。 #### threadpool threadpool 不同於一般的 thread ，是將所有的 tasks 丟入 pool 中，而閒置的 thread 則從這個 pool 中取出可以執行的 task ，這樣可以避免不同 thread 之間工作量不平均或是 thread 執行速度不一而造成效能的損耗。 參考 [mergesort-concurrent](https://github.com/sysprog21/mergesort-concurrent) 中對 threadpool 的應用，實作在 raytracing 中，從效能比較圖可以發現， threadpool 比一般的 pthread 又更來得快速。 ![](https://i.imgur.com/IurkkBR.png) * 不同 THREAD_NUM 對效能的影響 | thread number | execution time | |:------:|:------:| |1|1.769772s| |2|0.867196s| |4|0.468847s| |8|0.302147s| |12|0.257031s| |16|0.258006s| |64|0.261613s| |128|0.262480s| |256|0.266355s| |512|0.282510s| ![](https://i.imgur.com/I2WDiAT.png) ### OpenCL https://www.fixstars.com/en/opencl/book/OpenCLProgrammingBook/opencl-c/ http://www.kimicat.com/opencl-1/opencl-jiao-xue-yi https://github.com/smistad/OpenCL-Getting-Started ### GCC optimization 最後，再用一次 -Ofast 吧~（不過要檢查最後出來的 out.ppm 是否正確，優化 pthread 可能會產生錯誤） ## 參考資料 [gprof2dot github](https://github.com/jrfonseca/gprof2dot) [pThreads for Raytracing](https://embedded2016.hackpad.com/ep/pad/static/wOu40KzMaIP) [Enhance raytracing program](https://embedded2016.hackpad.com/ep/pad/static/f5CCUGMQ4Kp)
Last changed by  
 
許耕福
551
Published on HackMD