2016q3 Homework1 (raytracing)

# 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 ![](https://i.imgur.com/QuJYU2C.gif) - 雖然每個 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！！

Syntax	Example	Reference
# Header	Header	基本排版
- Unordered List	Unordered List
1. Ordered List	Ordered List
- [ ] Todo List	Todo List
> Blockquote	Blockquote
Bold font	Bold font
Italics font	Italics font
~~Strikethrough~~	~~Strikethrough~~
19^th^	19^th
H~2~O	H₂O
++Inserted text++	Inserted text
==Marked text==	Marked text
[link text](https:// "title")	Link
![image alt](https:// "title")	Image
`Code`	`Code`	在筆記中貼入程式碼
```javascript var i = 0; ```	`var i = 0;`
:smile:		Emoji list
{%youtube youtube_id %}	Externals
$L^aT_eX$	L^aT_eX
:::info This is a alert area. :::	This is a alert area.