# 2017q1 Homework01 (raytracing)
contributed by <`hugikun999`>
### Reviewed by `yangyang95`
- 中文與英文之間要留有空格
- 文字訊息應避免使用圖片，以方便搜尋
- loop unrolling ： “展開 function 而不使用呼叫的方式” 的解釋是否有些奇怪？ [參考資料](https://zh.wikipedia.org/wiki/%E5%BE%AA%E7%8E%AF%E5%B1%95%E5%BC%80)
- force inline ： “加上 inline 通常compiler就會自動 inline” 是否正確？ [參考資料](https://dotblogs.com.tw/v6610688/2013/11/27/introduction_inline_function)
還有 sqrt() 回傳的是 **平方根**，而非方均根，兩者並不相同
- OpenMP 的部分，觀察一下 `#pragma` 該放的位置，還有記得把會改變到的變數 (stk 、 d 、 object_color) 使用 private 處理 [參考資料](https://hackmd.io/s/rkVjtkkcl)
- commit [4196911bc510cdccfc595369b4ca8ef2285fa7e6](https://github.com/hugikun999/raytracing/commit/4196911bc510cdccfc595369b4ca8ef2285fa7e6)
commit message 還是改明確一點吧，至少提到使用是 POSIX thread
## Gprof
在make時記得要加上 `CFLAGS=-pg` 和 `LDFLAGS=-pg` 兩個選項，第一個是設定編譯選項，第二個是鏈接選項。
* [Sample-Error](https://sourceware.org/binutils/docs/gprof/Sampling-Error.html#Sampling-Error)
prof 是會產生不準確的，尤其是當 multi-thread 時可能會造成重覆的 sample，只有當程式的 run-time 大於 sample-time 時才可以確保 gprof 是精準的分析。
### commond
(1)
```shell
$ gprof -p ./raytracing
```
只輸出function的時間開銷表。
(2)
```shell
$ gprof -q ./raytracing
```
只輸出call graph
(3)
```shell
$ gprof -b ./raytracing
```
略過中間的解釋
## [graphviz](http://www.openfoundry.org/tw/foss-programs/8820-graphviz-)
將gprof產生的結果數據透過graphviz產生出容易觀看的圖表。graphviz的檔案需要特定格式(ex:dot、neato、fdp)，會需要用到[gprof2dot](https://github.com/jrfonseca/gprof2dot)將gprof產生的檔案轉成dot的形式。
### install gprof2dot
安裝的時後會用到[pip](https://pip.pypa.io/en/stable/installing/),所以要先安裝python。
要注意這裡不可以下```$ sudo apt install pip```，會找不到東西安裝。
```
$sudo apt install python python-pip
$sudo pip install --upgrade pip
$sudo pip install gprof2dot
```
### command
在[這個網站](https://github.com/jrfonseca/gprof2dot)中有提供不同情況下使用的command，但是其中gprof給的command執行後會出現command not found，因此我改用下面的command。
```
$ gprof ./raytracing | gprof2dot | dot -T png -o output.png
```
## static function
```shell
static void f1()
{
std::cout << "f1()" << std::endl;
}
void f2()
{
std::cout << "f2()" << std::endl;
}
```
這兩個 function 的差別在於有沒有宣告時加上 `static`，f1() 只能被這個[compilation Unit](https://www.cs.auckland.ac.nz/references/unix/digital/AQTLTBTE/DOCU_015.HTM)所看見，f2() 會被不同的 compilation Uint 看見。
同一個.h檔在被多個.c檔引用，在 compile 時會將.h檔展開，如果在.h檔內定義了一個 function 的實作最後將所有.o檔一起編成執行檔時就會發生重覆定義的問題，因此在.h檔內通常不會去定義一個 function 的實作而是只有宣告 function，在.c中才去定義實作的部份。另外一個方法是可以利用 `extern` ，聲明變數會在其他的位置被定義，這個位置可能是在同一份文件之中，或是在其他文件之中，需要注意的是在使用 `extern` 時不可賦值，否則將被視為重覆定義。
## Raytracing
### file detail
```C
typedef double point3[3];
```
用```point3```來宣告的東西是一個具有三個element的指標。
```C
struct object_fill{}
```
紀錄RGB、反光率之類的object。
```
models.inc
```
這個檔案是一些物體和光的資料。
### 可能的優化方向
* Loop unrolling
藉由展開function而不使用呼叫的方式，可以減少花費在呼叫的時間，但是會造成程式本身的膨脹，有點類似空間換取時間的做法。
* Force inline
如果定義時加上"inline"通常compiler就會自動inline，但在這次的MAKEFILE中特別加了關閉編譯器最佳化選項 -O0，因此會須要force inline，就算關閉最佳化依然會inline。
* Pthread
* SIMD
* AVX
* openMP
### function
* inline function
效果：在定義時將前面加上inline，藉由inline可以將函式直接在main中展開，免除函式呼叫所造成的成本，從而提升效能。
注意：須要在定意時加，若在宣告時加沒有作用，且可能會造成在complier時main過度龐大。另外如果函式內含有其它複雜度高的函式，則效益不大。
```C
sqrt(double a);
```
說明：回傳a的[方均根](https://zh.wikipedia.org/wiki/%E5%B9%B3%E6%96%B9%E5%B9%B3%E5%9D%87%E6%95%B0)。
回傳值：a的方均根。
### 未優化
將原本下載的原始碼做編譯而得到的結果，可以看到這個program花最多的時間是dot_product()，藉由這張數據圖可以看到花費時間比較多的程式，可以從這些function去尋找優化方法。另外可以看到由call graph所繪出的圖，思考如何從中減少時間的方向。
```
Execution time od raytracing() : 5.309807 sec
```
>請直接將訊息(含程式碼以及輸出結果)貼上來，避免使用圖片
>[name=課程助教][color=red]
### 優化
#### establish record（失敗）
我發現normalize()和length()兩個函式其實很相近，在normalize()中已經算出length()要求的東西，所以我就把它的位置記錄起來，這樣只要比對位置一樣就不必重算。
從數據看來normalize()的％數有上升，但是花費的時間反而更多。
#### Loop unrolling
(一)
我更改了add_vector()、subtract_vector()、multiply_vectors()、multiply_vector()、dot_product()這些fuction，把能不用for迴圈做的事給拆開來寫。從perf stat可以看到instructions有減少但是cache-misses卻有所上升。
（二）
在```raytracing.c```中的raytracing()裡面有三個for迴圈，第三個for是以SAMPLE這個變數下去跑，其實它的真實值是4，所以這裡也可以拆開來跑。但是由於這次for迴圈內的行數較多拆開來會有點亂。
> 參考自heathcliffYang
force inline+loop unrolling
```
Execution time of raytracing() : 2.184140 sec
```
#### Force inline
(一)
將```math-toolkih.h```中所有有用到```inline```的地方全部替換成``` __attribute__((always_inline))```，特別住意前面是兩個```_```而不是一個。可以看到branch-misses下降很多，cache-misses卻上升了，總體時間下降了很多。另外在```make PROFILE=1```時會出現```always_inline function might not be inlinable```是指compiler不一定會做inline這個指令
（二）
在```idx_stack.h```中也有inline的部份，依照之前的改法改成```__attribute__((always_inline))```去強制inline。時間大概可以再減少0.02秒。
#### OpenMP
（一）
在```raytracing.c```中加上```#inclde <omp.h>```並在更改MAKEFILE中的參數。目前結果是變更慢且做出來的圖是錯的，應該是parallel的地方錯了。
(1)MAKEFILE
```C
CC ?= gcc
CFLAGS = \
-std=gnu99 -Wall -O0 -g -fopenmp
LDFLAGS = \
-lm -fopenmp
```
(2)raytracing.c
```C
#pragma omp parallel for
for (int j = 0; j < height; j++) {
for (int i = 0; i < width; i++) {
double r = 0, g = 0, b = 0;
/* MSAA */
＃pragma omp parallel for
for (int s = 0; s < SAMPLES; s++) {
idx_stack_init(&stk);
.
.
.
.
```
發現在上面的code中有r、g、b，在其中會分別歸0，而若分下去做可能會造成存取上的問題。
（二）
嘗試將最下方的pixels分開做改成如下。發現圖是正確的，執行時間卻變超久，應該是每個thread做的事情太少反而浪費分出去的時間。應該以更大的部份下去分。
```
# Rendering scene
Done!
Execution time of raytracing() : 13.653941 sec
```
(1)raytarcing.c
```C
#pragma omp section
{
pixels[((i + (j * width)) * 3) + 0] = r * 255 / SAMPLES;
}
#pragma omp section
{
pixels[((i + (j * width)) * 3) + 1] = g * 255 / SAMPLES;
}
#pragma omp section
{
pixels[((i + (j * width)) * 3) + 2] = b * 255 / SAMPLES;
}
```
(三)（失敗）
嘗試對```raytracing.c```的rayConstruction()作平行化，原本我是想連add_vector()的地方一起放入section，但是我發現這邊的加法有相依性，我把順序改動之後產生的圖就是錯的，跟一般的加法不太一樣。總結就是會花更多的時間。
（1）raytracing.c
```C
static void rayConstruction(point3 d, const point3 u, const point3 v,
const point3 w, unsigned int i, unsigned int j,
const viewpoint *view, unsigned int width,
unsigned int height)
{
double xmin = -0.0175;
double ymin = -0.0175;
double xmax = 0.0175;
double ymax = 0.0175;
double focal = 0.05;
point3 u_tmp, v_tmp, w_tmp, s;
#pragma omp parallel sections
{
#pragma omp section
{
double w_s = focal;
multiply_vector(w, w_s, w_tmp);
}
#pragma omp section
{
double u_s = xmin + ((xmax - xmin) * (float) i / (width - 1));
multiply_vector(u, u_s, u_tmp);
}
#pragma omp section
{
double v_s = ymax + ((ymin - ymax) * (float) j / (height - 1));
multiply_vector(v, v_s, v_tmp);
/* s = e + u_s * u + v_s * v + w_s * w */
}
}
```
(四)
透過分析raytracing()這個函式，可以發現到d、stk、object_color這三個東西在三個for迴圈內是會被更改到的（大家共用），所以在平行化的時候會有正確性的問題，利用```privete```這個標簽可以將變數複製一份，存取的同時就不會更動到其它thread的數據。結果大幅降低所花費的時間。
（1）Loop unrolling + force inline +openMP
```
Execution time of raytracing() : 1.059777 sec
```
(2)raytracing.c
```C
#pragma omp parallel for private( d, stk, object_color) num_threads()
```
#### Pthread
其實 pthread 就是 openMP 底層的實作，相對於 openMP 的限制，pthread 可以更自由的將想要平行化的地方做平行化，C 底下的 pthread 有一個麻煩的地方是只能接受一個參數的傳入，因此必須先將所需要的所有參數包成 struct。
可以發現8個時時間有明顯比4個快，但是12個和8個就已經相去不遠了，可以從數據看到數目愈多總 cycles 也會變的更多，雖然事情的總量是一樣的可是 cycle 卻變多了，由此可知所花費的時間和數目並不是直接呈現反比的關係。
另外，我這邊是以橫向下去做區分，不同的切割法應該也會有不同的時間消耗，需要真正去實作才知道如何切割能有更加的效能。這也正是 pthread 比 openMP 更好的重點，可以自己比較不同方法之間的優劣而不被限定。
* for row slice
(1) thread = 4 個
```shell
Execution time of raytracing() : 1.046374 sec
----------------------------------------------------
Performance counter stats for './raytracing 4' (10 runs):
20,2916 cache-misses ( +- 5.44% )
194,8376,1762 instructions # 2.15 insns per cycle ( +- 0.00% )
90,7140,9994 cycles ( +- 1.28% )
1.312637314 seconds time elapsed ( +- 8.02% )
```
(2) thread = 8 個
```shell
Execution time of raytracing() : 0.853592 sec
----------------------------------------------------
Performance counter stats for './raytracing 8' (10 runs):
26,5521 cache-misses ( +- 9.45% )
194,8811,1404 instructions # 1.58 insns per cycle ( +- 0.00% )
123,5394,1646 cycles ( +- 0.88% )
1.123687747 seconds time elapsed ( +- 7.62% )
```
(3) thread = 12 個
```shell
Execution time of raytracing() : 0.700497 sec
----------------------------------------------------
Performance counter stats for './raytracing 12' (10 runs):
26,4471 cache-misses ( +- 5.80% )
194,2632,5210 instructions # 1.43 insns per cycle ( +- 0.00% )
136,0667,6502 cycles ( +- 0.43% )
1.111256845 seconds time elapsed ( +- 6.79% )
```
* for cols slice
(1) thread = 4 個
```shell
Execution time of raytracing() : 1.304032 sec
----------------------------------------------------
Performance counter stats for './raytracing_thread 4' (10 runs):
5,1317 cache-misses ( +- 3.02% )
194,8001,0494 instructions # 2.13 insns per cycle ( +- 0.00% )
91,3949,1806 cycles ( +- 2.44% )
1.146683817 seconds time elapsed ( +- 2.88% )
```
(2) thread = 8 個
```shell
Execution time of raytracing() : 0.772257 sec
----------------------------------------------------
Performance counter stats for './raytracing_thread 8' (10 runs):
7,0822 cache-misses ( +- 4.22% )
194,8258,7802 instructions # 1.62 insns per cycle ( +- 0.00% )
120,3381,1433 cycles ( +- 2.18% )
0.991003226 seconds time elapsed ( +- 10.45% )
```
(3) thread = 12 個
```shell
Execution time of raytracing() : 0.743515 sec
----------------------------------------------------
Performance counter stats for './raytracing_thread 12' (10 runs):
7,0021 cache-misses ( +- 2.33% )
194,2522,0067 instructions # 1.43 insns per cycle ( +- 0.00% )
135,4591,5705 cycles ( +- 0.52% )
0.729297521 seconds time elapsed ( +- 1.31% )
```
- [ ]比較不同切割法
#### Software pipeline
[gcc option](https://gcc.gnu.org/onlinedocs/gcc/Optimize-Options.html)
這個方法利用了 pipeline 的概念，將一個 instruction 分成許多stage，因此每個 instruction 之間的順序就很重要，如果一個 instruction 需要的資料是是上一次 instrction 才剛做完處理而還未存回 memory，如此可能造成讀入的資料錯誤的情況，這樣的資料則有**相依性**，如果可以減少 stage bubble，使每個 stage 充份利用可以提高效率。這方面就牽涉到每個 instruction 的不同，考慮每個 instruction 的不同做安排，但是現代 compiler 通常會有 out of order 的功能，所以就算在寫 code 時刻意安排過順序，最後 compile 的結果也不一定會依照 code 的排序執行。
(1)
這邊我利用 GCC 所提供的 option做編譯，```-fsel-sched-pipelining```、```-fselective-scheduling```，出來的結果有快了一點點，大概是個位數趴數的降低，並不是非常明顯，甚至可能是誤差範圍，不能確定是否因為真的用到的 software pipeline 的原理。
```shell
Performance counter stats for './raytracing' (10 runs):
3,5974 cache-misses ( +- 3.88% )
194,6533,9114 instructions # 2.32 insns per cycle ( +- 0.00% )
83,8537,5118 cycles ( +- 0.62% )
2.561081869 seconds time elapsed ( +- 0.68% )
```
(2)
一般的 software pipeline 都是在組語的層級去做分析和改動，譬如：將 load 這一類需要花費較多時間的 Instruction 先處理，也可以降低資料相依性的問題所造成的問題。我用了同樣的原理，先將 `raytracing()` 中的 sample 做 loop unrolling 之後將裏面的事情分成了4個 stage，將這4個 stage 做重新的排序。
Sign in with Wallet
Connect another wallet