# 2017q1 Homework1 (raytracing) contributed by <`Weinux`> ###### tags: `sysprog2017` `w1` `raytracing` `Weinux` ### Reviewed by `xdennisx` - 沒有分析平行化之後的效能，例如：OpenMP、pthread - Git commit message 應該要完整一點，包刮實作方式、實作之後的影響等等 - commit [f0d4184af071ea9d4c9b850cca61da8b59d02394](https://github.com/Weinux/raytracing/commit/f0d4184af071ea9d4c9b850cca61da8b59d02394) 應該確認程式無誤再 commit - commit [c69cafa2208b9d08bfe7b2005d8a377cff2c37dc](https://github.com/Weinux/raytracing/commit/c69cafa2208b9d08bfe7b2005d8a377cff2c37dc) 應避免錯字 `btought` ## 開發環境 * OS：Lubuntu 16.04 LTS * Linux 系統版本: 4.4.0-63-generic * Architecture: x86_64 * CPU 作業模式： 32-bit, 64-bit * Byte Order: Little Endian * CPU: Intel(R) Core(TM) i5-2410M CPU @ 2.30GHz * Model name: Intel(R) Core(TM) i5-2410M CPU @ 2.30GHz * Memory: 6GB (5870MB) * Cache: * L1d cache: 32K * L1i cache: 32K * L2 cache: 256K * L3 cache: 3072K ## Raytracing - 直接編譯程式 `$ make` ```text = cc -std=gnu99 -Wall -O0 -g -c -o objects.o objects.c cc -std=gnu99 -Wall -O0 -g -c -o raytracing.o raytracing.c cc -std=gnu99 -Wall -O0 -g -c -o main.o main.c cc -o raytracing objects.o raytracing.o main.o -lm ``` `$ ./raytracing` ```text= # Rendering scene Done! Execution time of raytracing() : 3.854475 sec ``` ![](https://i.imgur.com/9ti7uWC.png) 使用 gprof 觀察 - 必須在 gcc option 中加入 `-pg` 才能生成可以被 `grof` 觀察的數據 - 在 Makefile 中程式碼, 可以看到只要設定 `PROFILE=1` 就可以在編譯時加入 `-pg` 指令 ```clike=17 ifeq ($(strip $(PROFILE)),1) PROF_FLAGS = -pg CFLAGS += $(PROF_FLAGS) LDFLAGS += $(PROF_FLAGS) endif ``` ``` $ make clean $ make PROFILE=1 ``` 可以看到 ``` cc -std=gnu99 -Wall -O0 -g -pg -c -o objects.o objects.c cc -std=gnu99 -Wall -O0 -g -pg -c -o raytracing.o raytracing.c cc -std=gnu99 -Wall -O0 -g -pg -c -o main.o main.c cc -o raytracing objects.o raytracing.o main.o -lm -pg ``` 接著再執行程式並且使用 gprof 指令觀察 `$ ./raytracing` ``` # Rendering scene Done! Execution time of raytracing() : 8.033182 sec ``` `$ gprof ./raytracing | less` ``` Each sample counts as 0.01 seconds. % cumulative self self total time seconds seconds calls s/call s/call name 18.28 0.55 0.55 56956357 0.00 0.00 subtract_vector 16.62 1.05 0.50 69646433 0.00 0.00 dot_product 11.97 1.41 0.36 10598450 0.00 0.00 normalize 11.63 1.76 0.35 31410180 0.00 0.00 multiply_vector 9.14 2.04 0.28 13861875 0.00 0.00 rayRectangularIntersection 6.48 2.23 0.20 17836094 0.00 0.00 add_vector 5.98 2.41 0.18 4620625 0.00 0.00 ray_hit_object 5.15 2.57 0.16 13861875 0.00 0.00 raySphereIntersection 3.99 2.69 0.12 17821809 0.00 0.00 cross_product 2.33 2.76 0.07 1 0.07 3.01 raytracing 1.99 2.82 0.06 1048576 0.00 0.00 ray_color 1.33 2.86 0.04 1048576 0.00 0.00 rayConstruction 1.00 2.89 0.03 4221152 0.00 0.00 multiply_vectors 1.00 2.92 0.03 2520791 0.00 0.00 idx_stack_top 1.00 2.95 0.03 2110576 0.00 0.00 compute_specular_diffuse 1.00 2.98 0.03 1241598 0.00 0.00 reflection 0.66 3.00 0.02 1241598 0.00 0.00 refraction 0.50 3.01 0.02 3838091 0.00 0.00 length 0.00 3.01 0.00 2558386 0.00 0.00 idx_stack_empty ``` - 透過 gprof 可以發現在 raytracing 程式 **subtract_vector, dot_product, normalize, multiply_vector** 佔了大部分的執行時間 接著透過 gprof2dot 來將 gprof 相關資訊視覺化, 使用 gprof2dot 前需要先作下列的安裝才可以使用, 參考 [hugikun999的共筆](https://hackmd.io/s/HyHhgcv6#) ``` $sudo apt-get 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/9XpSyJT.png) ## Loop unrolling 在原本的 math-toolkit 中的迴圈部份全部展開減少 branch 與 branch miss 對程式效能的影響 ```text= # Rendering scene Done! Execution time of raytracing() : 2.664209 sec ``` ``` Each sample counts as 0.01 seconds. % cumulative self self total time seconds seconds calls s/call s/call name 20.21 0.40 0.40 69646433 0.00 0.00 dot_product 12.38 0.65 0.25 13861875 0.00 0.00 rayRectangularIntersection 10.11 0.85 0.20 10598450 0.00 0.00 normalize 9.60 1.04 0.19 56956357 0.00 0.00 subtract_vector 8.09 1.20 0.16 31410180 0.00 0.00 multiply_vector 8.09 1.36 0.16 4620625 0.00 0.00 ray_hit_object 5.31 1.46 0.11 17836094 0.00 0.00 add_vector 5.31 1.57 0.11 17821809 0.00 0.00 cross_product 4.80 1.66 0.10 13861875 0.00 0.00 raySphereIntersection 4.55 1.75 0.09 1048576 0.00 0.00 ray_color 3.03 1.81 0.06 1048576 0.00 0.00 rayConstruction 2.02 1.85 0.04 2110576 0.00 0.00 localColor 2.02 1.89 0.04 1 0.04 1.98 raytracing 1.52 1.92 0.03 4221152 0.00 0.00 multiply_vectors 1.01 1.94 0.02 3838091 0.00 0.00 length 0.51 1.95 0.01 2558386 0.00 0.00 idx_stack_empty 0.51 1.96 0.01 2110576 0.00 0.00 compute_specular_diffuse 0.51 1.97 0.01 1241598 0.00 0.00 reflection 0.51 1.98 0.01 1241598 0.00 0.00 refraction 0.00 1.98 0.00 2520791 0.00 0.00 idx_stack_top ``` - 所得到的結果比起一開始的執行時間整整快了 1.2 sec - 程式中 **subtract_vector, dot_product, normalize, multiply_vector** 執行時間也都有下降』 ## Force inline - 在 gcc 要 force inline function 需要加入`__attribute__((always_inline))` 可以強制 gcc 在最佳化沒有開啟 `-O0` 時 inline - [How do i force gcc to inline a fuction](http://stackoverflow.com/questions/8381293/how-do-i-force-gcc-to-inline-a-function) ```clike=26 static inline __attribute__((always_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]; } ``` ``` # Rendering scene Done! Execution time of raytracing() : 2.435457 sec ``` - Force inline 所得到的結果比起 loop unrolling 的執行時間又再快了 0.2 sec ## 參考資料