Try   HackMD

光線追蹤程式案例分析

tags: sysprog-hw raytracing parallelism

TODO

  • 學習使用 Gnu gprof
  • 研究 math-toolkit.h 其中數學函式
  • 優化 raytracing (透過 thread、。。。)
  • 學習 raytracing 的運行原理
  • raytracing 實作

Gnu gprof 效能分析

Gprof 操作

使用指令make PROFILE=1 會讓程式重新編譯並加入-gp的參數，接著執行 raytracing 會讓 gprof 啟動並分析數據，會產生出一份 gmon.out 的文件，再輸入 gprof -b a.out gmon.out | less 便會得到 raytracing 中各函數的詳細資訊：

Jason H：gprof -b a.out gmon.out | less 標起來的地方應該要寫raytracing吧~XDDD

Hua：謝謝同學指證

Flat profile:

Each sample counts as 0.01 seconds.
  %   cumulative   self              self     total           
 time   seconds   seconds    calls   s/call   s/call  name    
 23.59      0.66     0.66 69646433     0.00     0.00  dot_product
 13.94      1.05     0.39 56956357     0.00     0.00  subtract_vector
 11.79      1.38     0.33 13861875     0.00     0.00  rayRectangularIntersection
  8.58      1.62     0.24 10598450     0.00     0.00  normalize
  6.79      1.81     0.19 17836094     0.00     0.00  add_vector
  6.61      2.00     0.19 31410180     0.00     0.00  multiply_vector
  6.43      2.18     0.18 13861875     0.00     0.00  raySphereIntersection
  5.54      2.33     0.16 17821809     0.00     0.00  cross_product
  3.22      2.42     0.09  4620625     0.00     0.00  ray_hit_object
  2.50      2.49     0.07  1048576     0.00     0.00  ray_color
  2.14      2.55     0.06  4221152     0.00     0.00  multiply_vectors
  2.14      2.61     0.06  2110576     0.00     0.00  compute_specular_diffuse
  1.79      2.66     0.05        1     0.05     2.80  raytracing
  1.43      2.70     0.04  2110576     0.00     0.00  localColor
  1.07      2.73     0.03  1241598     0.00     0.00  refraction
  1.07      2.76     0.03  1048576     0.00     0.00  rayConstruction
  0.71      2.78     0.02  3838091     0.00     0.00  length
  0.36      2.79     0.01  2520791     0.00     0.00  idx_stack_top
  0.36      2.80     0.01  1204003     0.00     0.00  idx_stack_push
  0.00      2.80     0.00  2558386     0.00     0.00  idx_stack_empty
  0.00      2.80     0.00  1241598     0.00     0.00  protect_color_overflow
  0.00      2.80     0.00  1241598     0.00     0.00  reflection
  0.00      2.80     0.00  1048576     0.00     0.00  idx_stack_init
  0.00      2.80     0.00   113297     0.00     0.00  fresnel
  0.00      2.80     0.00    37595     0.00     0.00  idx_stack_pop
  0.00      2.80     0.00        3     0.00     0.00  append_rectangular
  0.00      2.80     0.00        3     0.00     0.00  append_sphere
  0.00      2.80     0.00        2     0.00     0.00  append_light
  0.00      2.80     0.00        1     0.00     0.00  calculateBasisVectors
  0.00      2.80     0.00        1     0.00     0.00  delete_light_list
  0.00      2.80     0.00        1     0.00     0.00  delete_rectangular_list
  0.00      2.80     0.00        1     0.00     0.00  delete_sphere_list
  0.00      2.80     0.00        1     0.00     0.00  diff_in_second
  0.00      2.80     0.00        1     0.00     0.00  write_to_ppm

(還不了解各個函式再 raytracing 中為何會佔用如此比例，研究完程式主體後，再補充)

Gprof 參數

Gprof 可依據自己的需求去調出需要的資訊：

  • -b：不輸出統計圖表中每個字段的詳細描述。
  • -p：只輸出函數的調用圖。
  • -q：只輸出函數的時間消耗列表。
  • -E Name：不再輸出函數Name 及其子函數的調用圖，此標誌類似於 -e 標誌，但它在總時間和百分比時間的計算中排除了由函數Name 及其子函數所用的時間。
  • -e Name：不再輸出函數Name 及其子函數的調用圖（除非它們有未被限制的其它父函數）。可以給定多個 -e 標誌。一個 -e 標誌只能指定一個函數。
  • -F Name：輸出函數Name 及其子函數的調用圖，它類似於 -f 標誌，但它在總時間和百分比時間計算中僅使用所打印的例程的時間。可以指定多個 -F 標誌。一個 -F 標誌只能指定一個函數。 -F 標誌覆蓋 -E 標誌。
  • -f Name：輸出函數Name 及其子函數的調用圖。可以指定多個 -f 標誌。一個 -f 標誌只能指定一個函數。
  • -z：顯示使用次數為零的例程（按照調用計數和累積時間計算）。

