# 2017q1 Homework1 (raytracing)
contributed by < `claaaaassic` >
### Reviewed by you74674
* commit內容蠻清楚的
* 關於loop unrolling，或許可以比較看看compiler的loop unrolling flag？
* 開發紀錄內容也很完整
## 開發環境
```shell
$ lscpu
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
型號： 42
Model name: Intel(R) Core(TM) i5-2410M CPU @ 2.30GHz
製程： 7
CPU MHz： 886.785
CPU max MHz: 2900.0000
CPU min MHz: 800.0000
BogoMIPS: 4589.49
虛擬： VT-x
L1d 快取： 32K
L1i 快取： 32K
L2 快取： 256K
L3 快取： 3072K
NUMA node0 CPU(s): 0-3
```
## 基本知識
gcc options
- `-O0` : 使用預設編譯模式(關閉最佳化)
- `-pg` : 編譯時加入一些 code 可讓 gprof 觀測
GNU gprof
- 分析什麼是程式執行中最花時間的，以及 function 之間的關係
call graph
- 追蹤 function 之間的關係
force inline
- inline是向編譯器提出“建議”，把inline的函數在函數位置直接展開（減輕系統負擔(overhead)），編譯器會對比兩者執行時間後選擇執行inline與否。
POSIX Thread
OpenMP
software pipelining
loop unrolling
## 作業要求
* 在 GitHub 上 fork [raytracing](https://github.com/sysprog21/raytracing)，並思考如何改善程式效能
* 以 `make PROFILE=1` 重新編譯程式碼，並且學習 [gprof](https://sourceware.org/binutils/docs/gprof/)
* 參考 [使用 GNU gprof 進行 Linux 平台的程式分析](http://os.51cto.com/art/200703/41426.htm)
* 以 [gprof](https://sourceware.org/binutils/docs/gprof/) 指出效能瓶頸，並且著手改寫檔案 `math-toolkit.h` 在內的函式實做，充分紀錄效能差異在共筆
* 注意: 請勿更動編譯器最佳化選項 `-O0` (關閉最佳化)
* 檔案 `math-toolkit.h` 定義的若干數學操作函式很重要，可參考 [Investigating SSE cross product performance](http://threadlocalmutex.com/?p=8)、[MathFu](https://google.github.io/mathfu/) 原始程式碼，以及 [2015q3 Homework #1 Ext](http://wiki.csie.ncku.edu.tw/embedded/2015q3h1ext)
* 可善用 POSIX Thread, OpenMP, software pipelining, 以及 loop unrolling 一類的技巧來加速程式運作
* 將你的觀察、分析，以及各式效能改善過程，並善用 gnuplot 製圖，紀錄於「[作業區](https://hackmd.io/s/Hy2rieDYe)」
## graphviz
參考 [2016q3 hugikun999](https://hackmd.io/s/HyHhgcv6#) 的筆記
### 安裝過程
```shell
$sudo apt-get install python python-pip
$sudo pip install --upgrade pip
$sudo pip install gprof2dot
```
### 圖表
`$ gprof ./raytracing | gprof2dot | dot -T png -o output.png`
神奇的圖表就這樣跑出來了！非常有助於理解程式啊！原本醜醜的 call graph 只有一些文字表格，圖表真的好看很多，不過我這張圖是在已經使用 loop unrolling 跟 force inline 改善過了不是一開始的圖
## 開發過程
首先看完 [video](https://www.youtube.com/watch?v=m1RmfOfSwno) "Homework 2" 的部份、實做程式的解說 [video](https://www.youtube.com/watch?v=V_rLyzecuaE)、[對應的共筆](https://embedded2016.hackpad.com/ep/pad/static/f5CCUGMQ4Kp)
這個作業要觀察 raytracing 的效能瓶頸，改寫檔案改善程式效能，過程中維持 `gcc -O0` (關閉最佳化)，可以以 POSIX Thread, OpenMP, software pipelining, loop unrolling 為改善的方向。
### 以 make PROFILE=1 重新編譯程式碼，並且學習 gprof
在 Makefile 裡面找到這段程式
```shell
CFLAGS = \
-std=gnu99 -Wall -O0 -g
LDFLAGS = \
-lm
ifeq ($(strip $(PROFILE)),1)
PROF_FLAGS = -pg
CFLAGS += $(PROF_FLAGS)
LDFLAGS += $(PROF_FLAGS)
endif
```
也就是輸入 `$ make PROFILE=1` 可以編譯檔案後面帶著 `-pg` 的參數，查一下這個參數可以幹麻
> Generate extra code to write profile information suitable for the analysis program gprof
> [reference link](https://gcc.gnu.org/onlinedocs/gcc-6.3.0/gcc/Instrumentation-Options.html#Instrumentation-Options)
所以說輸入 `$ make PROFILE=1` 就可以開始來學習 gprof 了！
==注意：在 CFLAGS 及 LDFLAGS 都需要加上`-O0`==
首先觀察一下精美的 650 行程式碼
```shell
$ cloc *.[ch]
8 text files.
8 unique files.
0 files ignored.
http://cloc.sourceforge.net v 1.60 T=0.01 s (684.7 files/s, 73091.8 lines/s)
-------------------------------------------------------------------------------
Language files blank comment code
-------------------------------------------------------------------------------
C 3 93 70 453
C/C++ Header 5 41 0 197
-------------------------------------------------------------------------------
SUM: 8 134 70 650
-------------------------------------------------------------------------------
```
接著看看執行時間
```shell
# Rendering scene
Done!
Execution time of raytracing() : 3.837321 sec
```
接著看看加上 `-pg` 的執行時間
```shell
# Rendering scene
Done!
Execution time of raytracing() : 7.437667 sec
```
居然要花到大約 7.43 秒，那就來看一下多花的這些執行時間給我的資訊吧
```shell
$ gporf ./raytracing | less
Each sample counts as 0.01 seconds.
% cumulative self self total
time seconds seconds calls s/call s/call name
20.63 0.67 0.67 56956357 0.00 0.00 subtract_vector
20.01 1.32 0.65 69646433 0.00 0.00 dot_product
10.16 1.65 0.33 10598450 0.00 0.00 normalize
9.54 1.96 0.31 17836094 0.00 0.00 add_vector
7.70 2.21 0.25 13861875 0.00 0.00 rayRectangularIntersection
6.16 2.41 0.20 13861875 0.00 0.00 raySphereIntersection
6.00 2.61 0.20 31410180 0.00 0.00 multiply_vector
4.93 2.77 0.16 4620625 0.00 0.00 ray_hit_object
3.39 2.88 0.11 17821809 0.00 0.00 cross_product
2.62 2.96 0.09 4221152 0.00 0.00 multiply_vectors
2.46 3.04 0.08 1048576 0.00 0.00 ray_color
1.54 3.09 0.05 2110576 0.00 0.00 localColor
```
光是花在前三個 function 居然就佔了整體 50% 左右，呼叫的次數也是千萬等級的，如果減少前三個 function 的執行時間應該可以有效的增加效能
## Optimization : loop unrolling
針對 math-toolkit.h 裡面的迴圈進行改善，把三層的迴圈展開！雖然降低可讀性但是可以增快速度
執行時間由 **3.837321 sec** 降為 **2.617314 sec**，大約為原本的 **68.2%**
```
# Rendering scene
Done!
Execution time of raytracing() : 2.617314 sec
```
根據 gprof 產生的分析可以比較一下使用 loop unrolling 的函式所獲得的改善，觀察 self 欄位可以看出函式的總執行時間
subtract_vector 0.67 > 0.22
dot_product 0.65 > 0.32
add_vector 0.31 > 0.04
multiply_vectors 0.09 > 0.02
multiply_vector 0.20 > 0.19
時間上大都有所減少
```shell
Flat profile:
Each sample counts as 0.01 seconds.
% cumulative self self total
time seconds seconds calls s/call s/call name
17.50 0.32 0.32 69646433 0.00 0.00 dot_product
14.22 0.58 0.26 13861875 0.00 0.00 rayRectangularIntersection
14.22 0.84 0.26 10598450 0.00 0.00 normalize
11.76 1.06 0.22 56956357 0.00 0.00 subtract_vector
10.12 1.24 0.19 31410180 0.00 0.00 multiply_vector
7.93 1.39 0.15 17821809 0.00 0.00 cross_product
5.19 1.48 0.10 4620625 0.00 0.00 ray_hit_object
4.37 1.56 0.08 1048576 0.00 0.00 ray_color
2.73 1.61 0.05 13861875 0.00 0.00 raySphereIntersection
2.73 1.66 0.05 2110576 0.00 0.00 compute_specular_diffuse
2.19 1.70 0.04 17836094 0.00 0.00 add_vector
1.64 1.73 0.03 1241598 0.00 0.00 refraction
1.09 1.75 0.02 2110576 0.00 0.00 localColor
1.09 1.77 0.02 1048576 0.00 0.00 rayConstruction
0.82 1.79 0.02 4221152 0.00 0.00 multiply_vectors
```
從圖表上也可以看出整體的時間差異
:::success
> [time=Mon, Mar 13, 2017 1:41 AM]
這邊看完文章[Modern Microprocessers](http://www.lighterra.com/papers/modernmicroprocessors/)之後，我不知道哪來的想法覺得使用 loop unrolling 應該可以減少 cache misses 以及使得 instructions per cycle 增加，以下進行 perf 比較
* original
```
Performance counter stats for './raytracing' (10 runs):
51,357 cache-misses # 26.809 % of all cache refs ( +- 2.60% )
191,564 cache-references ( +- 6.88% )
19,467,327,586 instructions # 1.82 insn per cycle ( +- 0.00% )
10,722,360,954 cycles ( +- 0.09% )
```
* loop unrolling
```
Performance counter stats for './raytracing' (10 runs):
45,413 cache-misses # 28.828 % of all cache refs ( +- 3.19% )
157,528 cache-references ( +- 3.48% )
12,315,238,559 instructions # 1.69 insn per cycle ( +- 0.00% )
7,285,757,575 cycles ( +- 0.07% )
```
結果卻是相反的， cache misses 以及 instructions per cycle 雖然總量減少，可是比例上來說卻是增加的，所以說使用 loop unrolling 理論上來說可以減少 branch prediction 產生的 cache misses ，但結果上來說卻是沒有符合理論。
:::
## Optimization : force inline
在 Makefile 中的 gcc 有使用 `-O0` 這個關閉最佳化的選項，但如果想要減少函數呼叫次數，可以使用 force inline，將 function 放入呼叫該 function 的位置，使用方法為加上 __attribute__((always_inline))
首先測試看看前三耗時的 function 使用 force inline 會不會變更快
```
# Rendering scene
Done!
Execution time of raytracing() : 2.488187 sec
```
減少了 0.129127 sec ，看來是可以降低執行時間，接著實驗把所有 math-toolkit.h 裡面的函式都 force inline
```
# Rendering scene
Done!
Execution time of raytracing() : 2.282104 sec
```
使用 loop unrolling + force inline 的結果與單獨使用 loop unrolling 比較
降低執行時間 **0.33512 sec** ，執行時間變為原本的 **87.2%**
從圖表上可以比較清楚看到做了 optimized 之後的時間差異
從 gprof 上可以看出剛剛 math-toolkit.h 裡面的函式都已經被展開了
```shell
Flat profile:
Each sample counts as 0.01 seconds.
% cumulative self self total
time seconds sec onds calls s/call s/call name
31.32 0.65 0.65 13861875 0.00 0.00 rayRectangularIntersection
18.70 1.03 0.39 13861875 0.00 0.00 raySphereIntersection
15.05 1.34 0.31 2110576 0.00 0.00 compute_specular_diffuse
9.23 1.53 0.19 2110576 0.00 0.00 localColor
8.26 1.70 0.17 1048576 0.00 0.00 ray_color
7.04 1.85 0.15 4620625 0.00 0.00 ray_hit_object
4.37 1.94 0.09 1048576 0.00 0.00 rayConstruction
1.94 1.98 0.04 1241598 0.00 0.00 refraction
1.46 2.01 0.03 1241598 0.00 0.00 reflection
0.97 2.03 0.02 2520791 0.00 0.00 idx_stack_top
0.49 2.04 0.01 1241598 0.00 0.00 protect_color_overflow
0.49 2.05 0.01 1204003 0.00 0.00 idx_stack_push
0.49 2.06 0.01 1048576 0.00 0.00 idx_stack_init
0.24 2.06 0.01 113297 0.00 0.00 fresnel
0.00 2.06 0.00 2558386 0.00 0.00 idx_stack_empty
0.00 2.06 0.00 37595 0.00 0.00 idx_stack_pop
```
## OpenMP
參考 [OpenMP简易教程(pdf) ](https://drive.google.com/file/d/0B4WZ6ihm_C7zYkdvNUJyYlJFRG8/view)
#pragma omp 指令 [子句[子句]...]
- parallel for 表示接下來的for 迴圈將被並行執行
- private() 可以把變數宣告爲私有變數，讓其他執行緒無法存取，可以解決race condition的問題
- lastprivate 可以把變數結束後繼續取用
首先先修改 Makefile，讓它可以執行 openMP
```
ifeq ($(strip $(OPENMP)),1)
PROF_FLAGS = -fopenmp
CFLAGS += $(PROF_FLAGS)
LDFLAGS += $(PROF_FLAGS)
endif
```
接著根據 call function 裡面看到 raytracing 是大部分程式的進入點，而且裡面大部分程式碼使用 for 迴圈，使用 openMP 應該會有一些改變
stk, d, object_color 在 raytracing 迴圈裡面的 ray_color 裡面有改變值
為了防止 race condition 把他們設為 private
在 for 的最外面加上這句
`#pragma omp parallel for private(stk, d, object_color)`
時間上從 2.282104 sec 降到了 1.114757 sec
```
# Rendering
Done!
Execution time of raytracing() : 1.114757 sec
Verified OK
```
openMP 裡面有個 schedule 語法可以用，有四種參數可以選擇，實際上三種，第四種是根據系統設定為前三種的其中一個
- static
- 如果沒有使用 schedule 預設會加上 schedule(static)，他的方法是把所有的迴圈平均分給每一個子程序
- dynamic
- 這個是動態的分配
- guided
- 這個則是越前面接觸到的子程序處理越多迴圈，逐漸遞減
剛剛沒加 schedule 時就是 static 了
Execution time of raytracing() : 1.114757 sec
使用 dynamic
Execution time of raytracing() : 0.964898 sec
使用 guided
Execution time of raytracing() : 0.975975 sec
使用 dynamic 參數或 guided 相差不遠，不過都比沒加時快大約 0.05 sec
最後選擇使用 dynamic
## 參考資料
[B02: raytracing](https://hackmd.io/s/HyuBWDwYl#)
[Enhance raytracing program](https://embedded2016.hackpad.com/ep/pad/static/f5CCUGMQ4Kp)
Sign in with Wallet
Connect another wallet