2016q3 Homework1 (raytracing)

案例分析：raytracing

• 取得原始程式碼、編譯和測試

  ​$ git clone https://github.com/sysprog21/raytracing 
  ​$ cd raytracing
  ​$ make
  ​$ ./raytracing
  

• 透過 convert 這個工具可將 PPM 轉為 PNG 或其他格式，如:

  ​$ convert out.ppm out.png
  

• make check 會檢驗程式碼輸出的圖片是否符合預期，符合的話會得到 “Verified OK!” 字樣

• 使用 gprof 分析 raytracing 生成的數據

  ​$ gprof ./raytracing | less
  

• gprof 分析中呼叫最多次的函式

  ​Flat profile:
  
  ​Each sample counts as 0.01 seconds.
  ​  %   cumulative   self              self     total           
  ​ time   seconds   seconds    calls   s/call   s/call  name    
  ​ 24.89      0.49     0.49 69646433     0.00     0.00  dot_product
  ​ 22.35      0.93     0.44 56956357     0.00     0.00  subtract_vector
  ​  9.65      1.12     0.19 17836094     0.00     0.00  add_vector
  ​  8.63      1.29     0.17 13861875     0.00     0.00  rayRectangularIntersection
  ​  7.11      1.43     0.14 13861875     0.00     0.00  raySphereIntersection
  ​  6.60      1.56     0.13 31410180     0.00     0.00  multiply_vector
  ​  5.59      1.67     0.11 17821809     0.00     0.00  cross_product
  ​  4.06      1.75     0.08 10598450     0.00     0.00  normalize
  

可能的效能改進方向

• POSIX Thread
• OpenMP
• software pipelining
• loop unrolling

原版

• 執行時間：4.759024 sec

優化版 - 展開 for 迴圈

• 修改呼叫最多次的 dot_product()
• 展開 for 迴圈以減少分支指令

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;
}

• 執行時間：4.458128 sec

優化版 - OpenMP

標頭檔：#include <omp.h>
編譯參數：-fopenmp

• 修改raytracing()
• 用 64 個 thread 來跑 for 迴圈

#pragma omp parallel for num_threads(64)
for (int j = 0; j < height; j++) {
    for (int i = 0; i < width; i++) {
        double r = 0, g = 0, b = 0;
	    /* MSAA */
        for (int s = 0; s < SAMPLES; s++) {
            idx_stack_init(&stk);
            rayConstruction(d, u, v, w,
                            i * factor + s / factor,
                            j * factor + s % factor,
                            view,
                            width * factor, height * factor);
            if (ray_color(view->vrp, 0.0, d, &stk, rectangulars, spheres,
                          lights, object_color,
                          MAX_REFLECTION_BOUNCES)) {
                r += object_color[0];
                g += object_color[1];
                b += object_color[2];
            } else {
                r += background_color[0];
                g += background_color[1];
                b += background_color[2];
            }
            pixels[((i + (j * width)) * 3) + 0] = r * 255 / SAMPLES;
            pixels[((i + (j * width)) * 3) + 1] = g * 255 / SAMPLES;
            pixels[((i + (j * width)) * 3) + 2] = b * 255 / SAMPLES;
        }
    }
}

• 執行時間：3.842497 sec
• 問題：加上 OpenMP 後，執行了很多次，但每次的執行時間都差很多，有時候比原版快，有時候卻比原本更慢