關於math-toolkit.h

inline function(內行函式)

由於呼叫函式會消耗資源，而當函式本身的操作相當少時，這樣子的函式呼叫對 CPU 而言是相當沒有效率的，也因此有了 inline 的使用，當一支函式被宣告成 inline 時，程式執行到此函數時，會使用類似巨集(macro)的方法將函式直接展開運算。

int inline plus(int x)
{
    return x*x;
}

int main(int argc, char argv[]){
    
    plus(10);
    
    return 0;
}

當執行main時的效果會等同於

int main(int argc, char argv[]){
    
    int x = 10;
    x*x;
    
    return 0;
}

Inline直接再程式執行中把函式展開，而不是另外使用記憶體來呼叫函式並運算，對於小型的函式而言，這樣處理的效益較高。

優化

未優化版本

# Rendering scene
Done!
Execution time of raytracing() : 2.355340 sec

用編譯器最佳化時間

by -Ofast
# Rendering scene
Done
Execution time of raytracing() : 0.492111 sec

好像有點快…= =

Loop unrolling

將已知執行次數的迴圈全部展開，省略判斷；透過 gprof 得知使用次數最高的函式，針對這些"熱點"來進行優化

/*dot_product：69646433 times call*/
static inline double dot_product(const double *v1, const double *v2)
{
    double dp = 0.0;
        dp += v1[0] * v2[0];
        dp += v1[1] * v2[1];
        dp += v1[2] * v2[2];
    return dp;
}

僅僅修改 dot_product 的函式就使得時間有了0.25秒的縮減：

# Rendering scene
Done!
Execution time of raytracing() : 2.100537 sec

接著針對呼叫次數超過10萬次的"熱點"去做優化，其中有：dot_product、subtract_vector、add_vector、multiply_vector、multiply_vectors

# Rendering scene
Done!
Execution time of raytracing() : 1.688148 sec

足足有0.67秒的時間縮減

上述函式總合共有 180070216 次的 function call，而我的電腦是3.8GHz的CPU，每次for loop都需要比loop unrooling的函式多了 7 次的指令( 宣告i + ( 條件判斷 + i++ ) * 迴圈執行次數 )，因此預測減少的執行時間應該是：
(180070216 / 3.8GHz ) * 7 = 0.33170829263(s)

但實際執行時間足足比預測時間少了兩倍，這邊"推測是"CPU的 branch prediction 所導致，當 branch prediction 預測失敗時的 time penalty 會是兩倍的指令時間，這樣算出來的時間就較為接近實際時間：
(180070216 / 3.8GHz ) * 7 * 2 = 0.66341658526(s)

會說是推測的原因是因為，for loop 應當是傾向於預測繼續執行的 branch prediction，但如此一來預測時間會與實際執行有一段落差，況且我並不清楚硬體是不是有採用 branch prediction 的作法：
(180070216 / 3.8GHz ) * (7 + 2) = 0.42648209052(s)

OpenMP

利用 OpenMP 的 API 對程式進行平行化，OpenMP儘管使用起來相對 POSIX Threads 簡易且方便，但被平行化的程式碼有著更多的限制，視情況會有不一樣的使用。

使用 OpenMP 必須引入<omp.h>的函式庫，以下是針對不會相互影響的 for loop 去進行平行化的修改，這裡必須注意的是，因為下述函式都是執行 3 次的 for loop，因此不直接對 for loop 進行平行化，而是在 loop unrolling 之後將三次的運算切割成 3 個 section 後運算。

比較：for loop平行化( 2 threads )、section切割( 3 threads )

/*subtract_vector*/
static inline
void subtract_vector(const double *a, const double *b, double *out)
{
        #pragma omp parallel sections
        {
                #pragma omp section
                {
                        out[0] = a[0] - b[0];
                }
                #pragma omp section
                {
                        out[1] = a[1] - b[1];
                }
                #pragma omp section
                {
                        out[2] = a[2] - b[2];
                }        
        }
}

對 subtract_vector、add_vector、multiply_vector、multiply_vectors 四個函式進行切割後，有了0.5秒的進步

# Rendering scene
Done!
Execution time of raytracing() : 1.858434 sec

在繼續對 dot_product 進行平行化，因為 dot_product 的 for loop 中的運算是相互有關聯的，所以用上面的方法會讓變數因為 race condition 而有錯誤的存取，為了避免此一問題將程式修改成：

