HackMD
2017q1 Homework01 (raytracing)
contributed by <hugikun999>
Reviewed by yangyang95
- 中文與英文之間要留有空格
- 文字訊息應避免使用圖片，以方便搜尋
- loop unrolling ： “展開 function 而不使用呼叫的方式” 的解釋是否有些奇怪？ 參考資料
- force inline ： “加上 inline 通常compiler就會自動 inline” 是否正確？ 參考資料
還有 sqrt() 回傳的是 平方根，而非方均根，兩者並不相同 - OpenMP 的部分，觀察一下
#pragma該放的位置，還有記得把會改變到的變數 (stk 、 d 、 object_color) 使用 private 處理 參考資料 - commit 4196911bc510cdccfc595369b4ca8ef2285fa7e6
commit message 還是改明確一點吧，至少提到使用是 POSIX thread
Gprof
在make時記得要加上 CFLAGS=-pg 和 LDFLAGS=-pg 兩個選項，第一個是設定編譯選項，第二個是鏈接選項。
- Sample-Error
prof 是會產生不準確的，尤其是當 multi-thread 時可能會造成重覆的 sample，只有當程式的 run-time 大於 sample-time 時才可以確保 gprof 是精準的分析。
commond
(1)
$ gprof -p ./raytracing
只輸出function的時間開銷表。
(2)
$ gprof -q ./raytracing
只輸出call graph
(3)
$ gprof -b ./raytracing
略過中間的解釋
graphviz
將gprof產生的結果數據透過graphviz產生出容易觀看的圖表。graphviz的檔案需要特定格式(ex:dot、neato、fdp)，會需要用到gprof2dot將gprof產生的檔案轉成dot的形式。
install gprof2dot
安裝的時後會用到pip,所以要先安裝python。
要注意這裡不可以下$ sudo apt install pip，會找不到東西安裝。
$sudo apt install python python-pip
$sudo pip install --upgrade pip
$sudo pip install gprof2dot
command
在這個網站中有提供不同情況下使用的command，但是其中gprof給的command執行後會出現command not found，因此我改用下面的command。
$ gprof ./raytracing | gprof2dot | dot -T png -o output.png
static function
static void f1()
{
std::cout << "f1()" << std::endl;
}
void f2()
{
std::cout << "f2()" << std::endl;
}
這兩個 function 的差別在於有沒有宣告時加上 static，f1() 只能被這個compilation Unit所看見，f2() 會被不同的 compilation Uint 看見。
同一個.h檔在被多個.c檔引用，在 compile 時會將.h檔展開，如果在.h檔內定義了一個 function 的實作最後將所有.o檔一起編成執行檔時就會發生重覆定義的問題，因此在.h檔內通常不會去定義一個 function 的實作而是只有宣告 function，在.c中才去定義實作的部份。另外一個方法是可以利用 extern ，聲明變數會在其他的位置被定義，這個位置可能是在同一份文件之中，或是在其他文件之中，需要注意的是在使用 extern 時不可賦值，否則將被視為重覆定義。
Raytracing
file detail
typedef double point3[3];
用point3來宣告的東西是一個具有三個element的指標。
struct object_fill{}
紀錄RGB、反光率之類的object。
models.inc
這個檔案是一些物體和光的資料。
可能的優化方向
-
Loop unrolling
藉由展開function而不使用呼叫的方式，可以減少花費在呼叫的時間，但是會造成程式本身的膨脹，有點類似空間換取時間的做法。 -
Force inline
如果定義時加上"inline"通常compiler就會自動inline，但在這次的MAKEFILE中特別加了關閉編譯器最佳化選項 -O0，因此會須要force inline，就算關閉最佳化依然會inline。 -
Pthread
-
SIMD
-
AVX
-
openMP
function
-
inline function
效果：在定義時將前面加上inline，藉由inline可以將函式直接在main中展開，免除函式呼叫所造成的成本，從而提升效能。注意：須要在定意時加，若在宣告時加沒有作用，且可能會造成在complier時main過度龐大。另外如果函式內含有其它複雜度高的函式，則效益不大。
sqrt(double a);
說明：回傳a的方均根。
回傳值：a的方均根。
未優化
將原本下載的原始碼做編譯而得到的結果，可以看到這個program花最多的時間是dot_product()，藉由這張數據圖可以看到花費時間比較多的程式，可以從這些function去尋找優化方法。另外可以看到由call graph所繪出的圖，思考如何從中減少時間的方向。
Execution time od raytracing() : 5.309807 sec
請直接將訊息(含程式碼以及輸出結果)貼上來，避免使用圖片
課程助教
優化
establish record（失敗）
我發現normalize()和length()兩個函式其實很相近，在normalize()中已經算出length()要求的東西，所以我就把它的位置記錄起來，這樣只要比對位置一樣就不必重算。
從數據看來normalize()的％數有上升，但是花費的時間反而更多。
Loop unrolling
(一)
我更改了add_vector()、subtract_vector()、multiply_vectors()、multiply_vector()、dot_product()這些fuction，把能不用for迴圈做的事給拆開來寫。從perf stat可以看到instructions有減少但是cache-misses卻有所上升。
（二）
在raytracing.c中的raytracing()裡面有三個for迴圈，第三個for是以SAMPLE這個變數下去跑，其實它的真實值是4，所以這裡也可以拆開來跑。但是由於這次for迴圈內的行數較多拆開來會有點亂。
參考自heathcliffYang
force inline+loop unrolling
Execution time of raytracing() : 2.184140 sec
Force inline
(一)
將math-toolkih.h中所有有用到inline的地方全部替換成 __attribute__((always_inline))，特別住意前面是兩個_而不是一個。可以看到branch-misses下降很多，cache-misses卻上升了，總體時間下降了很多。另外在make PROFILE=1時會出現always_inline function might not be inlinable是指compiler不一定會做inline這個指令
（二）
在idx_stack.h中也有inline的部份，依照之前的改法改成__attribute__((always_inline))去強制inline。時間大概可以再減少0.02秒。
OpenMP
（一）
在raytracing.c中加上#inclde <omp.h>並在更改MAKEFILE中的參數。目前結果是變更慢且做出來的圖是錯的，應該是parallel的地方錯了。
(1)MAKEFILE
CC ?= gcc
CFLAGS = \
-std=gnu99 -Wall -O0 -g -fopenmp
LDFLAGS = \
-lm -fopenmp
(2)raytracing.c
#pragma omp parallel for
for (int j = 0; j < height; j++) {
for (int i = 0; i < width; i++) {
double r = 0, g = 0, b = 0;
/* MSAA */
＃pragma omp parallel for
for (int s = 0; s < SAMPLES; s++) {
idx_stack_init(&stk);
.
.
.
.
發現在上面的code中有r、g、b，在其中會分別歸0，而若分下去做可能會造成存取上的問題。
（二）
嘗試將最下方的pixels分開做改成如下。發現圖是正確的，執行時間卻變超久，應該是每個thread做的事情太少反而浪費分出去的時間。應該以更大的部份下去分。
# Rendering scene
Done!
Execution time of raytracing() : 13.653941 sec
(1)raytarcing.c
#pragma omp section
{
pixels[((i + (j * width)) * 3) + 0] = r * 255 / SAMPLES;
}
#pragma omp section
{
pixels[((i + (j * width)) * 3) + 1] = g * 255 / SAMPLES;
}
#pragma omp section
{
pixels[((i + (j * width)) * 3) + 2] = b * 255 / SAMPLES;
}
(三)（失敗）
嘗試對raytracing.c的rayConstruction()作平行化，原本我是想連add_vector()的地方一起放入section，但是我發現這邊的加法有相依性，我把順序改動之後產生的圖就是錯的，跟一般的加法不太一樣。總結就是會花更多的時間。
（1）raytracing.c
static void rayConstruction(point3 d, const point3 u, const point3 v,
const point3 w, unsigned int i, unsigned int j,
const viewpoint *view, unsigned int width,
unsigned int height)
{
double xmin = -0.0175;
double ymin = -0.0175;
double xmax = 0.0175;
double ymax = 0.0175;
double focal = 0.05;
point3 u_tmp, v_tmp, w_tmp, s;
#pragma omp parallel sections
{
#pragma omp section
{
double w_s = focal;
multiply_vector(w, w_s, w_tmp);
}
#pragma omp section
{
double u_s = xmin + ((xmax - xmin) * (float) i / (width - 1));
multiply_vector(u, u_s, u_tmp);
}
#pragma omp section
{
double v_s = ymax + ((ymin - ymax) * (float) j / (height - 1));
multiply_vector(v, v_s, v_tmp);
/* s = e + u_s * u + v_s * v + w_s * w */
}
}
(四)
透過分析raytracing()這個函式，可以發現到d、stk、object_color這三個東西在三個for迴圈內是會被更改到的（大家共用），所以在平行化的時候會有正確性的問題，利用privete這個標簽可以將變數複製一份，存取的同時就不會更動到其它thread的數據。結果大幅降低所花費的時間。
（1）Loop unrolling + force inline +openMP
Execution time of raytracing() : 1.059777 sec
(2)raytracing.c
#pragma omp parallel for private( d, stk, object_color) num_threads()
Pthread
其實 pthread 就是 openMP 底層的實作，相對於 openMP 的限制，pthread 可以更自由的將想要平行化的地方做平行化，C 底下的 pthread 有一個麻煩的地方是只能接受一個參數的傳入，因此必須先將所需要的所有參數包成 struct。
可以發現8個時時間有明顯比4個快，但是12個和8個就已經相去不遠了，可以從數據看到數目愈多總 cycles 也會變的更多，雖然事情的總量是一樣的可是 cycle 卻變多了，由此可知所花費的時間和數目並不是直接呈現反比的關係。
另外，我這邊是以橫向下去做區分，不同的切割法應該也會有不同的時間消耗，需要真正去實作才知道如何切割能有更加的效能。這也正是 pthread 比 openMP 更好的重點，可以自己比較不同方法之間的優劣而不被限定。
- for row slice
(1) thread = 4 個
Execution time of raytracing() : 1.046374 sec
----------------------------------------------------
Performance counter stats for './raytracing 4' (10 runs):
20,2916 cache-misses ( +- 5.44% )
194,8376,1762 instructions # 2.15 insns per cycle ( +- 0.00% )
90,7140,9994 cycles ( +- 1.28% )
1.312637314 seconds time elapsed ( +- 8.02% )
(2) thread = 8 個
Execution time of raytracing() : 0.853592 sec
----------------------------------------------------
Performance counter stats for './raytracing 8' (10 runs):
26,5521 cache-misses ( +- 9.45% )
194,8811,1404 instructions # 1.58 insns per cycle ( +- 0.00% )
123,5394,1646 cycles ( +- 0.88% )
1.123687747 seconds time elapsed ( +- 7.62% )
(3) thread = 12 個
Execution time of raytracing() : 0.700497 sec
----------------------------------------------------
Performance counter stats for './raytracing 12' (10 runs):
26,4471 cache-misses ( +- 5.80% )
194,2632,5210 instructions # 1.43 insns per cycle ( +- 0.00% )
136,0667,6502 cycles ( +- 0.43% )
1.111256845 seconds time elapsed ( +- 6.79% )
- for cols slice
(1) thread = 4 個
Execution time of raytracing() : 1.304032 sec
----------------------------------------------------
Performance counter stats for './raytracing_thread 4' (10 runs):
5,1317 cache-misses ( +- 3.02% )
194,8001,0494 instructions # 2.13 insns per cycle ( +- 0.00% )
91,3949,1806 cycles ( +- 2.44% )
1.146683817 seconds time elapsed ( +- 2.88% )
(2) thread = 8 個
Execution time of raytracing() : 0.772257 sec
----------------------------------------------------
Performance counter stats for './raytracing_thread 8' (10 runs):
7,0822 cache-misses ( +- 4.22% )
194,8258,7802 instructions # 1.62 insns per cycle ( +- 0.00% )
120,3381,1433 cycles ( +- 2.18% )
0.991003226 seconds time elapsed ( +- 10.45% )
(3) thread = 12 個
Execution time of raytracing() : 0.743515 sec
----------------------------------------------------
Performance counter stats for './raytracing_thread 12' (10 runs):
7,0021 cache-misses ( +- 2.33% )
194,2522,0067 instructions # 1.43 insns per cycle ( +- 0.00% )
135,4591,5705 cycles ( +- 0.52% )
0.729297521 seconds time elapsed ( +- 1.31% )
- [ ]比較不同切割法
Software pipeline
gcc option
這個方法利用了 pipeline 的概念，將一個 instruction 分成許多stage，因此每個 instruction 之間的順序就很重要，如果一個 instruction 需要的資料是是上一次 instrction 才剛做完處理而還未存回 memory，如此可能造成讀入的資料錯誤的情況，這樣的資料則有相依性，如果可以減少 stage bubble，使每個 stage 充份利用可以提高效率。這方面就牽涉到每個 instruction 的不同，考慮每個 instruction 的不同做安排，但是現代 compiler 通常會有 out of order 的功能，所以就算在寫 code 時刻意安排過順序，最後 compile 的結果也不一定會依照 code 的排序執行。
(1)
這邊我利用 GCC 所提供的 option做編譯，-fsel-sched-pipelining、-fselective-scheduling，出來的結果有快了一點點，大概是個位數趴數的降低，並不是非常明顯，甚至可能是誤差範圍，不能確定是否因為真的用到的 software pipeline 的原理。
Performance counter stats for './raytracing' (10 runs):
3,5974 cache-misses ( +- 3.88% )
194,6533,9114 instructions # 2.32 insns per cycle ( +- 0.00% )
83,8537,5118 cycles ( +- 0.62% )
2.561081869 seconds time elapsed ( +- 0.68% )
(2)
一般的 software pipeline 都是在組語的層級去做分析和改動，譬如：將 load 這一類需要花費較多時間的 Instruction 先處理，也可以降低資料相依性的問題所造成的問題。我用了同樣的原理，先將 raytracing() 中的 sample 做 loop unrolling 之後將裏面的事情分成了4個 stage，將這4個 stage 做重新的排序。
