2017q1 Homework2 (raytracing)

contributed by <xdennisx>

Reviewed by PeterTing

• 可以使用 OpenMP 來進行優化，個人覺得它簡單且好用。
• 可以加上圖表分析，使差異能夠一眼看出來。

前置作業

gprof

gprof 可以讓你知道你的程式在哪些部份花了多久的時間，也可以知道
function 之間 call 來 call 去的關係，這些資訊可以讓你發現你的程式中哪些部份執行的速度比你預期中的慢，或是哪些 function call 的次數比想像中的多，這些都是開發者想要增進效能一個很好切入的點

使用前將編譯器加入 -pg，這邊就打 make PROFILE=1 就好

dennis@dennis-X550CC:~/raytracing$ 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.
cc -std=gnu99 -Wall -O0 -g -pg -c -o main.o main.c
cc -o raytracing objects.o raytracing.o main.o -lm -pg 

執行他！

dennis@dennis-X550CC:~/raytracing$ ./raytracing 
# Rendering scene
Done!
Execution time of raytracing() : 7.107704 sec

追蹤他！

$ gprof ./raytracing | less

結果

Flat profile:

Each sample counts as 0.01 seconds.
  %   cumulative   self              self     total           
 time   seconds   seconds    calls   s/call   s/call  name    
 24.21      0.60     0.60 69646433     0.00     0.00  dot_product
 17.35      1.03     0.43 56956357     0.00     0.00  subtract_vector
 11.10      1.31     0.28 31410180     0.00     0.00  multiply_vector
 10.09      1.56     0.25 13861875     0.00     0.00  rayRectangularIntersection
  8.07      1.76     0.20 10598450     0.00     0.00  normalize
  5.65      1.90     0.14 17821809     0.00     0.00  cross_product
  5.25      2.03     0.13 17836094     0.00     0.00  add_vector
  4.03      2.13     0.10 13861875     0.00     0.00  raySphereIntersection
  3.23      2.21     0.08  2110576     0.00     0.00  compute_specular_diffuse
  2.42      2.27     0.06  4620625     0.00     0.00  ray_hit_object
  2.02      2.32     0.05  1048576     0.00     0.00  ray_color
  1.21      2.35     0.03  2110576     0.00     0.00  localColor
  1.01      2.37     0.03  4221152     0.00     0.00  multiply_vectors
  0.81      2.39     0.02  1241598     0.00     0.00  reflection
  0.61      2.41     0.02  2558386     0.00     0.00  idx_stack_empty
  0.61      2.42     0.02  1204003     0.00     0.00  idx_stack_push
  0.40      2.43     0.01  3838091     0.00     0.00  length
  0.40      2.44     0.01  2520791     0.00     0.00  idx_stack_top
:

優化

Loop Unrolling

從上面那張圖發現 dot_product 花的時間最多，所以我們從這裡下手，把裡面的 for loop unrolling

dp = v1[0] * v2[0] + v1[1] * v2[1] + v1[2] * v2[2];

再分析一次

dennis@dennis-X550CC:~/raytracing$ ./raytracing 
# Rendering scene
Done!
Execution time of raytracing() : 6.665834 sec

時間成功下降！

Flat profile:

Each sample counts as 0.01 seconds.
  %   cumulative   self              self     total           
 time   seconds   seconds    calls   s/call   s/call  name    
 21.50      0.49     0.49 56956357     0.00     0.00  subtract_vector
 13.60      0.80     0.31 69646433     0.00     0.00  dot_product
 11.19      1.06     0.26 31410180     0.00     0.00  multiply_vector
  9.22      1.27     0.21 10598450     0.00     0.00  normalize
  8.56      1.46     0.20 13861875     0.00     0.00  rayRectangularIntersection
  8.34      1.65     0.19 17836094     0.00     0.00  add_vector
  7.02      1.81     0.16 17821809     0.00     0.00  cross_product
  6.14      1.95     0.14  4620625     0.00     0.00  ray_hit_object
  5.92      2.09     0.14 13861875     0.00     0.00  raySphereIntersection
  2.41      2.14     0.06  4221152     0.00     0.00  multiply_vectors
  2.19      2.19     0.05  1048576     0.00     0.00  ray_color
  1.32      2.22     0.03  2110576     0.00     0.00  compute_specular_diffuse
  0.66      2.24     0.02  1204003     0.00     0.00  idx_stack_push
  0.44      2.25     0.01  2520791     0.00     0.00  idx_stack_top
  0.44      2.26     0.01    37595     0.00     0.00  idx_stack_pop
  0.44      2.27     0.01        1     0.01     2.28  raytracing
  0.22      2.27     0.01  2558386     0.00     0.00  idx_stack_empty
  0.22      2.28     0.01  1048576     0.00     0.00  rayConstruction
:

dot_product，成功從第一名變第二名

把所有的迴圈 unroll

dennis@dennis-X550CC:~/raytracing$ ./raytracing 
# Rendering scene
Done!
Execution time of raytracing() : 6.454031 sec

inline

inline 對 compiler 來說只是個建議的詞，不是說你打 inline 就一定會 inline，所以如果要強制 inline ，就需要在 inline 後面加上 __attribute__ ((always_inline))

從6.45秒變成2.94秒是否有點誇張

dennis@dennis-X550CC:~/raytracing$ ./raytracing 
# Rendering scene
Done!
Execution time of raytracing() : 2.941980 sec

pthread

把 raytracing() 裡面的 for loop 做平行化處理，這是把一張圖等分成四份，從上到下

    int gap = arg->height / arg->thread_count;
    int end = (arg->thread_index == (arg->thread_count)-1) ? arg->height
              : gap * (arg->thread_index + 1);
    for (int j = arg->thread_index * gap; j < end; j++) {
        for (int i = 0; i < arg->width; i++) {

大概下降 0.5 秒

dennis@dennis-X550CC:~/raytracing$ ./raytracing 
# Rendering scene
Done!
Execution time of raytracing() : 2.465868 sec

有個奇妙的地方，我用一樣多的 thread 去做同樣的事，只是順序不太一樣，結果竟然有差！

for (int j = arg->thread_index; j < arg->height; j+=arg->thread_count)

跟上一種 thread 大概也差了 0.4 秒，這樣前後差了就快 1 秒

dennis@dennis-X550CC:~/raytracing$ ./raytracing 
# Rendering scene
Done!
Execution time of raytracing() : 2.086082 sec

不知道怎樣的順序會是最快的？

Reference

• twzjwang