# 2016q3 Homework1 (raytracing)
contributed by <`shelly4132`>

### Reviewed by `HaoTse`
- 可以再嘗試其他優化方法，例如 SIMD、pthread等等
- `git add` 時可以避免上傳執行結果的圖片
- 可以使用 **gnuplot** 一類的工具繪製出效能比較圖表

## 開發環境
* 作業系統：Ubuntu 16.04 LTS
* CPU：Intel(R) Core(TM) i5-4200U CPU @ 1.60GHz
* Cache：
* L1d cache: 32K
* L1i cache: 32K
* L2 cache: 256K
* L3 cache: 3072K

## 事前準備
安裝一些必要的東西

$ sudo apt-get update
$ sudo apt-get install graphviz
$ sudo apt-get install imagemagick

先clone檔案下來執行看看

$ git clone https://github.com/shelly4132/raytracing 
$ cd raytracing
$ make
$ ./raytracing

結果

# Rendering scene
Done!
Execution time of raytracing() : 3.258902 sec

將O0改成Ofast，真的很快啊

# Rendering scene
Done!
Execution time of raytracing() : 0.281827 sec

可使用eog開啟圖片

或是將檔案轉換成png的格式

圖片


## 光影追蹤程式

先執行 ```$ make clean```把剛剛產生的執行檔刪掉

接著執行 ```$ make PROFILE=1```

cc -std=gnu99 -Wall -O0 -g -pg -c -o objects.o objects.c
cc -std=gnu99 -Wall -O0 -g -pg -c -o raytracing.o raytracing.c
cc -std=gnu99 -Wall -O0 -g -pg -c -o main.o main.c
cc -o raytracing objects.o raytracing.o main.o -lm -pg

#### gprof
-pg這個指令可以去追蹤程式執行的時間、幫助我們找到最耗時的function，以及每個function被呼叫的次數等等。

再執行一次可以發現因為多了追蹤程式的時間所以總體執行時間變長了。

# Rendering scene
Done!
Execution time of raytracing() : 7.058977 sec

接下來就可以執行以下命令看結果

$ gprof ./raytracing | less

從以下可看出最耗時的為subtract_vector、dot_product和multiply_vector等function，因此優化應該從這前幾名開始著手。

Each sample counts as 0.01 seconds.
% cumulative self self total
time seconds seconds calls s/call s/call name
20.88 0.58 0.58 56956357 0.00 0.00 subtract_vector
20.88 1.16 0.58 69646433 0.00 0.00 dot_product
10.08 1.44 0.28 31410180 0.00 0.00 multiply_vector
8.10 1.67 0.23 17836094 0.00 0.00 add_vector
7.20 1.87 0.20 4620625 0.00 0.00 ray_hit_object
6.66 2.05 0.19 13861875 0.00 0.00 rayRectangularIntersection
6.66 2.24 0.19 13861875 0.00 0.00 raySphereIntersection
6.12 2.41 0.17 17821809 0.00 0.00 cross_product
6.12 2.58 0.17 10598450 0.00 0.00 normalize
2.16 2.64 0.06 1 0.06 2.78 raytracing
1.44 2.68 0.04 1048576 0.00 0.00 ray_color
1.08 2.71 0.03 1048576 0.00 0.00 rayConstruction
0.90 2.73 0.03 3838091 0.00 0.00 length
0.36 2.74 0.01 4221152 0.00 0.00 multiply_vectors
0.36 2.75 0.01 2558386 0.00 0.00 idx_stack_empty

### 開始優化

### 方法一：force inline


在math-toolkit.h裡可以看到「static inline」這個關鍵字，拆開來看的話
#### static:
一個static函式表示它定義的範圍是local的，只會在這個檔案被看到。


#### inline:
在呼叫函式時會需要分配記憶空間因而需要額外的資源負擔，所以有些小函式我們可以「建議」編譯器將他設定為「行內函式」（Inline function），如果建議被採納，則該函式會自動在呼叫點展現為程式碼，行內函式建議可以直接定義於表頭檔案中。

所以我們可以把「static inline」理解為一個static的函式被加上了inline的屬性。
另外，如果編譯器優化設定為-O0，必須加上__attribute__((always_inline))強制展開，inline才會有作用。

於是我便在所有inline後面加上__attribute__((always_inline))
然後執行！

# Rendering scene
Done!
Execution time of raytracing() : 4.085727 sec

非常驚人的效果，執行時間一下子就掉了3秒左右！

### 方法二：Loop unrolling
這個方法顧名思義就是把迴圈展開，降低branch miss，雖然此法可能會造成程式的可讀性降低，和程式碼變得很冗長，但在一定限度內的展開迴圈的確是優化的好辦法。


以add_vector這個function來看，原本是i從0到2的迴圈，我直接把迴圈拿掉，把全部的運算寫出來。
#### 未展開

static inline __attribute__((always_inline))
void add_vector(const double *a, const double *b, double *out)
{
for (int i = 0; i < 3; i++)
out[i] = a[i] + b[i];
}

#### 展開後

