# [2016q1 Homework #2](http://wiki.csie.ncku.edu.tw/embedded/2016q1h2)

**作業要求 (A)**

* 在 GitHub 上 fork [raytracing](https://github.com/embedded2016/raytracing)，並思考如何改善程式效能
* 以 make PROFILE=1 重新編譯程式碼，並且學習 [gprof](https://sourceware.org/binutils/docs/gprof/)
* 參考 [使用 GNU gprof 進行 Linux 平台的程式分析](http://os.51cto.com/art/200703/41426.htm)
* 以 [gprof](https://sourceware.org/binutils/docs/gprof/) 指出效能瓶頸，並且著手改寫檔案 math-toolkit.h 在內的函式實做，充分紀錄效能差異在共筆
* 注意: 請勿更動編譯器最佳化選項 -O0 (關閉最佳化)
* 檔案 math-toolkit.h 定義的若干數學操作函式很重要，可參考 [SIMD optimized dot and cross product functions](http://tomjbward.co.uk/simd-optimized-dot-and-cross/) 和 [2015q3 Homework #1 Ext](http://wiki.csie.ncku.edu.tw/embedded/2015q3h1ext)
* 可善用 POSIX Thread, OpenMP, software pipelining, 以及 loop unrolling 一類的技巧來加速程式運作
* 將你的觀察、分析，以及各式效能改善過程，並善用 gnuplot 製圖，紀錄於「[作業區](https://embedded2016.hackpad.com/2016q1-Homework-2-v37rXPJjRlW)」，記得標注「開發紀錄(A)」

**Gprof 簡介:**

Gprof功能：打印出程式進行中各個函數消耗的時間，可以幫助程式設計師找到在眾多function中最好時的涵式。產生程式進行中的涵式間呼叫的情形，包括使用次數，可以幫助程式設計師分析程式的運行狀況。

有了涵式間的呼叫情形，能夠使我們提高工作的效率因為我們不用去一行一行看成是怎麼跑，對於小的程式來說可能沒有很明顯的差別，但對於有幾萬或是幾十萬行的程式來說就會差很多了！Gprof的功能對於維護舊的程式或是分析Open Source來說是很有用處的，有了彼此呼叫的關係之後我們對於程式是如何運作的框架也會有一定程度的瞭解，知道整個城市的“框架”之後我們對於要如何去更細節的分析程式也會更有概念，尤其是對於不熟悉的程式或是Open Source的code來說更是有用處。

**Gprof 實作原理：**

在編譯與連結的階段（使用-pg編譯和連結的參數），gcc會在程式中的每個function中都加入了一個mcount涵式(or "_mcount",or "__mcount"依賴於compiler或是OS的不同會叫不同名字)，也就是說在程式裡每一個function call 都會再呼叫mcount，而mcount會在記憶體中保存一張涵式使用的圖，並且通過function call stack的方式找尋子涵數與父函數的位址。這張涵式使用的圖也保存了所有與涵式相關的使用時間或是使用次數等等的資訊。

Gprog基本的用法_：_

1.在編譯時加入 -pg 為參數時使用

2.執行程式生成gprog分析的數據

3.使用gprog分析程式所產生的數據

**另外比較  perf top**：每隔一段period會去做採樣(Sample)，最後統計出大概的數據。

**Gprof 輸出訊息**

* % time：函式佔所有執行時間的百分比
* Cumulative seconds：函式累計執行的時間 (秒)
* Self Seconds：函式本身執行時間，Flat profile 是根據這個作排序，
* Calls：函式被呼叫的次數
* Self s/call：調用一次函式平均執行時間 (不包括裡頭呼叫函數)
* Total s/call：調用一次函式的平均執行時間 (包括裡頭呼叫的函數)
* name：函式名稱

**實際上用在<u>[raytracing](https://github.com/embedded2016/raytracing)</u>**

首先直接在source code裡面

$ make

/＊執行看看raytracing＊/

$ .raytracing

* # Rendering scene
* Done!
* Execution time of raytracing() : 5.805244 sec

在未修改過程式碼時執行時間為5.805244 s

$ eog output.ppm /* 開啟最後生成的圖形*/

/*再來使用gprof分析程式*/

首先把之前產生的檔案清掉

$ make clean

$make PROFILE=1 //設定要使用gprof

cc -std=gnu99 -Wall -O0 -g -pg -c -o objects.o objects.c

cc -std=gnu99 -Wall -O0 -g -pg -c -o raytracing.o raytracing.c

cc -std=gnu99 -Wall -O0 -g -pg -c -o main.o main.c

cc -o raytracing objects.o raytracing.o main.o -lm -pg

$ ./raytracing  //再執行一次

* # Rendering scene
* Done!
* Execution time of raytracing() : 6.070649 sec

由於多了gprof所以執行時間變長

$gprof -b raytracing gmon.out | head -n 20

* Flat profile:

* Each sample counts as 0.01 seconds.
* %   cumulative   self              self     total           
* time   seconds   seconds    calls   s/call   s/call  name    
* 21.88      0.79     0.79 69646433     0.00     0.00  dot_product
* 19.51      1.49     0.70 56956357     0.00     0.00  subtract_vector
* 10.03      1.85     0.36 13861875     0.00     0.00  rayRectangularIntersection
* 10.03      2.21     0.36 10598450     0.00     0.00  normalize
* 9.48      2.55     0.34 31410180     0.00     0.00  multiply_vector
* 6.69      2.79     0.24 13861875     0.00     0.00  raySphereIntersection
* 5.57      2.99     0.20 17836094     0.00     0.00  add_vector
* 4.18      3.14     0.15  4620625     0.00     0.00  ray_hit_object
* 2.79      3.24     0.10 17821809     0.00     0.00  cross_product
* 2.51      3.33     0.09  1048576     0.00     0.00  ray_color
* 1.67      3.39     0.06  4221152     0.00     0.00  multiply_vectors
* 1.11      3.43     0.04  1241598     0.00     0.00  refraction
* 1.11      3.47     0.04        1     0.04     3.59  raytracing
* 0.84      3.50     0.03  2110576     0.00     0.00  localColor
* 0.56      3.52     0.02  2520791     0.00     0.00  idx_stack_top

可以發現時間大部分都用在運算上，在知道哪些涵式比較花時間後我要怎麼找得到涵式在哪裡呢？

我利用了ctags幫我建立function tag我可以直接切換到我想要的function，ctags可以反查與查找非常的方便！

直接安裝完ctags後在目錄裡面下

$ctags -R * 

進去vim後在vim 的命令那邊下 **:set tags=./tags**

然後可以下:Tlist來看目前這個檔案裡頭有哪些tags通常會有funciton #define 與一些macro

找到想要找的function後按

* 【Ctrl】+【]】

就可以跳到function的定義

接著再輸入:

* 【Ctrl】+【t】

就可回到function call的地方

使用的教學可以自行google ctags或參考[](http://swaywang.blogspot.tw/2011/10/vim-ctags.html)http://swaywang.blogspot.tw/2011/10/vim-ctags.html

經過ctags幫我找完過後我很快就知道了這些花時間的function都在math-toolkit.h

## Loop unrolling

這邊做的事情很簡單,就只是把loop展開來,由於這邊用到的loop很小,所以直接展開來能夠少跑很多程式碼

另外由於loop會用到條件跳耀指令所以直接展開來將能夠減少執行時間

所以我就把下面使用到loop的function都展開

* static inline
* 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];                       
* }

* static inline
* void subtract_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];
* }

* static inline
* void multiply_vectors(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];
* }

* static inline
* void multiply_vector(const double *a, double b, double *out)
* {
* out[0] = a[0] * b;
* out[1] = a[1] * b;
* out[2] = a[2] * b;
* }
* static inline
* 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;
* }

都修改完之後再執行一次

$./raytracing

* # Rendering scene
* Done!
* Execution time of raytracing() : 2.236972 sec

使用loop unrolling降低執行時間為2.236972

* Flat profile:

* Each sample counts as 0.01 seconds.
* %   cumulative   self              self     total
* time   seconds   seconds    calls   s/call   s/call  name
* 17.77      0.38     0.38 69646433     0.00     0.00  dot_product
* 14.03      0.68     0.30 13861875     0.00     0.00  rayRectangularIntersection
* 11.69      0.93     0.25 56956357     0.00     0.00  subtract_vector
* 11.22      1.17     0.24 10598450     0.00     0.00  normalize
* 10.75      1.40     0.23 17821809     0.00     0.00  cross_product
* 9.82      1.61     0.21 13861875     0.00     0.00  raySphereIntersection
* 6.31      1.75     0.14  4620625     0.00     0.00  ray_hit_object
* 6.08      1.88     0.13 31410180     0.00     0.00  multiply_vector
* 5.14      1.99     0.11 17836094     0.00     0.00  add_vector
* 1.87      2.03     0.04  4221152     0.00     0.00  multiply_vectors
* 1.87      2.07     0.04  1048576     0.00     0.00  ray_color
* 1.17      2.09     0.03  1048576     0.00     0.00  rayConstruction
* 0.94      2.11     0.02        1     0.02     2.14  raytracing
* 0.47      2.12     0.01  2110576     0.00     0.00  compute_specular_diffuse
* 0.47      2.13     0.01  2110576     0.00     0.00  localColor

可以看到使用unrolling的funtion執行時間都減少了所以導致整個執行時間下降

## POSIX Thread

* 說好的程式呢？
* 這幾天會全部補上！

這邊主要參考[陳品睿大大的hackpad](https://embedded2016.hackpad.com/2016q1-Homework-2A-bLGQtRraTES)

<undefined style="color: rgb(0, 0, 0); font-family: Helvetica; font-size: medium; letter-spacing: normal;">* 分析二：</undefined><span style="color: rgb(0, 0, 0); font-family: Helvetica; font-size: medium; letter-spacing: normal;"></span>

* 來看一段raytracing.c (raytracing) 的程式碼

* 用 `filename (function_name)` 的標注即可

* for (int j = 0; j < height; j++) {
* for (int i = 0; i < width; i++) {
* double r = 0, g = 0, b = 0;
* /* MSAA */
* for (int s = 0; s < SAMPLES; s++) {
* idx_stack_init(&stk);
* rayConstruction(d, u, v, w,
* i * factor + s / factor,
* j * factor + s % factor,
* view,
* width * factor, height * factor);
* if (ray_color(view->vrp, 0.0, d, &stk, rectangulars, spheres,
* lights, object_color,
* MAX_REFLECTION_BOUNCES)) {
* r += object_color[0];
* g += object_color[1];
* b += object_color[2];
* } else {
* r += background_color[0];
* g += background_color[1];
* b += background_color[2];
* }
* pixels[((i + (j * width)) * 3) + 0] = r * 255 / SAMPLES;
* pixels[((i + (j * width)) * 3) + 1] = g * 255 / SAMPLES;
* pixels[((i + (j * width)) * 3) + 2] = b * 255 / SAMPLES;
* }
* }
* }

可以發現各個pixel是可以獨自運算的，故我們可以做平行處理。

再把程式碼讀過一次 , 每個pixel都拆成x,y,z三個維度每個維度都是獨自做運算的彼此不相干所以可以做平行處理（OpenCL,OpenMP,thread）

所以我就先做了thread看看

**thread 實作 **

**參考資料**[](http://blog.csdn.net/liangxanhai/article/details/7767430)http://blog.csdn.net/liangxanhai/article/details/7767430

pthread_create define

int pthread_create([pthread_t](http://baike.baidu.com/view/4591990.htm)*restrict tidp,const pthread_attr_t *restrict_attr,void*（*start_rtn)(void*),void *restrict arg);

回傳值 ：如果成功則回傳0，否則就回傳錯誤編號

* 當回傳成功時，
* tidp指向的記憶體單元被設置為新創的執行緒的thread ID。
* attr參數用於制定各種不同的執行緒的屬性。
* 新創建的執行緒從start_rtn涵式的位置開始執行，而這個涵式只會有一個void *的pointer，如果需要向start_rtn傳入不只一個參數的話，就需要先將參數放到一個結構中，然後再把這個結構的位置作為arg傳入。

* 在linux底下使用Ｃ來開發多執行緒的程式，linux系統下的多執行緒回依循POSIX執行緒的見面做設計，稱為pthread。

* **補充**restrict 是 C 的關鍵字，只能用來修飾 pointer，目的是協助 compiler 做最佳化，是告知 compiler ，這一個 restrict pointer 是唯一指向 data 的 pointer，意即程式當中不會透過其他變數 ( pointer,或者直接存取 ) 來 access 此 data
* 例子如下：

* int * restrict rptr = (int*) malloc(10*sizeof(int)); 
* int a[10]; 
* int * ptr; 
* ptr = a; 
* for(int i =0; i<10;i++) {  
* ptr += 5; 
* rptr +=5; 
* a *= 5; 
* ptr += 3; 
* rptr += 3; 
* }

* 當 compiler 看到 rptr 為 restric，就會用 rptr += 8 取代 rptr += 3 和 rptr += 5
* 而 ptr 就不應該被直接替換，因為它不是唯一會 access 該 data 的變數

* C99 用到restrict的例子：
* void* memcpy (void* restrict destination, const void* restrict source, size_t n);
* 代表destination和source區段是不可重疊的
* 結果

* # Rendering scene
* Done!
* Execution time of raytracing() : 0.244959 sec