作業二 Raytracing 開發紀錄

工具學習
程式分析
改善方式
實做結果
問題討論

工具學習

gprof
gnuplot
- Gnuplot (Part I)
- 製作文件工具

程式分析

原本的 Execution time of raytracing() 為 5s 左右
使用 -Ofast 最佳化的結果，以超越這個數值為目標。
gprof分析顯示耗時最多的依序為
1. subtract_vector
2. dot_product
3. rayRectangularIntersection
4. add_vector
在raytracing.c : raytracing()中發現有巢狀for迴圈，或許可以使用平行運算加快速度。

改善方式

loop_unrolling
- 每次的for loop會進行一次size的判斷，這樣簡化了程式的內容，但在特定的loop中，執行的次數是固定的。因此我們將for loop的內容展開，這樣可以減少程式執行時，判斷式的損耗，減少組合語言中 branch的數量，藉由這樣增進程式效能。
Force Inline
- 程式中有 static inline的關鍵字，但gcc在 -O0 沒有最佳化的情況下，會忽視 inline。因此在function前加上 attribute((always_inline)) 會提醒編譯器執行inline。
- 參考資料
  - attribute的使用
  - Force Inline












//Force Inline
__attribute__((always_inline)) void subtract_vector(const double *a, const double *b, double *out)
{
// loop unrolling
    out[0]=a[0]-b[0];
    out[1]=a[1]-b[1];
    out[2]=a[2]-b[2];
/*
    for (int i = 0; i < 3; i++)
        out[i] = a[i] - b[i];
*/
}

OpenMP
- 使用OpenMP可以將程式中的區段或是迴圈，讓多核心系統進行平行處理。在迴圈中，使用的條件為：「迴圈內部的程式，可獨立運作。」就是迴圈內部的程式，彼此不能有相依性，否則無法使用OpenMP。
- 以這次的範例程式來說，在raytracing.c : raytracing()，可以發現有三個巢狀迴圈，分別以 height,width,SAMPLE為迴圈的執行數。在for前一行加上
  #pragma omp for即可告訴編譯器，使用OpenMP編譯。





























    #pragma omp parallel for schedule(dynamic) collapse(2) num_threads(64) private(stk), private(d),private(object_color) 
    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;
            }
        }
    }

- 參考資料

實做結果

loop_unrolling
Force Inline + loop_unrolling

執行5次的平均時間
OpenMP
- 在原有的程式碼下，直接插入OpenMP指令，並沒有使效能有效提昇，反而會降低許多。
- 在gprof中，可以看到各個function被呼叫的次數減少，推測是因為多核心分散處理的結果。
OpenMP + Force Inline + loop_unrolling
- 而在優化後的程式碼中，插入OpenMP指令，效能顯著的提昇。
- gprof，可以看到比force_inline呼叫的次數少了許多。

問題討論

不太能確定為何原本的版本加上OpenMP會增加接近一倍的時間。