/*dot_product*/
static inline
double dot_product(const double *v1, const double *v2)
{
    double dp0, dp1, dp2;

    #pragma omp parallel sections
    {
        #pragma omp section
        {
            dp0 = v1[0] * v2[0];
        }
        #pragma omp section
        {
            dp1 = v1[1] * v2[1];
        }
        #pragma omp section
        {
            dp2 = v1[2] * v2[2];
        }        
    }
    return dp0 + dp1 + dp2;
}

執行時間：

# Rendering scene
Done!
Execution time of raytracing() : 1.664112 sec

雖然 OpenMP 的方法相對於未優化是有時間上的縮減，但與 Loop unrooling 相比較是沒有多大差別的，這是因為平行化在配置 CPU 去執行任務時會有時間上的成本，而這次優化的對象的迴圈都是小型的迴圈，如果迴圈的執行次數一大，則平行化就會更加的有效益。

強制 Inline 展開

inline在程式中的展開對於編譯器而言都是建議，因此並非所有的 inline function都是展開的，只要修改函式就可以強制展開：

static inline __attribute__((always_inline))
double dot_product(const double *v1, const double *v2)
{
    double dp = 0.0;
    for (int i = 0; i < 3; i++)
        dp += v1[i] * v2[i];
    return dp;
}

結果：

# Rendering scene
Done!
Execution time of raytracing() : 2.082474 sec

Multi-Thread

前言：真正實作才知道 Thread 有多難…

Jim H：「眼高手低」的困境

Hua：老師的"誠實面對自己"聲聲入耳

首先必須先了解 thread 的使用方法

/*pthread reference*/
int pthread_create
(
    pthread_t *restrict thread,//thread位置傳入
    const pthread_attr_t *restrict attr,//
    void *(*start_routine)(void*),//function位置傳入
    void *restrict arg//function參數傳入
);//thread生成成功時，會回傳0

/*同步thread的執行，等待所有指定的thread執行完，才會繼續*/
int pthread_join
(
    pthread_t thread,//thread位置傳入
    void **value_ptr//
);//成功時，回傳0

簡單的 thread 使用概念示意：

pthread_t thread1, thread2;//生成thread
//將thread連接到要被執行的函式
pthread_create(&thread1, NULL, &function, 傳入參數);
pthread_create(&thread2, NULL, &function, 傳入參數);
//執行完同步
pthread_join(&thread1, NULL);
pthread_join(&thread2, NULL);
//end

實作過程 ( 參照陳品睿同學的開發紀錄 )：
我將 raytracing 的函式切成若干段後，交由 thread 去執行平行化，其中遇到的問題：

  • thread_create 函數只能傳遞一個參數，因此必須將參數包成一個 struct 後傳入
  • thread_create 傳遞的參數要傳入(void *)
  • thread_create所要求的函數必須回傳 ( void * )的值

Jim H：請比較 thread_num 從 2, 4, 8, 16, 32 一路增加，對於效能的改善(或衰退)

Hua：好的

實作結果(THREAD_NUM = 2)：
Execution time of raytracing() : 1.271259 sec

實作結果(THREAD_NUM = 4)：
Execution time of raytracing() : 0.963407 sec

實作結果(THREAD_NUM = 8)：
Execution time of raytracing() : 0.664082 sec

實作結果(THREAD_NUM = 16)：
Execution time of raytracing() : 0.601015 sec

實作結果(THREAD_NUM = 20)：
Execution time of raytracing() : 0.585029 sec

實作結果(THREAD_NUM = 32)：
Execution time of raytracing() : 0.603257 sec

實作結果(THREAD_NUM = 64)：
Execution time of raytracing() : 0.552773 sec

整合(Github上版本)

上面的所有優化都只有單一項優化，因此將 Loop unrolling、強制inline展開及 mutlithread 三種優化做整合，因為 mutlithread 的執行時間已經接近最佳化了，果然整合後就成功突破了。

這邊沒有把 OpenMP 的最佳化整合進去是因為 Loop unrolling 的時間與其相差不多，但程式碼只能選擇一種，因此我選擇了 Loop unrolling 較單純對電腦負擔也較小。

Loop unrolling + 強制inline展開 + mutlithread
# Rendering scene
Done!
Execution time of raytracing() : 0.330396 sec

OpenMP + 強制inline展開 + mutlithread
# Rendering scene
Done!
Execution time of raytracing() : 0.330861 sec

時間圖

參考文獻

Last changed by 
 
ShaoHua Wang
0
1
586
Published on HackMD