2017q1 Homework1 (raytracing)

contributed by<jack81306>

Reviewed by `changyuanhua`

commit 的標題要用命令口吻，所以不要用 ThirdOptimized 這類開頭（我之前也犯過相同錯誤 )
這裡有 commit 錯誤標題首字大寫
可以放你的程式碼在上面
可以加上圖表，比較你每次實驗的時間等等，這樣一眼就能看出你實驗的差異

tags:`jack81306`

開發環境

Architecture:          x86_64
CPU 作業模式：    32-bit, 64-bit
Byte Order:            Little Endian
CPU(s):                4
On-line CPU(s) list:   0-3
每核心執行緒數：2
每通訊端核心數：2
Socket(s):             1
NUMA 節點：         1
供應商識別號：  GenuineIntel
CPU 家族：          6
型號：              60
Model name:            Intel(R) Core(TM) i5-4210M CPU @ 2.60GHz
製程：              3
CPU MHz：             2463.049
CPU max MHz:           3200.0000
CPU min MHz:           800.0000
BogoMIPS:              5187.96
虛擬：              VT-x
L1d 快取：          32K
L1i 快取：          32K
L2 快取：           256K
L3 快取：           3072K
NUMA node0 CPU(s):     0-3

首次測試

為了和之後的優化做比較,因此先進行第一次尚未優化過的程式碼測試.
使用工具
- gprof: gprof介紹教學
- graphviz: graphviz使用
- gprof2dot: gprof2dot安裝及使用

第一次運行時間

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

第一次運行時間（編譯時添加上-pg）

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

運行時各 function 運行時間

Each sample counts as 0.01 seconds.
  %   cumulative   self              self     total           
 time   seconds   seconds    calls   s/call   s/call  name    
 20.19      0.45     0.45 56956357     0.00     0.00  subtract_vector
 18.40      0.86     0.41 69646433     0.00     0.00  dot_product
 10.32      1.09     0.23 10598450     0.00     0.00  normalize
  9.42      1.30     0.21 13861875     0.00     0.00  rayRectangularIntersection
  8.08      1.48     0.18 17836094     0.00     0.00  add_vector
  5.83      1.61     0.13 17821809     0.00     0.00  cross_product
  5.61      1.74     0.13 31410180     0.00     0.00  multiply_vector
  4.94      1.85     0.11  4620625     0.00     0.00  ray_hit_object
  4.49      1.95     0.10 13861875     0.00     0.00  raySphereIntersection
  3.14      2.02     0.07  1048576     0.00     0.00  ray_color
  2.47      2.07     0.06  4221152     0.00     0.00  multiply_vectors
  1.79      2.11     0.04  2110576     0.00     0.00  compute_specular_diffuse
  0.90      2.13     0.02  3838091     0.00     0.00  length
  0.90      2.15     0.02  1048576     0.00     0.00  rayConstruction
  0.67      2.17     0.02  1204003     0.00     0.00  idx_stack_push
  0.45      2.18     0.01  2520791     0.00     0.00  idx_stack_top
  .
  .
  .

從運行時間中,我們可以發現到說subtract_vector和dot_product這兩個 function 是造成程式運行速度慢的原因,所以我第一次的優化打算對這兩個 funciton 進行優化.

中英文字間請以空白隔開
課程助教

圖表分析

第一次優化

這次優化,我使用了loop unrolling的方法作為優化方法,我將subtract_vector和dot_product這兩個function進行循環展開,以降低浪費再計算回圈的時間.
第一次優化後運行時間

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

第一次優化後運行時間(編譯時加上-pg選項)

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

從這個結果看來,大約只有優化了0.4秒左右,實在是很少阿！現在我再來看一下,是什麼托慢了整體的運行時間.
運行時各function運行時間

