# 2016q3 Homework1 (raytracing)
contributed by <`vic85821`>
### Reviewed by `0140454`
* 應該善用 .gitignore 來排除測試時由程式所產生的檔案。
例如 [commit "modify by Macro"](https://github.com/vic85821/raytracing/commit/ee19e2359821a9b674a4cbe36f127fedf282d110) 中的 `output_lu.txt`。
* 應該把非必要的註解刪除後再 commit。
例如 [commit "use OpenMP to improve"](https://github.com/vic85821/raytracing/commit/320cd9376a31ee8fdb7f625cdda09f540a6903cb)。
* 可使用 **gnuplot** 來輸出效能比較圖。
* 未來可嘗試 SIMD 指令來優化並分析其效能及應用環境等。
## 開發環境
* Ubuntu 16.04.1 LTS
* Linux version 4.4.0-38-generic
* CPU : Intel® Core™ i5-3230M CPU @ 2.60GHz
* MEM : 8GB
* L1d cache : 32K
* L1i cache : 32K
* L2 cache : 256K
* L3 cache : 3072K
## 事前準備
* 預先裝好軟體
```shell
$ sudo apt-get update
$ sudo apt-get install graphviz
$ sudo apt-get install imagemagick
```
## 目標
雖然作業很多QAQ,但對我來說,就算都不太懂,只要有學到新的知識,儘管是名詞定義,一點一滴慢慢的跟上,一學期下來一定不同於其他的課程的收穫量!!!!!
# 案例分析
* 在優化之前,先來執行一次看看效能&時間
`Execution time of raytracing() : 3.020114 sec`
* 若使用gprof
```shell
$ make PROFILE=1
```
`Execution time of raytracing() : 6.545642 sec`
產生 `gmon.out` 透過 `gprof ./raytracing | less` 觀察各個function的呼叫次數與使用時間
* `less` 可以讓結果分頁,有助於觀察
```shell
Each sample counts as 0.01 seconds.
% cumulative self self total
time seconds seconds calls s/call s/call name
21.96 0.54 0.54 69646433 0.00 0.00 dot_product
15.86 0.93 0.39 56956357 0.00 0.00 subtract_vector
10.58 1.19 0.26 10598450 0.00 0.00 normalize
9.97 1.44 0.25 13861875 0.00 0.00 rayRectangularIntersection
9.97 1.68 0.25 13861875 0.00 0.00 raySphereIntersection
7.93 1.88 0.20 31410180 0.00 0.00 multiply_vector
7.52 2.06 0.19 17836094 0.00 0.00 add_vector
4.88 2.18 0.12 4620625 0.00 0.00 ray_hit_object
3.25 2.26 0.08 17821809 0.00 0.00 cross_product
2.44 2.32 0.06 1048576 0.00 0.00 ray_color
1.83 2.37 0.05 4221152 0.00 0.00 multiply_vectors
0.81 2.39 0.02 2110576 0.00 0.00 localColor
0.81 2.41 0.02 1241598 0.00 0.00 protect_color_overflow
```
* 偷偷的利用編譯器的最佳化,看一下執行時間(將Makefile裡面的 `-O0` 改成 `-Ofast`)
`Execution time of raytracing() : 0.670504 sec`
>目標就是超越編譯器最佳化了!!(~~這個執行速度好快R~ QAQ~~)
* 開始著手優化!!!
## Loop unrolling
看完功課介紹的video,馬上就來試試看,暴力把LOOP展開!!
* note : [loop unrolling](https://zh.wikipedia.org/wiki/%E5%BE%AA%E7%8E%AF%E5%B1%95%E5%BC%80)
* 減少branch prediction 可以增加效率
* 過多會讓程式可讀性下降 (coding 金字塔!! - readable)
* 透過gprof可以找出較佔時間的前幾名
* 將math-toolkit.h定義的一些數學運算function()展開
* e.g. `add_vector()`, `substract_vector()`
```c
/* 舉例 dot_product */
double dot_product(const double *v1, const double *v2)
{
double dp = 0.0;
dp = v1[0] * v2[0], v1[1] * v2[1], v1[2] * v2[2];
return dp;
}
```
* 緊接著看看執行時間有沒有改變
`Execution time of raytracing() : 2.235425 sec`
時間快了將近1s
## OpenMP / Pthread
彼此沒有相依的data就很自然會想到平行化,不過對於OpenMP與Pthread還沒有很了解,因此要先找找資料!!
* note : [OpenMP](http://aaz-blogger.blogspot.tw/2011/03/openmp-parallel-construct.html) [Pthread]()
* 首先,因為不知道我的電腦上的執行緒最多可以到幾個,因此先來寫個小程式順便熟悉OpenMP的用法
* 這是一個讓每個執行緒都印出一次 Hello!!的程式
```c
#include<stdio.h>
#include<omp.h> //要先include OpenMP library
int main()
{
#pragma omp parallel // parallel directive 的特殊敘述行
//block外的data為各個多執行緒所共享,block內部則各自使用
{
printf("Hello!!\n");
}
return 0;
}
```
* 編譯指令`gcc -fopenmp xxx.c -o xxx`要加上`-fopenmp`才能順利執行
```
Hello!!
Hello!!
Hello!!
Hello!!
```
由此執行結果可知 --> 我的電腦有4個執行緒
但如果我想要限制不要使用全部的執行緒,再編譯之後在多加一行`export OMP_NUM_THREADS=2`即代表我只要使用到其中兩個執行緒
---
來開始找看看哪裡可以套用OpenMP優化
* 跟Loop Unrolling改的地方一樣,只是改成openMP
* 唯一需要注意的,在dot_product()需稍做更動,因為彼此資料是不獨立的
```c
double dot_product(const double *v1, const double *v2)
{
double dp = 0.0;
#omp parallel for reduction(+:dp)
for (int i = 0; i < 3; ++i) {
dp += v1[i] * v2[i];
}
return dp;
}
```
* remind : 編譯要多加 `-fopenmp` !!
* 緊接著看看執行時間有沒有改變
`Execution time of raytracing() : 1.844765 sec`
**結果快超多!!!! 快接近編譯器最佳化了!!繼續努力!!**
但是使用openMP多執行緒, cache miss反而增加到38.658 %
```
Performance counter stats for './raytracing' (10 runs):
124,333 cache-misses # 38.658 % of all cache refs ( +- 8.44% ) (66.47%)
```
>> 請詳細閱讀 [Effects of Multithreading on Cache Performance](http://web.engr.oregonstate.edu/~benl/Publications/Journals/IEEE_ToC99.pdf)，不要跳著讀，你需要培養背景知識 [name=jserv]
## Macro
重新改一下math-toolkit.h
將原本的function重新改成Macro
```
#define DOT(a,b) ((a[0]*b[0])+(a[1]*b[1])+(a[2]*b[2]))
#define SUB(a,b,out) ((out[0]=a[0]-b[0]),(out[1]=a[1]-b[1]),(out[2]=a[2]-b[2]))
#define ADD(a,b,out) ((out[0]=a[0]+b[0]),(out[1]=a[1]+b[1]),(out[2]=a[2]+b[2]))
#define MULV(a,b,out) ((out[0]=a[0]*b[0]),(out[1]=a[1]*b[1]),(out[2]=a[2]*b[2]))
#define MULC(a,b,out) ((out[0]=a[0]*(b)),(out[1]=a[1]*(b)),(out[2]=a[2]*(b)))
```
減少程式執行時,call function的時間,因此可以縮短執行時間
```
Execution time of raytracing() : 1.639391 sec
```
---
優化到現在,再用一次gprof來分析程式
```
% cumulative self self total
time seconds seconds calls s/call s/call name
24.57 0.28 0.28 13861875 0.00 0.00 rayRectangularIntersection
20.19 0.51 0.23 10598450 0.00 0.00 normalize
12.73 0.66 0.15 13861875 0.00 0.00 raySphereIntersection
10.53 0.78 0.12 17821809 0.00 0.00 cross_product
8.78 0.88 0.10 4221152 0.00 0.00 multiply_vectors
6.14 0.95 0.07 2110576 0.00 0.00 localColor
3.51 0.99 0.04 4620625 0.00 0.00 ray_hit_object
3.51 1.03 0.04 1048576 0.00 0.00 ray_color
2.63 1.06 0.03 2110576 0.00 0.00 compute_specular_diffuse
2.19 1.08 0.03 2520791 0.00 0.00 idx_stack_top
1.76 1.10 0.02 1048576 0.00 0.00 rayConstruction
0.88 1.11 0.01 1241598 0.00 0.00 protect_color_overflow
0.88 1.12 0.01 1204003 0.00 0.00 idx_stack_push
0.88 1.13 0.01 1048576 0.00 0.00 idx_stack_init
0.88 1.14 0.01 1 0.01 1.14 raytracing
0.00 1.14 0.00 3838091 0.00 0.00 length
0.00 1.14 0.00 2558386 0.00 0.00 idx_stack_empty
0.00 1.14 0.00 1241598 0.00 0.00 reflection
```
可以看的出來,原本定義再math-toolkit的function都不是排名前幾名了,接著就是想辦法再減少現在當今最消耗時間的部份!!
---
## 參考資料
* [功課介紹video](https://www.youtube.com/watch?v=m1RmfOfSwno)
* [aaz的記憶倉庫-OpenMP](http://aaz-blogger.blogspot.tw/2011/03/openmp-parallel-construct.html)
* [Effects of Multithreading on Cache Performance](http://web.engr.oregonstate.edu/~benl/Publications/Journals/IEEE_ToC99.pdf)
Sign in with Wallet
Connect another wallet