# 2016q3 Homework1 (raytracing)
contributed by <`HaoTse`>
---
### Reviewed by `shelly4132`
- 可以利用 **gnuplot** 繪製出效能比較圖表
- 可將POSIX Thread的方法實作出來
---
## 開發工具
- graphviz: 畫示意圖
- imagemagick: 格式轉換
```shell
$ sudo apt-get update
$ sudo apt-get install graphviz
$ sudo apt-get install imagemagick
```
----
### gprof
- GNU的工具
- 使用方式
- 編譯時加上`-pg`的參數，編譯器會在各函數中加入mcount函數
- 執行產生gmon.out
- `$ gprof -b raytracing gmon.out | less`
> 由於輸出訊息多，`$ less` 使我們可以使用上下鍵看訊息。[name=鄭皓澤]
- gprof v.s perf
**perf top** 的原理是每隔一段時間採樣一次，最後根據這些資料輸出,因此採樣的頻率可能會造成結果的不同。
---
## 效能分析
首先不開啟gprof，得到結果如下
```
# Rendering scene
Done!
Execution time of raytracing() : 3.338670 sec
```
接著使用`$ make PROFILE=1`重新編譯
> 注意得先做`$ make clean`
```
# Rendering scene
Done!
Execution time of raytracing() : 6.912961 sec
```
兩者對照可以看出gprof對速度的影響。
----
### gmon.out
`$ gprof -b raytracing gmon.out | less`
```shell=
% cumulative self self total
time seconds seconds calls s/call s/call name
21.79 0.54 0.54 69646433 0.00 0.00 dot_product
20.58 1.05 0.51 56956357 0.00 0.00 subtract_vector
12.91 1.37 0.32 31410180 0.00 0.00 multiply_vector
9.68 1.61 0.24 13861875 0.00 0.00 raySphereIntersection
8.47 1.82 0.21 13861875 0.00 0.00 rayRectangularIntersection
6.86 1.99 0.17 10598450 0.00 0.00 normalize
4.44 2.10 0.11 17836094 0.00 0.00 add_vector
4.03 2.20 0.10 17821809 0.00 0.00 cross_product
2.42 2.26 0.06 4620625 0.00 0.00 ray_hit_object
2.02 2.31 0.05 1048576 0.00 0.00 ray_color
1.61 2.35 0.04 4221152 0.00 0.00 multiply_vectors
1.21 2.38 0.03 2520791 0.00 0.00 idx_stack_top
1.01 2.41 0.03 1048576 0.00 0.00 rayConstruction
0.81 2.43 0.02 2110576 0.00 0.00 localColor
0.81 2.45 0.02 1241598 0.00 0.00 refraction
0.40 2.46 0.01 2110576 0.00 0.00 compute_specular_diffuse
0.40 2.47 0.01 1241598 0.00 0.00 reflection
0.40 2.48 0.01 1 0.01 0.01 delete_sphere_list
0.20 2.48 0.01 1 0.01 0.01 calculateBasisVectors
0.00 2.48 0.00 3838091 0.00 0.00 length
0.00 2.48 0.00 2558386 0.00 0.00 idx_stack_empty
0.00 2.48 0.00 1241598 0.00 0.00 protect_color_overflow
0.00 2.48 0.00 1204003 0.00 0.00 idx_stack_push
0.00 2.48 0.00 1048576 0.00 0.00 idx_stack_init
0.00 2.48 0.00 113297 0.00 0.00 fresnel
0.00 2.48 0.00 37595 0.00 0.00 idx_stack_pop
0.00 2.48 0.00 3 0.00 0.00 append_rectangular
0.00 2.48 0.00 3 0.00 0.00 append_sphere
0.00 2.48 0.00 2 0.00 0.00 append_light
0.00 2.48 0.00 1 0.00 0.00 delete_light_list
0.00 2.48 0.00 1 0.00 0.00 delete_rectangular_list
0.00 2.48 0.00 1 0.00 0.00 diff_in_second
0.00 2.48 0.00 1 0.00 2.47 raytracing
0.00 2.48 0.00 1 0.00 0.00 write_to_ppm
```
前三名dot_product、subtract_vector、multiply_vector都在math-toolkit.h這個檔案中，因此我們首先著手對它做優化。
---
## 優化方法1： force inline function
開啟math-toolkit.h後，最明顯的部份就是**static inline**，可是這次我們要求不使用編譯器最佳化，因此使用`__attribute__((always_inline))`強制開啟inline。
先將前面提到的3個最花時間的function加上force inline。
----
- 執行結果
```
# Rendering scene
Done!
Execution time of raytracing() : 4.771009 sec
```
執行時間從 6.912961sec下降至 4.771009sec。
----
- gprof輸出
```
% cumulative self self total
time seconds seconds calls s/call s/call name
32.06 1.00 1.00 13861875 0.00 0.00 rayRectangularIntersection
22.77 1.71 0.71 13861875 0.00 0.00 raySphereIntersection
8.66 1.98 0.27 10598450 0.00 0.00 normalize
7.70 2.22 0.24 2110576 0.00 0.00 compute_specular_diffuse
6.41 2.42 0.20 17836094 0.00 0.00 add_vector
5.45 2.59 0.17 17821809 0.00 0.00 cross_product
3.85 2.71 0.12 4620625 0.00 0.00 ray_hit_object
3.53 2.82 0.11 2110576 0.00 0.00 localColor
2.89 2.91 0.09 1048576 0.00 0.00 ray_color
2.24 2.98 0.07 1048576 0.00 0.00 rayConstruction
1.28 3.02 0.04 1241598 0.00 0.00 reflection
0.96 3.05 0.03 4221152 0.00 0.00 multiply_vectors
0.96 3.08 0.03 1241598 0.00 0.00 refraction
0.64 3.10 0.02 3838091 0.00 0.00 length
0.32 3.11 0.01 1 0.01 0.01 delete_sphere_list
0.32 3.12 0.01 1 0.01 3.11 raytracing
```
前面最耗時的3個function也從前3名消失了。
----
將所有的inline funciotn作force inline後，花費時間明顯下降，結果如下
```
# Rendering scene
Done!
Execution time of raytracing() : 3.916428 sec
```
---
## 優化方法2： loop unrolling
在math-toolkit.h中有許多function都有for loop，因此決定再套入loop unrolling方法降低速度。
修改後得到結果如下
```
# Rendering scene
Done!
Execution time of raytracing() : 2.934387 sec
```
執行時間從 3.916428sec降至 2.934387sec。
----
## 優化方法3： OpenMP
在raytracing.c的raytracing()中有一段程式碼如下
```clike=
for (int j = 0; j < height; j++) {
for (int i = 0; i < width; i++) {
double r = 0, g = 0, b = 0;
/* MSAA */
for (int s = 0; s < SAMPLES; s++) {
idx_stack_init(&stk);
rayConstruction(d, u, v, w,
i * factor + s / factor,
j * factor + s % factor,
view,
width * factor, height * factor);
if (ray_color(view->vrp, 0.0, d, &stk, rectangulars, spheres,
lights, object_color,
MAX_REFLECTION_BOUNCES)) {
r += object_color[0];
g += object_color[1];
b += object_color[2];
} else {
r += background_color[0];
g += background_color[1];
b += background_color[2];
}
pixels[((i + (j * width)) * 3) + 0] = r * 255 / SAMPLES;
pixels[((i + (j * width)) * 3) + 1] = g * 255 / SAMPLES;
pixels[((i + (j * width)) * 3) + 2] = b * 255 / SAMPLES;
}
}
}
```
可以看出各個pixel可以獨立運算，因此想使用多執行緒的方式來試著改善程式效能，在同學的筆記中看到OpenMP這套工具，先嘗試使用看看。
----
- 使用方式
- Makefile部份改為
```
CFLAGS = \
-std=gnu99 -Wall -O0 -g -fopenmp
LDFLAGS = \
-lm -lgomp
```
- 在上述的for loop前面增加`#pragma omp parallel for`
----
### 輸出結果
```
# Rendering scene
Done!
Execution time of raytracing() : 2.306696 sec
```
原先為 2.934387sec，發現下降並不明顯。
- `#pragma omp parallel for num_threads(64) `
將thread數量指定至64條。
不過`$ make check`後發現結果**fail**，參考同學的筆記之後發現要改為
```clike
#pragma omp parallel for num_threads(64) \
private(stk) private(d) \
private(object_color)
```
因為變數 stk、d 以及 object_color 必須要透過 private clause 宣告為執行緒私有的，否則預設之下在 #pragma omp 前的變數都是 shared，會導致計算結果錯誤。成功輸出結果如下
```
# Rendering scene
Done!
Execution time of raytracing() : 1.606055 sec
```
時間下降更多了。
---
## 目標
在`-Ofast`且不開啟`-pg`的情況下，結果如下
```
# Rendering scene
Done!
Execution time of raytracing() : 0.389374 sec
```
目標為**超越電腦**。
---
## 其他方法(待實驗)
- [ ] pthread
---
## 參考資料
- [inline介紹](http://www.cnblogs.com/cnmaizi/archive/2011/01/19/1939686.html)
- [OpenMP簡介](http://angelonotes.blogspot.tw/2012/03/openmpintroduction.html)
- [勃興筆記](https://hackmd.io/s/BygM4qP6)
- [彥寬學長筆記](https://embedded2016.hackpad.com/2016q1-Homework-2A-wOu40KzMaIP)
- [品睿學長筆記](https://embedded2016.hackpad.com/2016q1-Homework-2A-bLGQtRraTES)
###### tags: `HaoTse` `sysprog21` `raytracing` `gprof` `OpenMP`
Sign in with Wallet
Connect another wallet