# 2017q1 Homework1 (raytracing)
contributed by <`yangyang95`>
###### tags: `sysprog2017` `HW1` `yangyang95`
電腦規格看 [這裡](https://hackmd.io/s/HJ2c_XYKx)
github page 看 [這裡](https://github.com/yangyang95/raytracing)

### Reviewed by <`claaaaassic`>
* commit [f1f5dc634704b34c8bfaa3a288e9fb530a19fb69](https://github.com/yangyang95/raytracing/commit/f1f5dc634704b34c8bfaa3a288e9fb530a19fb69) 這個 commit 是錯誤的，可以使用 `git rebase` 修改內容，也可以省下下一個 fix typo 的 commit
* OpenMP 可以嘗試使用 schedule 決定多執行緒如何分配迴圈，或許可以更加改善效能

## 程式編譯

先執行一次測定執行時間

$ ./raytracing (without profiling)
# Rendering scene
Done!
Execution time of raytracing() : 2.923696 sec

再來加入 Proflie

$./raytracing (with profiling)
# Rendering scene
Done!
Execution time of raytracing() : 6.183047 sec

這裡值得一提的是，再加入 Profile 的指令 `$ make PROFILE=1` 之前
記得先清理之前編譯完的檔案 `$ make clean`
不然會出現以下訊息 `make: Nothing to be done for 'all'.`

使用 gprof 分析時竟然沒有輸出，見鬼了 = =
嘗試 make clean 重來也不行...
先來查查資料。

$ gprof -b raytracing gmon.out | less

Flat profile:

Each sample counts as 0.01 seconds.
  %   cumulative   self              self     total
 time   seconds   seconds    calls  Ts/call  Ts/call  name
^L

                        Call graph


granularity: each sample hit covers 2 byte(s) no time propagated

index % time    self  children    called     name
^L
Index by function name

(END)

上面的錯誤，經過搜尋還有 [FB 討論區](https://www.facebook.com/groups/system.software2017/permalink/1325126694219363) 版友的幫忙成功找到問題。
為 gcc-6 版本的 bug ，因為 --enabled-default-pie 的選項不同以往，在 gcc-6 是預設開啟，所以導致了沒有結果產生。在 CFLAGS 的部分加入` -no-pie`

參考資料：
- [Debian Bug report logs - binutils: GCC 6's --enable-default-pie breaks gprof](https://bugs.debian.org/cgi-bin/bugreport.cgi?bug=854704)
- [How to activate gcc 4.7 version?](http://askubuntu.com/questions/269257/how-to-activate-gcc-4-7-version)

## gporf & perf 分析

於是我使用 gcc-6.2.0 跟 -no-pie 的編譯選項重新比較一次結果。
之後的結果也以這邊為比較基準。

$ ./raytracing (without profiling)
# Rendering scene
Done!
Execution time of raytracing() : 2.920220 sec

$ ./raytracing (with profiling)
# Rendering scene
Done!
Execution time of raytracing() : 6.788265 sec

$ ./raytracing (使用 -O1 編譯器優化)
# Rendering scene 
Done!
Execution time of raytracing() : 0.802728 sec

gprof 分析結果：

Flat profile:

Each sample counts as 0.01 seconds.
  %   cumulative   self              self     total           
 time   seconds   seconds    calls   s/call   s/call  name    
 22.53      0.64     0.64 69646433     0.00     0.00  dot_product
 17.56      1.13     0.50 56956357     0.00     0.00  subtract_vector
 10.11      1.42     0.29 31410180     0.00     0.00  multiply_vector
  8.52      1.66     0.24 13861875     0.00     0.00  rayRectangularIntersection
  8.34      1.89     0.24 10598450     0.00     0.00  normalize
  6.92      2.09     0.20 13861875     0.00     0.00  raySphereIntersection
  5.50      2.24     0.16 17836094     0.00     0.00  add_vector
  5.32      2.39     0.15  4620625     0.00     0.00  ray_hit_object
  3.19      2.48     0.09  1048576     0.00     0.00  ray_color
  3.02      2.57     0.09 17821809     0.00     0.00  cross_product
  3.02      2.65     0.09  4221152     0.00     0.00  multiply_vectors
  1.60      2.70     0.05  2110576     0.00     0.00  localColor
  1.06      2.73     0.03  3838091     0.00     0.00  length
  1.06      2.76     0.03  2110576     0.00     0.00  compute_specular_diffuse
  0.71      2.78     0.02  2520791     0.00     0.00  idx_stack_top
  0.71      2.80     0.02        1     0.02     2.82  raytracing
  0.35      2.81     0.01  1241598     0.00     0.00  refraction
  0.35      2.82     0.01   113297     0.00     0.00  fresnel
  0.18      2.82     0.01        1     0.01     0.01  delete_sphere_list
  0.00      2.82     0.00  2558386     0.00     0.00  idx_stack_empty
  0.00      2.82     0.00  1241598     0.00     0.00  protect_color_overflow
  0.00      2.82     0.00  1241598     0.00     0.00  reflection
  0.00      2.82     0.00  1204003     0.00     0.00  idx_stack_push
  0.00      2.82     0.00  1048576     0.00     0.00  idx_stack_init
  0.00      2.82     0.00  1048576     0.00     0.00  rayConstruction
  0.00      2.82     0.00    37595     0.00     0.00  idx_stack_pop
  0.00      2.82     0.00        3     0.00     0.00  append_rectangular
  0.00      2.82     0.00        3     0.00     0.00  append_sphere
  0.00      2.82     0.00        2     0.00     0.00  append_light
  0.00      2.82     0.00        1     0.00     0.00  calculateBasisVectors
  0.00      2.82     0.00        1     0.00     0.00  delete_light_list
  0.00      2.82     0.00        1     0.00     0.00  delete_rectangular_list
  0.00      2.82     0.00        1     0.00     0.00  diff_in_second
  0.00      2.82     0.00        1     0.00     0.00  write_to_ppm

接下來試試 perf 分析：

  64.75%  libc-2.24.so  [.] _mcount
   9.51%  raytracing    [.] multiply_vector
   6.07%  raytracing    [.] dot_product
   3.44%  raytracing    [.] raytracing
   3.01%  libc-2.24.so  [.] __mcount_internal
   3.01%  raytracing    [.] subtract_vector
   2.63%  raytracing    [.] normalize
   2.63%  raytracing    [.] cross_product
   2.63%  raytracing    [.] multiply_vectors
   2.30%  raytracing    [.] idx_stack_push
   0.00%  raytracing    [.] raySphereIntersection
   0.00%  [kernel]      [k] nmi
   0.00%  raytracing    [.] localColor
   0.00%  raytracing    [.] ray_hit_object
   0.00%  raytracing    [.] add_vector
   0.00%  [kernel]      [k] irq_work_run
   0.00%  [kernel]      [k] native_sched_clock
   0.00%  [kernel]      [k] native_write_msr

在 [這篇](https://hackmd.io/s/ByDd4h8T#) 看到非常詳盡的程式碼分析。

## 強制 inline
將所有函式加入強制 inline 的 attribute `__attribute__((always_inline))` 來讓編譯器使用 inline
因為使用 inline 只能 **建議** 編譯器將函式的本體在使用到該函式的位置直接展開。

得到的執行時間是： 2.775253 sec ，快了大約 0.145 秒。

## Loop Unrolling
gprof 分析結果中 dot_product 函式佔 22.53% 的總時間，所以是第一個需要改善的函式。

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

嘗試把裡面的 for 迴圈展開，看看效能的變化。

double dot_product(const double *v1, const double *v2)
{
    return v1[0] * v2[0] + v1[1] * v2[1] + v1[2] * v2[2];
}

得到執行時間： 2.395486 sec ，又快了 0.38 秒。

接下來把向量處理的數學函式都進行 loop unrolling 處理。
得到的執行時間是： 1.838528 sec ，相較沒有 unrolling 的結果，快了大約 1 秒。

重新執行一次 gprof

  %   cumulative   self              self     total           
 time   seconds   seconds    calls   s/call   s/call  name    
 32.04      0.49     0.49 13861875     0.00     0.00  rayRectangularIntersection
 16.02      0.74     0.25  2110576     0.00     0.00  compute_specular_diffuse
 15.69      0.98     0.24 13861875     0.00     0.00  raySphereIntersection
 12.42      1.17     0.19  1048576     0.00     0.00  ray_color

可以看出佔用多數時間的已經變成 raytracing.c 內的函式。

## 多執行緒編程
對多執行緒沒有接觸過，因此先來讀點資料。
查看之前的共筆時看到很多 POSIX Thread 跟 OpenMP 的實作，所以來查查兩者有何不同。

- POSIX Thread (PThread)：作為POSIX標準的擴展，Pthreads可以提供使用者層級(User-level)或是核心階層(Kernel-level)的多執行緒庫。為底層的執行緒 API ，需要較熟練的執行緒管理。
- OpenMP：誇平台的多執行緒實現，為上層的執行緒函式庫。

參考資料：
- [Pthreads vs. OpenMP](http://stackoverflow.com/questions/3949901/pthreads-vs-openmp)
- [多執行緒 (Multi-thread)](https://sls.weco.net/node/21324)
- [POSIX執行緒](https://zh.wikipedia.org/wiki/POSIX%E7%BA%BF%E7%A8%8B)

## OpenMP
這裡稍微介紹一下語法，OpenMP 的句子分成三個部分：
- Directives (編譯程式定向) : 程式人員加入，用以提示編譯器如何編譯的字句
- Clauses (子句)
- Functions (函式)

語法參考： `#pragma omp directive [clause]`
舉例來說： `#pragma omp parallel for`

參考資料：
- [Directive - wiki](https://en.wikipedia.org/wiki/Directive_(programming))
- [簡易的程式平行化](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/)
- [OpenMP 函式庫](https://msdn.microsoft.com/en-us/library/tt15eb9t.aspx)

針對 raytracing 函式進行平行化處理，在函式內的 for 迴圈加入 OpenMP 語法：
`#pragma omp parallel for num_threads(64) private(stk), private(d),private(object_color)`

以 64 個執行緒，來讓 for 迴圈增加效能。同時需把迴圈內會被改變的變數改為 private 。

得到執行時間： 0.724710 sec ，到這裡已經成功比編譯器優化來的快了。

參考資料：
- [ktvexe HackMD 筆記](https://hackmd.io/s/Sygsi6X6)
- [jkrvivian HackMD 筆記](https://hackmd.io/s/ByDd4h8T#)
- [baimao8437 HackMD 筆記](https://hackmd.io/s/rkVjtkkcl)

## gnuplot 製圖
最後利用 gnuplot 來將結果製圖，試了好久才成功 XD

output.txt ：

Original  2.920220
inline    2.775253
unrolling 1.838528
-O1       0.802728
OpenMP    0.724710

runtime .gp ：

reset
set ylabel 'time(sec)'
set style fill solid
set title 'perfomance comparison'
set term png enhanced font 'Verdana,10'
set output 'runtime.png'
set key above

plot [:][0:3.5]'output.txt' using 2:xticlabel(1) with histogram notitle, \
'' using ($0+0.2):($2+0.1):2 with labels notitle

參考資料：
- [gnuplot 語法解說和示範](https://hackmd.io/s/Skwp-alOg)
- [Chapter 6. Input, Output](http://dsec.pku.edu.cn/dsectest/dsec_cn/gnuplot/plot-6.html)
- [gnuplot demo script](http://gnuplot.sourceforge.net/demo_cvs/datastrings.html)

## 結論：
將各種實作方法繪圖後，可看出比 -O1 編譯器優化來的快速。

註：後面的優化方法是根據前面方法再進行優化，也就是說 OpenMP 實作也包含 inline, unrolling 提供的優化。