static inline __attribute__((always_inline))
void add_vector(const double *a, const double *b, double *out)
{
out[0] = a[0] + b[0];
out[1] = a[1] + b[1];
out[2] = a[2] + b[2];
}

執行後可以發現時間又降低了大概1秒左右

# Rendering scene
Done!
Execution time of raytracing() : 3.141350 sec

現在我們再用gprof看一遍，可以發現subtract_vector、dot_product和multiply_vector那些function的排名都掉到很後面了，而rayRectangularIntersection、raySphereIntersection等等則變成比例較高的。

Each sample counts as 0.01 seconds.
% cumulative self self total
time seconds seconds calls s/call s/call name
37.19 0.71 0.71 13861875 0.00 0.00 rayRectangularIntersection
21.47 1.12 0.41 13861875 0.00 0.00 raySphereIntersection
9.43 1.30 0.18 2110576 0.00 0.00 localColor
9.43 1.48 0.18 10598450 0.00 0.00 normalize
6.28 1.60 0.12 4620625 0.00 0.00 ray_hit_object
4.19 1.68 0.08 2110576 0.00 0.00 compute_specular_diffuse
4.19 1.76 0.08 1048576 0.00 0.00 ray_color
3.14 1.82 0.06 1048576 0.00 0.00 rayConstruction
2.09 1.86 0.04 1241598 0.00 0.00 reflection
1.05 1.88 0.02 1 0.02 1.91 raytracing
0.52 1.89 0.01 2520791 0.00 0.00 idx_stack_top
0.52 1.90 0.01 1241598 0.00 0.00 protect_color_overflow
0.52 1.91 0.01 1241598 0.00 0.00 refraction
0.00 1.91 0.00 2558386 0.00 0.00 idx_stack_empty
0.00 1.91 0.00 1204003 0.00 0.00 idx_stack_push
0.00 1.91 0.00 1048576 0.00 0.00 idx_stack_init
0.00 1.91 0.00 113297 0.00 0.00 fresnel
0.00 1.91 0.00 37595 0.00 0.00 idx_stack_pop

### 方法三：OpenMP
從上面的結果我們看到rayRectangularIntersection、raySphereIntersection所佔耗時間最多的2個，而他們剛好都是被raytracing.c裡的raytracing()所間接呼叫的，又正好raytracing()裡每個pixel是可以獨自運算的，所以我們可以對他做平行處理增加效能。

#### OpenMP簡介
OpenMP（Open Multi-Processing）是一套支援跨平台共享記憶體方式的多執行緒並行的編程API，使用C,C++和Fortran語言，可以在大多數的處理器體系和作業系統中執行，包括Solaris, AIX, HP-UX, GNU/Linux, Mac OS X, 和Microsoft Windows。包括一套編譯器指令、庫和一些能夠影響執行行為的環境變數。

* 編譯時要記得在Makefile中的CFLAGS加上-fopenmp,LDFLAGS加上-lgomp

一開始自己在raytracing()的for迴圈上加了下面這一行

#pragma omp parallel for private(stk), private(object_color), private(d)

但執行出來的時間幾乎沒有減少

# Rendering scene
Done!
Execution time of raytracing() : 3.070660 sec

後來才發現原來我忘記去設定thread的數量

#pragma omp parallel for num_threads(50) private(stk), private(object_color), private(d)

開了50個thread後時間就比之前又降了1秒左右

# Rendering scene
Done!
Execution time of raytracing() : 1.959896 sec

把gprof拿掉之後，距離Ofast最佳化的時間還有一段差距

# Rendering scene
Done!
Execution time of raytracing() : 0.979613 sec

#### 語法說明
* for：用在 for 迴圈之前，會將迴圈平行化處理。（註：迴圈的 index 只能是 int）
* private：讓每個執行緒中，都有一份變數的複本，以免互相干擾。
* num_threads：設定平行化時執行緒的數量。




## 參考資料
* [C語言inline詳細講解](http://www.cnblogs.com/cnmaizi/archive/2011/01/19/1939686.html)
* [彥寬學長](https://embedded2016.hackpad.com/2016q1-Homework-2A-wOu40KzMaIP)
* [陳品睿學長](https://embedded2016.hackpad.com/2016q1-Homework-2A-bLGQtRraTES)
* [vvn](https://hackmd.io/MYQwpgnARsBMUFoBmAWAjADgSsBmLGSuArAgAwDsFKAJmmAGxJgbFA==?view#2016q3-homework1-raytracing)
* [勃興](https://hackmd.io/s/BygM4qP6#2016q3-homework1-raytracing)
* [簡易的程式平行化－OpenMP（五） 變數的平行化](https://kheresy.wordpress.com/2006/09/22/%E7%B0%A1%E6%98%93%E7%9A%84%E7%A8%8B%E5%BC%8F%E5%B9%B3%E8%A1%8C%E5%8C%96%EF%BC%8Dopenmp%EF%BC%88%E4%BA%94%EF%BC%89-%E8%AE%8A%E6%95%B8%E7%9A%84%E5%B9%B3%E8%A1%8C%E5%8C%96/)