Each sample counts as 0.01 seconds.
  %   cumulative   self              self     total           
 time   seconds   seconds    calls   s/call   s/call  name    
 17.18      0.29     0.29 69646433     0.00     0.00  dot_product
 12.06      0.49     0.20 31410180     0.00     0.00  multiply_vector
 11.45      0.68     0.19 10598450     0.00     0.00  normalize
 10.85      0.86     0.18 56956357     0.00     0.00  subtract_vector
  7.84      0.99     0.13  4620625     0.00     0.00  ray_hit_object
  7.53      1.11     0.13 17821809     0.00     0.00  cross_product
  7.23      1.23     0.12 13861875     0.00     0.00  rayRectangularIntersection
  5.42      1.32     0.09 17836094     0.00     0.00  add_vector
  4.22      1.39     0.07 13861875     0.00     0.00  raySphereIntersection
  3.01      1.44     0.05  4221152     0.00     0.00  multiply_vectors
  3.01      1.49     0.05  2110576     0.00     0.00  compute_specular_diffuse
  1.81      1.52     0.03  2520791     0.00     0.00  idx_stack_top
  1.81      1.55     0.03  1048576     0.00     0.00  ray_color
  1.81      1.58     0.03        1     0.03     1.64  raytracing
  1.21      1.60     0.02  3838091     0.00     0.00  length
  1.21      1.62     0.02  2110576     0.00     0.00  localColor
  1.21      1.64     0.02        1     0.02     0.02  delete_sphere_list
  0.60      1.65     0.01  1241598     0.00     0.00  reflection
  0.60      1.66     0.01  1048576     0.00     0.00  rayConstruction
  0.00      1.66     0.00  2558386     0.00     0.00  idx_stack_empty
  0.00      1.66     0.00  10241598     0.00     0.00  protect_color_overflow
  0.00      1.66     0.00  1241598     0.00     0.00  refraction
  0.00      1.66     0.00  1204003     0.00     0.00  idx_stack_push
  0.00      1.66     0.00  1048576     0.00     0.00  idx_stack_init
  .
  .
  .

從這個運行時間可以觀察到說,subtract_vector的運行時間從0.45降低到0.18,而dot_product從0.41秒降0.29秒,雖然有降低,但是還不夠快,還要更快.

圖表分析

第二次優化

第二次的優化,因為math-toolkit的function call都高達數千萬次,所以我把目標放在減少function call.
為了減少程式的function call,所以我把math-toolkit裡的funtion都加上了__attribute__((always_inline)).這條程式碼可以強制編譯器再編譯的時候,把function變為inline.
第二次運行時間

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

第二次運行時間（編譯時附加參數-pg）

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

這個結果讓我感到十分的驚訝阿！！沒有附加-pg參數的結果只減少了大約0.3秒,但是編譯時有附加pg參數的卻減少了2秒多.
於是我去閱讀了gprof的手冊,內容大概是,當你call一個function,會先執行額外的程式碼來紀錄時間與function名,所以結果就是當function call變少時,加入-pg選項的所需的額外時間也會跟著減少.
不過雖然function call 減少了許多,不過運行時間根第一次優化比起來,只減少了0.3秒左右,這速度還不夠快,還要更快阿！！！

圖表分析

第三次優化

第三次優化原本打算使用pthread來進行平行處理,但是再看完pthread的使用方式以及程式碼後,發現我根本不知道從哪裡下手去切thread阿阿阿阿
- pthread基本使用與介紹
於是我找了第二種方法,"OpenMP"來做平行處理,OpenMP的使用方式較為簡單,只要再回圈前面加入一些程式碼與參數即可,輸入之後,compile會自動將回圈內進行平行化處理.
- OpenMP基本使用與介紹
第3-1次優化：失敗
這次的優化我只有單純把raytracing裡的for回圈平行化,不過似乎會造成錯誤的結果,但是時間加快許多！！！
第3-1次優化運行時間

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

第3-2次優化
終於成功了,可喜可賀,這次我再優化選項後面添加了老師給的共筆內所提到的private(stk,d,object_color),發現結果仍然錯誤.
於是我後來觀察了一下,發現r,g,b 3個變數會進行累加,如果進行平行化的話,會有錯誤的結果,於是又增加了參數private(r,g,b),給這3個變數增加副本,這次結果就正確了！！
3-2次優化運行時間

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

參考資料

loop unrolling簡介
 forceInline方法
 OpenMG簡介與使用
 pthread簡介與使用

2017q1 Homework1 (raytracing)

Reviewed by changyuanhua

tags:jack81306

開發環境

首次測試

第一次優化

第二次優化

第三次優化

參考資料

Reviewed by `changyuanhua`

tags:`jack81306`