2017q1 Homework1 (raytracing)
contributed by <stanleytazi>
Reviewed by rayleigh0407
- 建議可以把執行結果做成圖表, 如此較好去觀察其變化 (例如比較 POSIX thread 數目及效能關係)
tags: stanleytazi
學習目標
- 可以善用 gprof 分析程式效能
- 根據作業要求提示可以學習 POSIX Thread, OpenMP, software pipelining, 以及 loop unrolling 等用法以及優缺點
未修改版本
- 執行結果
# Rendering scene
Done!
Execution time of raytracing() : 3.403861 sec
- gprof 結果
$ 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()orraytracing()這些是有呼叫到其他function的，這邊的數據是代表什意義呢？ - How to read gprof output
根據上面文章，應該是指執行時間扣掉 children 所執行的時間
- 根據gprof給的定義是代表該function所有執行時間佔總執行時間的百分比
-
gprof ( call graph )
- 在 call graph裡可以看出每個function所花費的時間，以及在內部所call的每個function的次數
+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 處理的時間，並繪製成圖:- 可以發現藍色部份位於球體的地方，表示處理時間是比較長的
- 可以發現藍色部份位於球體的地方，表示處理時間是比較長的
POSIX Thread
thread輪流拿工作來做(in_turn)
- 這邊一開始的想法是先不用作任何的partition，每個thread做完一個 pixel 後會去拿下一個尚未被執行的 pixel 來做，總共有4個thread輪流完成工作
- 優點是不會有分工不均的問題
- 缺點是有critical section需要保護，所以有可能會block
住 thread
Inraytracing.c(ray_pixel()):
// 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 拆解
- 改法如下
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>
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
- 這邊並未看出有太大效能的提昇
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
-
Any changes
Be notified of any changes
-
Mention me
Be notified of mention me
-
Unsubscribe
Subscribe