owned this note   changed 8 years ago  
Linked with GitHub

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() or raytracing()這些是有呼叫到其他function的，這邊的數據是代表什意義呢？
    • How to read gprof output
      根據上面文章，應該是指執行時間扣掉 children 所執行的時間

  • 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
      In raytracing.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

OpenMP

Select a repo