# 作業二 Raytracing 開發紀錄
* 工具學習
* 程式分析
* 改善方式
* 實做結果
* 問題討論
---
## 工具學習
* [gprof](http://os.51cto.com/art/200703/41426_1.htm)
* gnuplot
* [Gnuplot (Part I)](http://gtchen.pixnet.net/blog/post/5873441-gnuplot-(part-i))
* [製作文件工具](http://www.study-area.org/cyril/opentools/opentools/x441.html)
---
## 程式分析
* 原本的 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的使用](http://huenlil.pixnet.net/blog/post/26078382-%5B%E8%BD%89%5Dgnu-c-__attribute__-%E6%A9%9F%E5%88%B6%E7%B0%A1%E4%BB%8B)
* [Force Inline](http://stackoverflow.com/questions/13228326/force-inline-function-in-other-translation-unit)

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

* * 參考資料
* [OpenMP的心得](http://aaz-blogger.blogspot.tw/search/label/OpenMP)
* [OpenMP介紹](https://kheresy.wordpress.com/2006/06/09/%e7%b0%a1%e6%98%93%e7%9a%84%e7%a8%8b%e5%bc%8f%e5%b9%b3%e8%a1%8c%e5%8c%96%e6%96%b9%e6%b3%95%ef%bc%8dopenmp%ef%bc%88%e4%b8%80%ef%bc%89%e7%b0%a1%e4%bb%8b/)
* [語法使用](https://kheresy.wordpress.com/2006/09/22/%E7%B0%A1%E6%98%93%E7%9A%84%E7%A8%8B%E5%BC%8F%E5%B9%B3%E8%A1%8C%E5%8C%96%EF%BC%8Dopenmp%EF%BC%88%E4%BA%94%EF%BC%89-%E8%AE%8A%E6%95%B8%E7%9A%84%E5%B9%B3%E8%A1%8C%E5%8C%96/)

---

## 實做結果
* loop_unrolling


* Force Inline + loop_unrolling


執行5次的平均時間

* OpenMP
* 在原有的程式碼下，直接插入OpenMP指令，並沒有使效能有效提昇，反而會降低許多。
* 在gprof中，可以看到各個function被呼叫的次數減少，推測是因為多核心分散處理的結果。

* OpenMP + Force Inline + loop_unrolling
* 而在優化後的程式碼中，插入OpenMP指令，效能顯著的提昇。
* gprof，可以看到比force_inline呼叫的次數少了許多。

---

## 問題討論
* 不太能確定為何原本的版本加上OpenMP會增加接近一倍的時間。