Try   HackMD

2016q3 Homework1 (raytracing)

contributed by <andy19950>

Review TotallyWrong

  • Callgraph 是個很好用的Tool 可以嘗試一下，可以看到一些不一樣的程式Behavior。其實還有AVX，Software Pipline等方案可以嘗試。

使用gprof分析程式熱點

Flat profile:

Each sample counts as 0.01 seconds.
  %   cumulative   self              self     total           
 time   seconds   seconds    calls   s/call   s/call  name    
 18.06      0.48     0.48 69646433     0.00     0.00  dot_product
 16.55      0.92     0.44 56956357     0.00     0.00  subtract_vector
 11.66      1.23     0.31 31410180     0.00     0.00  multiply_vector
  8.46      1.46     0.23 17836094     0.00     0.00  add_vector
  8.46      1.68     0.23 13861875     0.00     0.00  rayRectangularIntersection
  • 我們擷取前五名最花時間的function來對它們做最佳化！！
  • 目標是可以利用程式碼的最佳化達到跟編譯器最佳化一樣的效果

首先使用-Ofast來看看編譯器最佳化的結果

Performance counter stats for './raytracing' (100 runs):

       62,894	cache-misses	#27.256 % of all cache refs	( +-  1.64% )
      230,751	cache-references				( +-  3.17% )
  262,129,289	branch						( +-  0.00% )
3,417,337,773	instructions	#1.79  insns per cycle		( +-  0.00% )
1,905,665,597	cycles						( +-  0.12% )
0.646348227	seconds time elapsed				( +-  0.40% )
  • 平均執行時間 ： 0.64 sec
  • branch 次數 ： 2.6億次

接下來對 math-toolkit.h 進行優化

  • 對有 for迴圈 的 function 使用 loop unrolling
  • 以 add_vector 為例






void add_vector(const double *a, const double *b, double *out)
{
    out[0] = a[0] + b[0];
    out[1] = a[1] + b[1];
    out[2] = a[2] + b[2];
}
  • 修改後的結果如下，可以發現優化過的 function 執行時間都有下降
Each sample counts as 0.01 seconds.
  %   cumulative   self              self     total           
 time   seconds   seconds    calls   s/call   s/call  name    
 16.19      0.28     0.28 69646433     0.00     0.00  dot_product
 15.89      0.55     0.27 13861875     0.00     0.00  rayRectangularIntersection
 13.83      0.78     0.24 56956357     0.00     0.00  subtract_vector
 10.59      0.96     0.18 10598450     0.00     0.00  normalize
  7.06      1.08     0.12 31410180     0.00     0.00  multiply_vector
  • 使用 perf 觀察可以發現 branch 次數大幅下降！！
  • 執行時間距離目標還很遠，必須找其他方法降低。
 Performance counter stats for './raytracing' (100 runs):

       106,186	cache-misses	#24.499 % of all cache refs	( +-  2.82% )
       433,426	cache-references				( +-  2.71% )
   969,948,464	branch						( +-  0.00% )
12,314,790,448	instructions	#1.89  insns per cycle		( +-  0.00% )
 6,506,120,704	cycles						( +-  0.07% )
   2.152467875	seconds time elapsed				( +-  0.14% )

再一次觀察 gprof

  • 我們可以發現一個重點程式 ： raytracing
  • 它的呼叫次數只有一次但執行時間卻可以跟呼叫百萬次的一樣久
Each sample counts as 0.01 seconds.
  %   cumulative   self              self     total           
 time   seconds   seconds    calls   s/call   s/call  name    
  1.83      1.50     0.03  3838091     0.00     0.00  length
  1.83      1.53     0.03        1     0.03     1.64  raytracing
  1.22      1.55     0.02  2110576     0.00     0.00  localColor

觀察 raytracing()

  • 我們可以知道他是最後將圖片計算出來的函式
  • 程式碼的部份用三個for迴圈來計算每個 pixel 的RGB值
  • 使用 loop unrolling 的話會讓程式碼太龐大而且不知道圖片的大小
  • 所以這邊我使用 pthread 來平行處理每個 pixel 使其加速

＊ 在優化 raytracing() 之前先來了解一下什麼是 pthread

POSIX Threads

pthread_create() VS fork()

  • 產生以及控管 thread 相較於 process 所需的系統資源低很多
  • 下表為 fork 以及 pthread_create 在不同 cpu 執行50000個 process/threads 所使用的時間
     platform	     |		fork	     |	 pthread_create()
