# 2016q3 Homework1 (raytracing)
#### contributed by <`andy19950`>
### Review TotallyWrong
* Callgraph 是個很好用的Tool 可以嘗試一下，可以看到一些不一樣的程式Behavior。其實還有AVX，Software Pipline等方案可以嘗試。
### 使用gprof分析程式熱點
```
Flat profile:
Each sample counts as 0.01 seconds.
% cumulative self self total
time seconds seconds calls s/call s/call name
18.06 0.48 0.48 69646433 0.00 0.00 dot_product
16.55 0.92 0.44 56956357 0.00 0.00 subtract_vector
11.66 1.23 0.31 31410180 0.00 0.00 multiply_vector
8.46 1.46 0.23 17836094 0.00 0.00 add_vector
8.46 1.68 0.23 13861875 0.00 0.00 rayRectangularIntersection
```
- 我們擷取前五名最花時間的function來對它們做最佳化！！
- 目標是可以利用程式碼的最佳化達到跟編譯器最佳化一樣的效果
---
### 首先使用-Ofast來看看編譯器最佳化的結果
```
Performance counter stats for './raytracing' (100 runs):
62,894 cache-misses #27.256 % of all cache refs ( +- 1.64% )
230,751 cache-references ( +- 3.17% )
262,129,289 branch ( +- 0.00% )
3,417,337,773 instructions #1.79 insns per cycle ( +- 0.00% )
1,905,665,597 cycles ( +- 0.12% )
0.646348227 seconds time elapsed ( +- 0.40% )
```
- 平均執行時間 ： 0.64 sec
- branch 次數 ： 2.6億次
---
### 接下來對 math-toolkit.h 進行優化
- 對有 for迴圈 的 function 使用 loop unrolling
- 以 add_vector 為例
``` clike=
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];
}
```
- 修改後的結果如下，可以發現優化過的 function 執行時間都有下降
```
Each sample counts as 0.01 seconds.
% cumulative self self total
time seconds seconds calls s/call s/call name
16.19 0.28 0.28 69646433 0.00 0.00 dot_product
15.89 0.55 0.27 13861875 0.00 0.00 rayRectangularIntersection
13.83 0.78 0.24 56956357 0.00 0.00 subtract_vector
10.59 0.96 0.18 10598450 0.00 0.00 normalize
7.06 1.08 0.12 31410180 0.00 0.00 multiply_vector
```
- 使用 perf 觀察可以發現 branch 次數大幅下降！！
- 執行時間距離目標還很遠，必須找其他方法降低。
```
Performance counter stats for './raytracing' (100 runs):
106,186 cache-misses #24.499 % of all cache refs ( +- 2.82% )
433,426 cache-references ( +- 2.71% )
969,948,464 branch ( +- 0.00% )
12,314,790,448 instructions #1.89 insns per cycle ( +- 0.00% )
6,506,120,704 cycles ( +- 0.07% )
2.152467875 seconds time elapsed ( +- 0.14% )
```
---
### 再一次觀察 gprof
- 我們可以發現一個重點程式 ： raytracing
- 它的呼叫次數只有一次但執行時間卻可以跟呼叫百萬次的一樣久
```
Each sample counts as 0.01 seconds.
% cumulative self self total
time seconds seconds calls s/call s/call name
1.83 1.50 0.03 3838091 0.00 0.00 length
1.83 1.53 0.03 1 0.03 1.64 raytracing
1.22 1.55 0.02 2110576 0.00 0.00 localColor
```
---
### 觀察 raytracing()
- 我們可以知道他是最後將圖片計算出來的函式
- 程式碼的部份用三個for迴圈來計算每個 pixel 的RGB值
- 使用 loop unrolling 的話會讓程式碼太龐大而且不知道圖片的大小
- 所以這邊我使用 pthread 來平行處理每個 pixel 使其加速
:::info
**＊ 在優化 raytracing() 之前先來了解一下什麼是 pthread**
:::
---
### POSIX Threads
#### pthread_create() VS fork()
- 產生以及控管 thread 相較於 process 所需的系統資源低很多
- 下表為 fork 以及 pthread_create 在不同 cpu 執行50000個 process/threads 所使用的時間
```
platform | fork | pthread_create()
====================| real user sys | real user sys
Intel 2.6 GHz Xeon | 8.1 0.1 2.9 | 0.9 0.2 0.3
Intel 2.8 GHz Xeon | 4.4 0.4 4.3 | 0.7 0.2 0.5
AMD 2.3 GHz Opteron | 12.5 1.0 12.5 | 1.2 0.2 1.3
AMD 2.4 GHz Opteron | 17.6 2.2 15.7 | 1.4 0.3 1.3
```
#### Thread 各自獨立的單位
1. Stack pointer
2. Registers
3. Scheduling properties
4. Set of pending and blocked signals
5. Thread specific data.
#### Shared Memory
- 雖然每個 thread 都有自己獨立的 private data 以及大家一起使用的 shared memory
- 但因為每個 thread 都是同步執行的，也就是誰先誰後沒有一定順序，所以使用 pthread 來同步執行必須先確保程式碼沒有相依性。
---
### 優化 raytracing()
- 根據上面的結論，我們必須找出程式碼沒有相依性的地方。
- 觀察程式碼後可以發現前兩個 for 迴圈只是在指定每個 pixel 的位置
- 想法： 把圖片分成幾個區塊，用 pthread 平行運算
#### 在 main 的部份生成 pthread 同時呼叫raytracing
```clike=
for(j=0; j<THREAD_NUM; j++){
/*---這邊省略把原本raytracing的參數包成struct傳入thread，詳細請參考我的github---*/
input* box = (input*) malloc (sizeof(input));
rc = pthread_create(&tid[j], &attr, raytracing, (void*) &box) ;
}
for(j=0; j<THREAD_NUM; j++)
rc = pthread_join(tid[j], NULL);
```
- input box為我宣告的struct，成員有原本需要傳入raytracing的參數。
- 因為 pthread_create 只有第四個參數可以當作raytracing的傳入值，所以我把它包成結構傳入。
- 需要注意的是根據定義第四個參數的型態必須是 (void*)。
#### 在 raytracing的部份 把原本最外層的迴圈條件改變讓程式只跑整張圖的一部分
```clike=
for (int j = box->j; j < (box->j + box->height / THREAD_NUM); j++) {
for (int i = 0; i < box->width; i++) {
```
- 每個thread都把寬度算完高度的部份用 THREAD_NUM 為單位去分。
- 簡單來說就是把整張圖橫切等分為 THREAD_NUM個，每個用一個 thread 去計算它的pixel。
- 下面部份的code若有用到原本的參數要向上面一樣使用 box->variable。
#### 結果分析
- thread 不是越多越好，512個 thread 執行時間不是最短！！
- 最主要的原因應該是 main 還在分配 thread 的時候，可能就有**前面的 thread 已經跑完了**，這樣就沒有平行化的效果，卻還要付出呼叫 thread 的代價。
- 經過實驗發現 THREAD_NUM = 8 開始效能算是最低（數據如下：）
```
THREAD_NUM EXEC_TIME || THREAD_NUM EXEC_TIME
512 0.996285 sec || 256 1.016958 sec
128 1.003348 sec || 64 1.022087 sec
32 0.957354 sec || 16 0.965541 sec
8 0.968322 sec || 4 1.089226 sec
2 1.217084 sec || 1 2.160865 sec
```
#### 使用 inline attribute (8 threads)
```
Performance counter stats for './raytracing' (100 runs):
98,242 cache-misses #11.745 % of all cache refs ( +- 0.80% )
836,439 cache-references ( +- 0.80% )
545,838,551 branch ( +- 0.00% )
10,597,581,108 instructions #1.19 insns per cycle ( +- 0.00% )
8,893,931,480 cycles ( +- 0.13% )
0.860754705 seconds time elapsed ( +- 0.26% )
```
- 時間可以降至 0.86 sec
- ---
### 結論
- 一開始使用 -Ofast 時間為 0.64 sec -O0 時間為 3.02 sec
- 優化後使用 -Ofast 時間為 0.26 sec -O0 時間為 0.86 sec
- 程式碼的最佳化竟然可以讓執行時間縮減成原來的 1/4
- 希望未來能夠再把這份程式優化，讓我達成一開始的目標。
---
### Reference
* [pthread 傳遞多個參數](http://pccts.blogspot.tw/2007/11/pthreadcreate.html)
* [POSIX Threads Programing](https://computing.llnl.gov/tutorials/pthreads/)
* [fork vs pthread](https://computing.llnl.gov/tutorials/pthreads/fork_vs_thread.txt)
* [吳彥寬的共筆](https://embedded2016.hackpad.com/2016q1-Homework-2A-wOu40KzMaIP)
- 特別感謝上面那位同學的共筆，非常詳細的解說，尤其是他解決了我苦思已久的bug！！
Sign in with Wallet
Connect another wallet