# 2016q3 Homework1 (raytracing)
contributed by <`TempoJiJi`>
###### tags: `TempoJiJi` `raytracing` `sysprog21`
### Reviewed by `SarahYuHanCheng`
* 建議圖表數值命名可以用縮寫取代代稱
## 預期目標
之前已對raytracing做過各方面的研究，但會做一次總復習，且會着重在上次未能達到的目標上。
過去的共筆：[組別共筆](https://embedded2016.hackpad.com/ep/pad/static/f5CCUGMQ4Kp), [個人共筆](https://embedded2016.hackpad.com/ep/pad/static/s8ujtGxBML2)
* 學習 gprof
* 以 gprof 指出效能瓶頸，並且著手改寫檔案 math-toolkit.h 在內的函式實做
* 善用 POSIX Thread, OpenMP, software pipelining, 以及 loop unrolling 一類的技巧來加速程式運作
* 實做SIMD
## 開發環境
* Ubuntu 16.04 LTS
* L1d cache: 32K
* L1i cache: 32K
* L2 cache: 256K
* L3 cache: 3072K
* Architecture: x86_64
* CPU op-mode(s): 32-bit, 64-bit
* Byte Order: Little Endian
* CPU(s): 4
* Model name: Intel(R) Core(TM) i5-4200U CPU @ 1.60GHz
---
測試未優化的程式效能：
```
# Rendering scene
Done!
Execution time of raytracing() : 3.338328 sec
```
利用gprof觀察程式效能及行爲，在Makefile的編譯選項裏加入 ==-pg== ，再進行編譯跟執行，就會產生一個gmon.out檔：
```clike
$ gprof raytracing gmon.out
% cumulative self self total
time seconds seconds calls s/call s/call name
24.91 0.60 0.60 69646433 0.00 0.00 dot_product
14.12 0.94 0.34 56956357 0.00 0.00 subtract_vector
10.38 1.19 0.25 13861875 0.00 0.00 rayRectangularIntersection
9.34 1.42 0.23 31410180 0.00 0.00 multiply_vector
8.72 1.63 0.21 10598450 0.00 0.00 normalize
7.06 1.80 0.17 4620625 0.00 0.00 ray_hit_object
4.98 1.92 0.12 17836094 0.00 0.00 add_vector
4.57 2.03 0.11 13861875 0.00 0.00 raySphereIntersection
4.15 2.13 0.10 17821809 0.00 0.00 cross_product
2.49 2.19 0.06 1048576 0.00 0.00 ray_color
2.08 2.24 0.05 1048576 0.00 0.00 rayConstruction
```
這裏可以看到dot_product跟subtrace_vector是最花時間的地方，程式執行期間總共被呼叫了接近7前萬次(dot_product)。
## 所以先從math-toolkit.h開始觀察：
### Loop Unrolling
優點：
* 分支預測（branch predictor）失敗減少。
* 如果循環體內語句沒有數據相關，增加了並發執行的機會。
* 可以在執行時動態循環展開。
缺點：
* 降低可讀性
```
static 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;
}
```
這裏可以看到利用迴圈來計算dot_product，而迴圈會有branch的情況發生，導致效能不好，所以就將迴圈拆開(loop unrolling)：
```clike=
double dp = 0.0;
dp += v1[0] * v2[0];
dp += v1[1] * v2[1];
dp += v1[2] * v2[2];
return dp;
```
```
# Rendering scene
Done!
Execution time of raytracing() : 2.999242 sec
```
可以看到只改一個dot_product時間就快了近0.4秒左右。
---
### Force Inline
inline是向編譯器提出“建議”，把inline的函數在函數位置直接展開（減輕系統負擔(overhead)），編譯器會對比兩者執行時間後選擇執行inline與否。
優點：
* 減少function call
在fucntion後面加上 __forceinline
```clike=
static inline __forceinline
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;
}
```
編譯加上 -D__forceinline="__attribute__((always_inline))" 進行編譯：
```
# Rendering scene
Done!
Execution time of raytracing() : 3.059393 sec
```
時間比原本的快了0.2秒左右，接下來用gprof觀察function call：
```
% cumulative self self total
time seconds seconds calls s/call s/call name
34.98 1.00 1.00 13861875 0.00 0.00 rayRectangularIntersection
22.38 1.64 0.64 13861875 0.00 0.00 raySphereIntersection
10.84 1.95 0.31 2110576 0.00 0.00 compute_specular_diffuse
9.44 2.22 0.27 2110576 0.00 0.00 localColor
7.17 2.43 0.21 1048576 0.00 0.00 ray_color
5.42 2.58 0.16 4620625 0.00 0.00 ray_hit_object
4.20 2.70 0.12 1048576 0.00 0.00 rayConstruction
```
可以看到math_tookit.h裏的function已經不見了
---
### Macro
優點：
* 執行速度快，沒有堆疊的 push 和 pop 動作的需要，減少時間的耗損
缺點：
* 巨集被呼叫多次以後，會耗損存放及使用大量的記憶體空間
將math_tookit.h裏的function改爲Macro來進行計算，這樣就能減少function call(stack frame的push,pop等行爲)所帶來的時間花費
```clike=
#define DOT(a,b) ((a[0]*b[0])+(a[1]*b[1])+(a[2]*b[2]))
```
```
# Rendering scene
Done!
Execution time of raytracing() : 2.741537 sec
```
這裏可以看到時間比loop unrolling快了近0.2秒左右，因此決定將math_tookit.h裏的花費較大的function都改爲Macro argument
根據gprof的結果，可以知道哪個function的花費最大，因此將它們都改爲Macro argument即可
```clike
#define DOT(a,b) ((a[0]*b[0])+(a[1]*b[1])+(a[2]*b[2]))
#define SUB_VEC(a,b,c) (c[0]=a[0]-b[0], c[1]=a[1]-b[1], c[2]=a[2]-b[2])
#define MVEC(a,b,out) (out[0]=a[0]*(b), out[1]=a[1]*(b), out[2]=a[2]*(b))
#define ADD(a,b,c) (c[0]=a[0]+b[0], c[1]=a[1]+b[1], c[2]=a[2]+b[2])
#define CDOT(a,b,out) (out[0]=(a[1]*b[2])-(a[2]*b[1]),out[1]=(a[2]*b[0])-(a[0]*b[2]),out[2]=(a[0]*b[1])-(a[1]*b[0]))
```
```
# Rendering scene
Done!
Execution time of raytracing() : 1.634365 sec
```
可以看到只改了math_tookit.h整個程式的效能就快了接近1倍，可見程式的效能瓶頸真的是在math_tookit.h裏。
---
## 實做PThread 跟 OpenMP
### OpenMP
首先來實做OpenMP，在for迴圈上加上：
```
#pragma omp parallel for num_threads(4) \
private(x), private(y)
```
num_threads是要建立的執行緒數量。private可以確保變數在各個執行緒裏是獨立的，並不會因爲某個執行緒改變了變數，而影響到其它執行緒。
在raytracing的兩層for迴圈上加上：
```
#pragma omp parallel for num_threads(4) \
private(stk), private(d), \
private(object_color)
for (int j = 0 ; j < 512; j++) {
for (int i = 0; i < 512; i++) {
double r = 0, g = 0, b = 0;
/* MSAA */
```
這裏將stk、d、object_color設爲private，是因爲這3個的值是會在各個執行緒裏進行更動。
最後要記得 ==#include<omp.h>== ， 以及在編譯選項中加上 ==-fopenp==
執行結果：
```
num_thread(4)
# Rendering scene
Done!
Execution time of raytracing() : 1.738263 sec
```
不同的num_thread比較圖：
---
### POSIX Thread
當function的參數超過一個，在建立pthread的時候需要將所有參數打包起來，才能傳送給function：
```clike=
typedef struct __ARG {
uint8_t *pixels;
color background;
rectangular_node rectangulars;
sphere_node spheres;
light_node lights;
const viewpoint *View;
int start_j;
point3 u, v, w, d;
} arg;
```
將圖片分成不同的等份交給不同的執行緒去進行，這裏我會先將row分成4個等份，再用4個執行緒去執行：
```clike=
/* (*data).start_j 爲每個執行緒所執行的起點 */
for (int j = (*data).start_j ; j < 512; j+=MAXX) {
for (int i = 0; i < 512; i++) {
double r = 0, g = 0, b = 0;
/* MSAA */
...
```
執行結果：
```
# Rendering scene
Done!
Execution time of raytracing() : 1.603646 sec
```
不同thread數量的比較圖：
由上圖可得知，thread的數量越多，不代表程式效能越好。
---
## 最佳優化，合並所有方法
合並所有方法，再跟不同的編譯優化做對比：
Sign in with Wallet
Connect another wallet