====================|	real	user	sys  |	real	user	sys
Intel 2.6 GHz Xeon  |	8.1 	0.1   	2.9  |	0.9 	0.2 	0.3
Intel 2.8 GHz Xeon  |	4.4 	0.4 	4.3  |	0.7 	0.2 	0.5
AMD 2.3 GHz Opteron |	12.5 	1.0 	12.5 | 	1.2 	0.2 	1.3
AMD 2.4 GHz Opteron |	17.6 	2.2 	15.7 |	1.4 	0.3 	1.3

Thread 各自獨立的單位

  1. Stack pointer
  2. Registers
  3. Scheduling properties
  4. Set of pending and blocked signals
  5. Thread specific data.

Shared Memory

  • 雖然每個 thread 都有自己獨立的 private data 以及大家一起使用的 shared memory
  • 但因為每個 thread 都是同步執行的，也就是誰先誰後沒有一定順序，所以使用 pthread 來同步執行必須先確保程式碼沒有相依性。

優化 raytracing()

  • 根據上面的結論，我們必須找出程式碼沒有相依性的地方。
  • 觀察程式碼後可以發現前兩個 for 迴圈只是在指定每個 pixel 的位置
  • 想法： 把圖片分成幾個區塊，用 pthread 平行運算

在 main 的部份生成 pthread 同時呼叫raytracing









for(j=0; j<THREAD_NUM; j++){
    /*---這邊省略把原本raytracing的參數包成struct傳入thread，詳細請參考我的github---*/
    input* box = (input*) malloc (sizeof(input));
    rc = pthread_create(&tid[j], &attr, raytracing, (void*) &box) ;
}

for(j=0; j<THREAD_NUM; j++)
    rc = pthread_join(tid[j], NULL);
  • input box為我宣告的struct，成員有原本需要傳入raytracing的參數。
  • 因為 pthread_create 只有第四個參數可以當作raytracing的傳入值，所以我把它包成結構傳入。
  • 需要注意的是根據定義第四個參數的型態必須是 (void*)。

在 raytracing的部份 把原本最外層的迴圈條件改變讓程式只跑整張圖的一部分



for (int j = box->j; j < (box->j + box->height / THREAD_NUM); j++) {
    for (int i = 0; i < box->width; i++) {
  • 每個thread都把寬度算完高度的部份用 THREAD_NUM 為單位去分。
  • 簡單來說就是把整張圖橫切等分為 THREAD_NUM個，每個用一個 thread 去計算它的pixel。
  • 下面部份的code若有用到原本的參數要向上面一樣使用 box->variable。

結果分析

  • thread 不是越多越好，512個 thread 執行時間不是最短！！
  • 最主要的原因應該是 main 還在分配 thread 的時候，可能就有前面的 thread 已經跑完了，這樣就沒有平行化的效果，卻還要付出呼叫 thread 的代價。
  • 經過實驗發現 THREAD_NUM = 8 開始效能算是最低（數據如下：）
THREAD_NUM	EXEC_TIME       ||	THREAD_NUM	EXEC_TIME
512		0.996285 sec    ||	256		1.016958 sec
128		1.003348 sec    ||	64		1.022087 sec
32		0.957354 sec    ||	16		0.965541 sec
8		0.968322 sec    ||	4		1.089226 sec
2		1.217084 sec    ||	1		2.160865 sec

使用 inline attribute (8 threads)

Performance counter stats for './raytracing' (100 runs):

        98,242	cache-misses	#11.745 % of all cache refs	( +-  0.80% )
       836,439	cache-references				( +-  0.80% )
   545,838,551	branch						( +-  0.00% )
10,597,581,108	instructions	#1.19  insns per cycle        	( +-  0.00% )
 8,893,931,480	cycles						( +-  0.13% )
   0.860754705	seconds time elapsed				( +-  0.26% )
  • 時間可以降至 0.86 sec

結論

  • 一開始使用 -Ofast 時間為 0.64 sec -O0 時間為 3.02 sec
  • 優化後使用 -Ofast 時間為 0.26 sec -O0 時間為 0.86 sec
  • 程式碼的最佳化竟然可以讓執行時間縮減成原來的 1/4
  • 希望未來能夠再把這份程式優化，讓我達成一開始的目標。

Reference

  • 特別感謝上面那位同學的共筆，非常詳細的解說，尤其是他解決了我苦思已久的bug！！
Last changed by 
 
吳庭安
0
660
Published on HackMD