# 2017q1 Homework1 (raytracing)
contributed by <`ryanwang522`>
### Reviewed by `illusion030`
* 沒有實作 force inline
* 平行化可以尋找熱點來決定平行化的策略，以達到最佳平行化的效果，可以參考 [ggary9424的共筆](https://embedded2016.hackpad.com/2016q1-Homework-2A-bLGQtRraTES#:h=程式運作分析)
* 可以跟編譯器最佳化的結果比較看看
---
## 開發環境
* OS: 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-4200H CPU @ 2.80GHz
## 原始版本
* 進行編譯並執行之後，利用 gprof 觀察程式內每個函式的呼叫情形
* `$ gprof ./raytracing | less`
* 發現 `dot_product()` 耗費的時間相當可觀，和 `math-toolfit.c` 裡頭的 function 同為程式熱點，可以從這裡去改善。
```
Execution time of raytracing() : 5.454266 sec
```
```
Each sample counts as 0.01 seconds.
% cumulative self self total
time seconds seconds calls s/call s/call name
24.45 0.54 0.54 69646433 0.00 0.00 dot_product
17.21 0.92 0.38 56956357 0.00 0.00 subtract_vector
9.96 1.14 0.22 31410180 0.00 0.00 multiply_vector
8.60 1.33 0.19 10598450 0.00 0.00 normalize
6.79 1.48 0.15 13861875 0.00 0.00 rayRectangularIntersection
6.79 1.63 0.15 4620625 0.00 0.00 ray_hit_object
6.34 1.77 0.14 13861875 0.00 0.00 raySphereIntersection
5.89 1.90 0.13 17836094 0.00 0.00 add_vector
4.98 2.01 0.11 17821809 0.00 0.00 cross_product
2.26 2.06 0.05 1048576 0.00 0.00 ray_color
1.36 2.09 0.03 1048576 0.00 0.00 rayConstruction
0.91 2.11 0.02 2110576 0.00 0.00 compute_specular_diffuse
0.91 2.13 0.02 2110576 0.00 0.00 localColor
0.91 2.15 0.02 1241598 0.00 0.00 refraction
0.91 2.17 0.02 1 0.02 2.20 raytracing
0.45 2.18 0.01 4221152 0.00 0.00 multiply_vectors
0.45 2.19 0.01 113297 0.00 0.00 fresnel
0.45 2.20 0.01 1 0.01 0.01 delete_sphere_list
0.23 2.21 0.01 2558386 0.00 0.00 idx_stack_empty
0.23 2.21 0.01 1204003 0.00 0.00 idx_stack_push
```
* 參考了 [hugikun999的共筆](https://hackmd.io/s/HyHhgcv6)，透過 graphviz 產生出視覺化的函式運作圖表如下
## 實際嘗試
### Loop unrolling
* 先試著將負擔較重的 `subtract_vector` 以及 `multiply_vector` 進行 loop unrolling
* `$ ./raytracing`
`Execution time of raytracing() : 4.693472 sec`
* 發現雖然只是減少少數的迴圈次數，但由於呼叫次數非常多，所以微小的改變也可以對效能有著不可忽略的影響。
* 將`math-toolkit.h`內的函式進行改寫。
* 與原版比較
### Multi-thread
* OpenMP `$ sudo apt-get install gcc-multilib`
* 修改`Makefile`
* 編譯參數 `CFLAGS` 加上 `-fopenmp`
* `LDFLAGS` 加上 `-lgomp`
* 針對`raytracing()`裡面的外層 for-loop 進行平行化，加上
```
#pragma omp parallel for num_threads(NUM_THREADS) private(stk, d)
```
* 接著執行看看，發現輸出圖形長這樣
* 因為先前修過平行程式設計的課程，看到這種輸出已經是家常便飯了QQ，也大概知道原因是有些 private 變數沒有設定好，造成每個 thread 都改到應該要在每個執行序裡面獨立的變數，再回去把平行的函式內容看懂。
* 觀察 `ray_color()`
* 發現 `object_color` 在裡面有大量的修改 -> 設為 private
* 大致上瀏覽了一下有沒有需要使用 critical section 保護的變數，決定就先試試吧！
```
#pragma omp parallel for num_threads(NUM_THREADS) private(stk, d, object_color)
```
* 進行輸出
* 觀察效能 `./raytracing`
```
Execution time of raytracing() : 1.064679 sec
```
* 執行 100 次並平均後的結果如圖所示，平行化使得執行時間縮減了 83%！
* 最後想來測試看看 openmp 的不同 schedule 模式有什麼差別
* 整理`schedule(type [,chunk_size])`，type 大致上分為四種
* static
* 每個 thread 在開始進行迴圈進行之前就已經被分配好了該執行的 iteration。
* 其中 chunk_size 代表每個 thread 每次要執行的迴圈次數。
* 舉例： 3 個 threads 執行 12 個 iterations。
`schedule(static, 1)` 也可以說是 cyclic partition
`schedule(static, 2)`
`schedule(static, 4)` 同 block partition
* dynamic / guided
* 每個 thread 也都執行一個 chunk_size 大小的區塊，當執行完再去 request 剩下的區塊
* guided 不同的地方是會先指行比較大的 chunk_size 區塊，隨後遞減到 指定的的 chunk_size。
* chunk_size 預設為 1。
* auto
* 交給 compiler 決定。
* runtime
* 透過設定 `OMP_schedule` 環境變數，在執行時間決定排程。
> 有錯還煩請指正。[name=Ryan Wang]
* 針對不同模式進行比較
* Cyclic partion
`#pragma omp parallel for num_threads(NUM_THREADS) private(stk, d, object_color) schedule(static, 1)`
* 執行結果
`Execution time of raytracing() : 0.765990 sec`
* Block partition
`#pragma omp parallel for num_threads(NUM_THREADS) private(stk, d, object_color) schedule(static, 128)`
* 執行結果
`Execution time of raytracing() : 0.769061 sec`
* Dynamic with size = 1
`#pragma omp parallel for num_threads(NUM_THREADS) private(stk, d, object_color) schedule(dynamic)`
* 執行結果
`Execution time of raytracing() : 0.766699 sec`
* gnuplot 比較
## Reference
[hugikun999共筆](https://hackmd.io/s/HyHhgcv6)
[gnuplot 語法解說和示範](https://hackmd.io/s/Skwp-alOg)
[Openmp loop schedule](https://software.intel.com/en-us/articles/openmp-loop-scheduling)
[多處理機與平行程式設計課程投影片]()
Sign in with Wallet
Connect another wallet