# HW1-Raytracing
###### tags: `Miyavi-Chen`
## 開發環境
cpu:
```clike=
$ 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
型號： 142
Model name: Intel(R) Core(TM) i5-7200U CPU @ 2.50GHz
製程： 9
CPU MHz： 446.594
CPU max MHz: 3100.0000
CPU min MHz: 400.0000
BogoMIPS: 5400.00
虛擬： VT-x
L1d 快取： 32K
L1i 快取： 32K
L2 快取： 256K
L3 快取： 3072K
NUMA node0 CPU(s): 0-3
```
kernel:
```
$ uname -a
Linux miyavi-desktop 4.8.0-39-generic #42~16.04.1-Ubuntu SMP Mon Feb 20 15:06:07 UTC 2017 x86_64 x86_64 x86_64 GNU/Linux
```
## 作業說明
* `make clean` 再利用`make PROFILE=1` complile 可以在程式進去跟離開加一些做統計的code(-gp檔)
## 學習清單
- [ ]gprof
- [x]Graphviz
- [x]loop unrolling
- [x]Force Inline
- [x]OpenMP
- [ ]Pthread
## 開始前準備
* 檢圖可用 eog 或 gimp [file name]
* 工具安裝
```clike=
$ sudo apt-get install graphviz
$ sudo apt-get install imagemagick
```
* `convert out.ppm out.png` 可以轉換圖檔
## Graphviz
可以把gprof產生的數據透過Graphviz產生容易懂的圖表.
但是Graphviz需要特定格式如下：
* dot 主要用在有向圖
* neato 基於spring-model(又稱force-based)算法
* twopi 徑向步圖
* circo 圓環布圖
* fdp 用在無向圖
#### Install Graphviz
`$ sudo apt-get install graphviz`
#### install gprof2dot
```
$sudo apt install python python-pip
$sudo pip install --upgrade pip
$sudo pip install gprof2dot
```
從[ gprof、gprof2dot.py、dot使用方法简介 ](https://casatwy.com/shi-yong-dotyu-yan-he-graphvizhui-tu-fan-yi.html)知道下面CMD來產生call graph 之有向圖
`gprof ./raytracing | gprof2dot -n0 -e0 | dot -T png -o output.png
`
## 還沒優化前
* 直接編譯然後執行
```
$make
$./raytracing
# Rendering scene
Done!
Execution time of raytracing() : 2.874858 sec
```
* 使用gprof分析
* 編譯加執行
```
$make clean
$make PROFILE=1
$./raytracing
$gprof ./raytracing | less
# Rendering scene
Done!
Execution time of raytracing() : 5.920379 sec
```
* 結果：想辦法減少前面幾項高%的時間/呼叫次數
```
Flat profile:
Each sample counts as 0.01 seconds.
% cumulative self self total
time seconds seconds calls s/call s/call name
23.88 0.63 0.63 56956357 0.00 0.00 subtract_vector
19.33 1.14 0.51 69646433 0.00 0.00 dot_product
8.34 1.36 0.22 17821809 0.00 0.00 cross_product
7.20 1.55 0.19 13861875 0.00 0.00 rayRectangularIntersection
6.82 1.73 0.18 10598450 0.00 0.00 normalize
6.63 1.91 0.18 17836094 0.00 0.00 add_vector
6.06 2.07 0.16 31410180 0.00 0.00 multiply_vector
6.06 2.23 0.16 13861875 0.00 0.00 raySphereIntersection
4.74 2.35 0.13 1048576 0.00 0.00 ray_color
3.03 2.43 0.08 4620625 0.00 0.00 ray_hit_object
1.90 2.48 0.05 4221152 0.00 0.00 multiply_vectors
......
```
## 優化法一：loop unrolling
* 一種將loop展開用空間換取時間的方法
* 將`math-toolkit.h`中剛剛前面用gprof分析較高%的functions的loop 展開.
* 如將subtract_vector中loop 展開
```
33 void subtract_vector(const double *a, const double *b, double *out)
34 {
35 ¦ for (int i = 0; i < 3; i++)
36 ¦ ¦ ¦ out[i] = a[i] - b[i];
37 }
```
* Loop unrolling 後
```
void subtract_vector(const double *a, const double *b, double *out)
34 {
35
37 ¦ out[0]= a[0] - b[0];
38 ¦ out[0]= a[1] - b[1];
39 ¦ out[0]= a[2] - b[2];
}
```
* 結果可以看到減法/點積/外積的呼叫次數都大幅降. 執行時間從2.8->1.1s 成功降低執行時間
```
# Rendering scene
Done!
Execution time of raytracing() : 1.101514 sec
Flat profile:
Each sample counts as 0.01 seconds.
% cumulative self self total
time seconds seconds calls ms/call ms/call name
52.03 0.39 0.39 3145730 0.00 0.00 cross_product
10.67 0.47 0.08 1 80.05 745.45 raytracing
9.34 0.54 0.07 10485760 0.00 0.00 subtract_vector
8.67 0.61 0.07 9437184 0.00 0.00 dot_product
4.00 0.64 0.03 1048579 0.00 0.00 normalize
4.00 0.67 0.03 1048576 0.00 0.00 rayConstruction
2.67 0.69 0.02 3145728 0.00 0.00 raySphereIntersection
2.00 0.70 0.02 4194304 0.00 0.00 add_vector
1.33 0.71 0.01 4194304 0.00 0.00 multiply_vector
1.33 0.72 0.01 3145728 0.00 0.00 rayRectangularIntersection
1.33 0.73 0.01 1048576 0.00 0.00 ray_color
```
## 優化法二：Force inline
* inline 原來在被關閉編譯器最佳化 -O0 後是不會被執行的，所以我們加入讓編譯器可以強執執行 inline function 的程式碼`__attribute__((always_inline)) `強制inlince進程式碼進而減少函數調用的呼叫
* 結果真的變快了不少
```
# Rendering scene
Done!
Execution time of raytracing() : 3.496136 sec
```
* 原本幾千萬次的呼叫項都不見了
```
Flat profile:
Each sample counts as 0.01 seconds.
% cumulative self self total
time seconds seconds calls s/call s/call name
35.56 0.91 0.91 13861875 0.00 0.00 rayRectangularIntersection
21.49 1.46 0.55 13861875 0.00 0.00 raySphereIntersection
11.72 1.76 0.30 2110576 0.00 0.00 compute_specular_diffuse
8.40 1.98 0.22 1048576 0.00 0.00 ray_color
8.21 2.19 0.21 4620625 0.00 0.00 ray_hit_object
7.42 2.38 0.19 2110576 0.00 0.00 localColor
2.74 2.45 0.07 1048576 0.00 0.00 rayConstruction
0.78 2.47 0.02 2520791 0.00 0.00 idx_stack_top
```
## 優化法三：OpenMP
* 觀念：OpenMP是一個跨平台的多執行緒實現，主執行緒(順序的執行指令)生成一系列的子執行緒，並將任務劃分給這些子執行緒進行執行。這些子執行緒並列的執行，由執行時環境將執行緒分配給不同的處理器。
* 語法格式：
像下面用到的`for/ parallel/ private` 都是`directive`
```
#pragma omp <directive> [clause[[,] clause] ...]
```
* Makefile 需要改一下,且include omp.h
```
CC ?= gcc
CFLAGS = \
-std=gnu99 -Wall -O0 -g -fopenmp
LDFLAGS = \
-lm -fopenmp
```
* raytracing.c加入下面程式碼在for前 . 因為d,stk,object_color 再raytracing 這個function的for 回圈中大家共用,使用private 使之再各執行緒都有一份
```
#pragma omp parallel for private( d, stk, object_color) num_threads(THREAD_CNT)\
shared(height,width,factor)
for (int j = 0; j < height; j++) {
for (int i = 0; i < width; i++) {
...
```
`num_threads(THREAD_CNT)`代表要用多少執行緒來跑
`private( d, stk, object_color)`代表各個執行續複製一份d,stk,object_color 變數
`shared(height,width,factor)`代表height,width,factor為共用
* 結果inline+openMP. 比單純inline又更快,呼叫次數又更少了
```
# Rendering scene
Done!
Execution time of raytracing() : 2.282882 sec
Flat profile:
Each sample counts as 0.01 seconds.
% cumulative self self total
time seconds seconds calls s/call s/call name
36.40 1.19 1.19 8503296 0.00 0.00 rayRectangularIntersection
26.00 2.04 0.85 8447223 0.00 0.00 raySphereIntersection
11.93 2.43 0.39 1372878 0.00 0.00 localColor
8.26 2.70 0.27 1310226 0.00 0.00 compute_specular_diffuse
4.59 2.85 0.15 2785719 0.00 0.00 ray_hit_object
4.28 2.99 0.14 558194 0.00 0.00 ray_color
2.75 3.08 0.09 818031 0.00 0.00 reflection
2.45 3.16 0.08 534180 0.00 0.00 rayConstruction
0.92 3.19 0.03 1609022 0.00 0.00 idx_stack_top
0.92 3.22 0.03 770567 0.00 0.00 refraction
```
* 參考資料
[Wiki_OpenMP](https://zh.wikipedia.org/zh-hk/OpenMP)
[簡易的程式平行化方法－openmp（一）簡介](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/)
[laochanlam 大](https://hackmd.io/s/B1hlfxl9e#)
[hugikun999 大](https://hackmd.io/s/HyHhgcv6#)
## 優化法四：POSIX Thread for Parallel Programming
* 有點忘了用法,複習一下[PThread](https://computing.llnl.gov/tutorials/pthreads/)
* 考慮要點：
* What type of parallel programming model to use?-> Raytracing function 裡的for loop.
* Problem partitioning-> 將height 切割成core數個partition
* Data dependencies-> Data 間為Indep.
* race conditions-> 因為data indep.所以沒race condition
* 使用方法：
* 建一個struct 用來存原本要傳入的參數
* 再使用pthread_create()時用一個該strcut pointer傳入給每個partition必要參數
* 最後等threads都作完後,使用pthread_joint合併
* TBD
Sign in with Wallet
Connect another wallet