2017q1 Homework1 (raytracing)

# 2017q1 Homework1 (raytracing) contributed by <`stanleytazi`> ### Reviewed by `rayleigh0407` * 建議可以把執行結果做成圖表, 如此較好去觀察其變化 (例如比較 POSIX thread 數目及效能關係) ###### tags: `stanleytazi` ## 學習目標 + 可以善用 gprof 分析程式效能 + 根據作業要求提示可以學習 POSIX Thread, OpenMP, software pipelining, 以及 loop unrolling 等用法以及優缺點 ## 未修改版本 + 執行結果 ```shell # Rendering scene Done! Execution time of raytracing() : 3.403861 sec ``` + **gprof** 結果 ```shell $ make clean $ make PROFILE=1 $ ./raytracing $ gprof raytacing gmon.out | less ``` + 以下這數據的解讀有些疑惑，先從 ==% time== 這項討論 + 根據gprof給的定義是代表該function所有執行時間佔總執行時間的百分比 `the percentage of the total running time of the program used by this function.` + 對於沒有呼叫到任何 function 的 function 還可以理解，但是對於`ray_color()` or `raytracing()`這些是有呼叫到其他function的，這邊的數據是代表什意義呢？ + [How to read gprof output](http://www.cs.cornell.edu/courses/cs414/2004fa/gprof.pdf) 根據上面文章，應該是指執行時間扣掉 children 所執行的時間 + gprof ( call graph ) + 在 call graph裡可以看出每個function所花費的時間，以及在內部所call的每個function的次數 ```shell +Each sample counts as 0.01 seconds. % cumulative self self total time seconds seconds calls s/call s/call name 22.76 0.68 0.68 69646433 0.00 0.00 dot_product 19.74 1.27 0.59 56956357 0.00 0.00 subtract_vector 10.21 1.58 0.31 31410180 0.00 0.00 multiply_vector 9.87 1.87 0.30 13861875 0.00 0.00 rayRectangularIntersection 9.04 2.14 0.27 10598450 0.00 0.00 normalize 6.36 2.33 0.19 17836094 0.00 0.00 add_vector 5.35 2.49 0.16 17821809 0.00 0.00 cross_product 5.35 2.65 0.16 4620625 0.00 0.00 ray_hit_object 3.51 2.76 0.11 13861875 0.00 0.00 raySphereIntersection 1.67 2.81 0.05 1048576 0.00 0.00 ray_color 1.67 2.86 0.05 1 0.05 2.99 raytracing 1.51 2.90 0.05 2110576 0.00 0.00 localColor 1.17 2.94 0.04 4221152 0.00 0.00 multiply_vectors 0.84 2.96 0.03 2110576 0.00 0.00 compute_specular_diffuse 0.67 2.98 0.02 1048576 0.00 0.00 rayConstruction 0.33 2.99 0.01 2520791 0.00 0.00 idx_stack_top Call graph (explanation follows)(部份) granularity: each sample hit covers 2 byte(s) for 0.33% of 2.99 seconds index % time self children called name 0.05 2.94 1/1 main [2] [1] 100.0 0.05 2.94 1 raytracing [1] 0.05 2.77 1048576/1048576 ray_color [3] 0.02 0.10 1048576/1048576 rayConstruction [15] 0.00 0.00 1/1 calculateBasisVectors [21] 0.00 0.00 1048576/1048576 idx_stack_init [26] ----------------------------------------------- <spontaneous> [2] 100.0 0.00 2.99 main [2] 0.05 2.94 1/1 raytracing [1] 0.00 0.00 3/3 append_sphere [29] 0.00 0.00 3/3 append_rectangular [28] 0.00 0.00 2/2 append_light [30] 0.00 0.00 1/1 write_to_ppm [35] 0.00 0.00 1/1 delete_rectangular_list [32] 0.00 0.00 1/1 delete_sphere_list [33] 0.00 0.00 1/1 delete_light_list [31] 0.00 0.00 1/1 diff_in_second [34] ----------------------------------------------- 1354679 ray_color [3] 0.05 2.77 1048576/1048576 raytracing [1] [3] 94.3 0.05 2.77 1048576+1354679 ray_color [3] 0.16 1.80 4620625/4620625 ray_hit_object [4] 0.03 0.36 2110576/2110576 compute_specular_diffuse [9] 0.05 0.18 2110576/2110576 localColor [12] 0.07 0.00 2596277/10598450 normalize [11] 0.00 0.04 1241598/1241598 reflection [16] 0.03 0.00 3169934/31410180 multiply_vector [10] 0.03 0.00 2483196/56956357 subtract_vector [7] 0.00 0.02 1241598/1241598 refraction [18] 0.01 0.00 2520791/2520791 idx_stack_top [19] 0.01 0.00 686738/17836094 add_vector [13] 0.00 0.00 113297/113297 fresnel [20] 0.00 0.00 3724794/3838091 length [22] 0.00 0.00 1241598/1241598 protect_color_overflow [24] 0.00 0.00 1204003/1204003 idx_stack_push [25] 0.00 0.00 37595/37595 idx_stack_pop [27] 1354679 ray_color [3] ``` + pixels 個別執行時間 + 如果想要利用 multi-thread 那要考慮如何分配每個thread的所要處理的事情 + 利用`clock_gettime()` 抓出每個pixel 處理的時間，並繪製成圖: + 可以發現藍色部份位於球體的地方，表示處理時間是比較長的 ![](https://i.imgur.com/N4tB1rP.png) ## POSIX Thread ### thread輪流拿工作來做(in_turn) + 這邊一開始的想法是先不用作任何的partition，每個thread做完一個 pixel 後會去拿下一個尚未被執行的 pixel 來做，總共有4個thread輪流完成工作 + 優點是不會有分工不均的問題 + 缺點是有critical section需要保護，所以有可能會block 住 thread In` raytracing.c(ray_pixel())`: ```clike // critical section while(1) { ... pthread_mutex_lock(&mtx); info->total_num++; info->w_idx++; if (info->w_idx >= info->width) { info->h_idx++; info->w_idx = 0; } hIdx = info->h_idx; wIdx = info->w_idx; pthread_mutex_unlock(&mtx); ... } ``` + 執行結果(20次平均) **1.529197 seconds** ### critical section 改成 atomic 的 operation + ### 把 pixels 按照 height index 分給不同thread + 另一種想法是避免有critical section，提前先把工作分好，這樣的問題是會有可能工作量分配不均，導致有些thread做完了事情，但其他thread可能還在做 + 如果有thread_i, i=0, 1, 2, ..., A-1，共有A個thread，則thread_i 所要處理的height的index會是 i+Aj, j=0,1,2... + 執行時間 (20次平均) (unit: seconds) + 2個thread:1.758365 + 4個thread:1.543278 + 6個thread:1.559132 + 8個thread:1.535096 + 執行時間在4個thread 之後並未隨著可以看到 thread 增多而減少 ## Loop unrolling + 4 個 thread + in turn: 1.053478 + cycle partition: 1.043785 + 可以看出loop unrolling對於效能的提昇是有將近30% ### dot_product 拆解 + 改法如下 ```clile static inline double dot_product(const double *v1, const double *v2) { double dp0 = 0.0, dp1 = 0.0, dp2 = 0.0; dp0 = v1[0] * v2[0]; dp1 = v1[1] * v2[1]; dp2 = v1[2] * v2[2]; return dp0 + dp1 + dp2; } ``` + assembly code 很好奇這樣的改動對於指令的影響 <**before**> ``` 000000000000041b <dot_product>: 41b: 55 push %rbp 41c: 48 89 e5 mov %rsp,%rbp 41f: 48 89 7d e8 mov %rdi,-0x18(%rbp) 423: 48 89 75 e0 mov %rsi,-0x20(%rbp) 427: 66 0f ef c0 pxor %xmm0,%xmm0 42b: f2 0f 11 45 f8 movsd %xmm0,-0x8(%rbp) 430: 48 8b 45 e8 mov -0x18(%rbp),%rax 434: f2 0f 10 08 movsd (%rax),%xmm1 438: 48 8b 45 e0 mov -0x20(%rbp),%rax 43c: f2 0f 10 00 movsd (%rax),%xmm0 440: f2 0f 59 c1 mulsd %xmm1,%xmm0 444: f2 0f 10 4d f8 movsd -0x8(%rbp),%xmm1 449: f2 0f 58 c1 addsd %xmm1,%xmm0 44d: f2 0f 11 45 f8 movsd %xmm0,-0x8(%rbp) 452: 48 8b 45 e8 mov -0x18(%rbp),%rax 456: 48 83 c0 08 add $0x8,%rax 45a: f2 0f 10 08 movsd (%rax),%xmm1 45e: 48 8b 45 e0 mov -0x20(%rbp),%rax 462: 48 83 c0 08 add $0x8,%rax 466: f2 0f 10 00 movsd (%rax),%xmm0 46a: f2 0f 59 c1 mulsd %xmm1,%xmm0 46e: f2 0f 10 4d f8 movsd -0x8(%rbp),%xmm1 473: f2 0f 58 c1 addsd %xmm1,%xmm0 477: f2 0f 11 45 f8 movsd %xmm0,-0x8(%rbp) 47c: 48 8b 45 e8 mov -0x18(%rbp),%rax 480: 48 83 c0 10 add $0x10,%rax 484: f2 0f 10 08 movsd (%rax),%xmm1 488: 48 8b 45 e0 mov -0x20(%rbp),%rax 48c: 48 83 c0 10 add $0x10,%rax 490: f2 0f 10 00 movsd (%rax),%xmm0 494: f2 0f 59 c1 mulsd %xmm1,%xmm0 498: f2 0f 10 4d f8 movsd -0x8(%rbp),%xmm1 49d: f2 0f 58 c1 addsd %xmm1,%xmm0 4a1: f2 0f 11 45 f8 movsd %xmm0,-0x8(%rbp) 4a6: f2 0f 10 45 f8 movsd -0x8(%rbp),%xmm0 4ab: 5d pop %rbp 4ac: c3 retq ``` <**after**> ```clike= 000000000000041b <dot_product>: 41b: 55 push %rbp 41c: 48 89 e5 mov %rsp,%rbp 41f: 48 89 7d d8 mov %rdi,-0x28(%rbp) 423: 48 89 75 d0 mov %rsi,-0x30(%rbp) 427: 66 0f ef c0 pxor %xmm0,%xmm0 42b: f2 0f 11 45 e8 movsd %xmm0,-0x18(%rbp) 430: 66 0f ef c0 pxor %xmm0,%xmm0 434: f2 0f 11 45 f0 movsd %xmm0,-0x10(%rbp) 439: 66 0f ef c0 pxor %xmm0,%xmm0 43d: f2 0f 11 45 f8 movsd %xmm0,-0x8(%rbp) 442: 48 8b 45 d8 mov -0x28(%rbp),%rax 446: f2 0f 10 08 movsd (%rax),%xmm1 44a: 48 8b 45 d0 mov -0x30(%rbp),%rax 44e: f2 0f 10 00 movsd (%rax),%xmm0 452: f2 0f 59 c1 mulsd %xmm1,%xmm0 456: f2 0f 11 45 e8 movsd %xmm0,-0x18(%rbp) 45b: 48 8b 45 d8 mov -0x28(%rbp),%rax 45f: 48 83 c0 08 add $0x8,%rax 463: f2 0f 10 08 movsd (%rax),%xmm1 467: 48 8b 45 d0 mov -0x30(%rbp),%rax 46b: 48 83 c0 08 add $0x8,%rax 46f: f2 0f 10 00 movsd (%rax),%xmm0 473: f2 0f 59 c1 mulsd %xmm1,%xmm0 477: f2 0f 11 45 f0 movsd %xmm0,-0x10(%rbp) 47c: 48 8b 45 d8 mov -0x28(%rbp),%rax 480: 48 83 c0 10 add $0x10,%rax 484: f2 0f 10 08 movsd (%rax),%xmm1 488: 48 8b 45 d0 mov -0x30(%rbp),%rax 48c: 48 83 c0 10 add $0x10,%rax 490: f2 0f 10 00 movsd (%rax),%xmm0 494: f2 0f 59 c1 mulsd %xmm1,%xmm0 498: f2 0f 11 45 f8 movsd %xmm0,-0x8(%rbp) 49d: f2 0f 10 45 e8 movsd -0x18(%rbp),%xmm0 4a2: f2 0f 58 45 f0 addsd -0x10(%rbp),%xmm0 4a7: f2 0f 58 45 f8 addsd -0x8(%rbp),%xmm0 4ac: 5d pop %rbp 4ad: c3 retq ``` 試著去理解兩個assembly code 的作法: <**before**> 以下動作在整個dot_product會重複做三次，所以內積運算中，每個方向的相乘結果都跟前一次有關連 ``` 430: 48 8b 45 e8 mov -0x18(%rbp),%rax 434: f2 0f 10 08 movsd (%rax),%xmm1 //從*v1取值到%xmm1 438: 48 8b 45 e0 mov -0x20(%rbp),%rax 43c: f2 0f 10 00 movsd (%rax),%xmm0 //從*v2取值到%xmm0 440: f2 0f 59 c1 mulsd %xmm1,%xmm0 //再將 %xmm0 與 %xmm1 相乘後把結果放到 %xmm0 444: f2 0f 10 4d f8 movsd -0x8(%rbp),%xmm1 449: f2 0f 58 c1 addsd %xmm1,%xmm0 //將前一次運算結果從stack mov 到 %xmm1 後與這次運算的結果做相加 44d: f2 0f 11 45 f8 movsd %xmm0,-0x8(%rbp) //將這次運算的結果放回 stack ``` **<after>** ``` 442: 48 8b 45 d8 mov -0x28(%rbp),%rax 446: f2 0f 10 08 movsd (%rax),%xmm1 44a: 48 8b 45 d0 mov -0x30(%rbp),%rax 44e: f2 0f 10 00 movsd (%rax),%xmm0 //各從兩個vector取出對應的同一個方向分量 452: f2 0f 59 c1 mulsd %xmm1,%xmm0 456: f2 0f 11 45 e8 movsd %xmm0,-0x18(%rbp) //相乘後把結果放到 stack裡 ``` 可以看到 **<after>** 三個方向分量的計算彼此間並沒有相依性，如果是這樣的話有機會作到一些pipeline的效果嘛？ + 4 個 thread + in turn: 1.065790 + cycle partition: 1.048646 + 這邊並未看出有太大效能的提昇 ```shell Each sample counts as 0.01 seconds. % cumulative self self total time seconds seconds calls us/call us/call name 16.62 0.53 0.53 7808832 0.07 0.07 dot_product 13.62 0.96 0.43 1668622 0.26 0.26 cross_product 10.92 1.30 0.35 8326100 0.04 0.04 subtract_vector 9.18 1.59 0.29 1105613 0.26 0.26 normalize 8.87 1.87 0.28 976700 0.29 2.05 ray_hit_object 8.39 2.14 0.27 2160821 0.12 0.27 raySphereIntersection 7.60 2.38 0.24 4416024 0.05 0.05 multiply_vector 5.38 2.55 0.17 1753786 0.10 0.61 rayRectangularIntersection 4.75 2.70 0.15 88022 1.71 33.75 ray_color 3.32 2.80 0.11 1810792 0.06 0.06 add_vector 2.22 2.87 0.07 192586 0.36 0.63 rayConstruction 1.90 2.93 0.06 ray_pixel 1.74 2.99 0.06 219993 0.25 0.83 localColor 1.58 3.04 0.05 230711 0.22 1.80 compute_specular_diffuse 1.11 3.07 0.04 301584 0.12 0.12 multiply_vectors ``` ## OpenMP +

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.