Try   HackMD

2016q3 Homework1 (raytracing)

contributed by <vic85821>

Reviewed by 0140454

  • 應該善用 .gitignore 來排除測試時由程式所產生的檔案。
    例如 commit "modify by Macro" 中的 output_lu.txt。
  • 應該把非必要的註解刪除後再 commit。
    例如 commit "use OpenMP to improve"。
  • 可使用 gnuplot 來輸出效能比較圖。
  • 未來可嘗試 SIMD 指令來優化並分析其效能及應用環境等。

開發環境

  • Ubuntu 16.04.1 LTS
  • Linux version 4.4.0-38-generic
  • CPU : Intel® Core™ i5-3230M CPU @ 2.60GHz
  • MEM : 8GB
  • L1d cache : 32K
  • L1i cache : 32K
  • L2 cache : 256K
  • L3 cache : 3072K

事前準備

  • 預先裝好軟體
$ sudo apt-get update
$ sudo apt-get install graphviz
$ sudo apt-get install imagemagick

目標

雖然作業很多QAQ,但對我來說,就算都不太懂,只要有學到新的知識,儘管是名詞定義,一點一滴慢慢的跟上,一學期下來一定不同於其他的課程的收穫量!!!

案例分析

  • 在優化之前,先來執行一次看看效能&時間
    Execution time of raytracing() : 3.020114 sec

  • 若使用gprof

$ make PROFILE=1

Execution time of raytracing() : 6.545642 sec
產生 gmon.out 透過 gprof ./raytracing | less 觀察各個function的呼叫次數與使用時間
* less 可以讓結果分頁,有助於觀察

	Each sample counts as 0.01 seconds.
  %   cumulative   self              self     total           
 time   seconds   seconds    calls   s/call   s/call  name    
 21.96      0.54     0.54 69646433     0.00     0.00  dot_product
 15.86      0.93     0.39 56956357     0.00     0.00  subtract_vector
 10.58      1.19     0.26 10598450     0.00     0.00  normalize
  9.97      1.44     0.25 13861875     0.00     0.00  rayRectangularIntersection
  9.97      1.68     0.25 13861875     0.00     0.00  raySphereIntersection
  7.93      1.88     0.20 31410180     0.00     0.00  multiply_vector
  7.52      2.06     0.19 17836094     0.00     0.00  add_vector
  4.88      2.18     0.12  4620625     0.00     0.00  ray_hit_object
  3.25      2.26     0.08 17821809     0.00     0.00  cross_product
  2.44      2.32     0.06  1048576     0.00     0.00  ray_color
  1.83      2.37     0.05  4221152     0.00     0.00  multiply_vectors
  0.81      2.39     0.02  2110576     0.00     0.00  localColor
  0.81      2.41     0.02  1241598     0.00     0.00  protect_color_overflow

  • 偷偷的利用編譯器的最佳化,看一下執行時間(將Makefile裡面的 -O0 改成 -Ofast)
    Execution time of raytracing() : 0.670504 sec

    目標就是超越編譯器最佳化了!!(這個執行速度好快R~ QAQ)

  • 開始著手優化!!!

Loop unrolling

看完功課介紹的video,馬上就來試試看,暴力把LOOP展開!!

  • note : loop unrolling

    • 減少branch prediction 可以增加效率
    • 過多會讓程式可讀性下降 (coding 金字塔!! - readable)

  • 透過gprof可以找出較佔時間的前幾名

  • 將math-toolkit.h定義的一些數學運算function()展開

    • e.g. add_vector(), substract_vector()
/* 舉例 dot_product */
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;
}
  • 緊接著看看執行時間有沒有改變
    Execution time of raytracing() : 2.235425 sec
    時間快了將近1s

OpenMP / Pthread

彼此沒有相依的data就很自然會想到平行化,不過對於OpenMP與Pthread還沒有很了解,因此要先找找資料!!

  • note : OpenMP Pthread
  • 首先,因為不知道我的電腦上的執行緒最多可以到幾個,因此先來寫個小程式順便熟悉OpenMP的用法
  • 這是一個讓每個執行緒都印出一次 Hello!!的程式
#include<stdio.h>
#include<omp.h> //要先include OpenMP library

int main()
{
    #pragma omp parallel // parallel directive 的特殊敘述行
    //block外的data為各個多執行緒所共享,block內部則各自使用
    {
         printf("Hello!!\n");
    }
	
    return 0;
}
  • 編譯指令gcc -fopenmp xxx.c -o xxx要加上-fopenmp才能順利執行
Hello!!
Hello!!
Hello!!
Hello!!

由此執行結果可知 –> 我的電腦有4個執行緒
但如果我想要限制不要使用全部的執行緒,再編譯之後在多加一行export OMP_NUM_THREADS=2即代表我只要使用到其中兩個執行緒

來開始找看看哪裡可以套用OpenMP優化

  • 跟Loop Unrolling改的地方一樣,只是改成openMP
  • 唯一需要注意的,在dot_product()需稍做更動,因為彼此資料是不獨立的
double dot_product(const double *v1, const double *v2)
{
    double dp = 0.0;
    #omp parallel for reduction(+:dp)
    for (int i = 0; i < 3; ++i) {
        dp += v1[i] * v2[i];
    }
    return dp;
}
  • remind : 編譯要多加 -fopenmp !!
  • 緊接著看看執行時間有沒有改變
    Execution time of raytracing() : 1.844765 sec
    結果快超多!!! 快接近編譯器最佳化了!!繼續努力!!

但是使用openMP多執行緒, cache miss反而增加到38.658 %

Performance counter stats for './raytracing' (10 runs):

           124,333      cache-misses #   38.658 % of all cache refs ( +-  8.44% )  (66.47%)

請詳細閱讀 Effects of Multithreading on Cache Performance，不要跳著讀，你需要培養背景知識 jserv

Macro

重新改一下math-toolkit.h
將原本的function重新改成Macro

#define DOT(a,b) ((a[0]*b[0])+(a[1]*b[1])+(a[2]*b[2]))
#define SUB(a,b,out) ((out[0]=a[0]-b[0]),(out[1]=a[1]-b[1]),(out[2]=a[2]-b[2]))
#define ADD(a,b,out) ((out[0]=a[0]+b[0]),(out[1]=a[1]+b[1]),(out[2]=a[2]+b[2]))
#define MULV(a,b,out) ((out[0]=a[0]*b[0]),(out[1]=a[1]*b[1]),(out[2]=a[2]*b[2]))
#define MULC(a,b,out) ((out[0]=a[0]*(b)),(out[1]=a[1]*(b)),(out[2]=a[2]*(b)))

減少程式執行時,call function的時間,因此可以縮短執行時間

Execution time of raytracing() : 1.639391 sec

優化到現在,再用一次gprof來分析程式

 %   cumulative   self              self     total           
 time   seconds   seconds    calls   s/call   s/call  name    
 24.57      0.28     0.28 13861875     0.00     0.00  rayRectangularIntersection
 20.19      0.51     0.23 10598450     0.00     0.00  normalize
 12.73      0.66     0.15 13861875     0.00     0.00  raySphereIntersection
 10.53      0.78     0.12 17821809     0.00     0.00  cross_product
  8.78      0.88     0.10  4221152     0.00     0.00  multiply_vectors
  6.14      0.95     0.07  2110576     0.00     0.00  localColor
  3.51      0.99     0.04  4620625     0.00     0.00  ray_hit_object
  3.51      1.03     0.04  1048576     0.00     0.00  ray_color
  2.63      1.06     0.03  2110576     0.00     0.00  compute_specular_diffuse
  2.19      1.08     0.03  2520791     0.00     0.00  idx_stack_top
  1.76      1.10     0.02  1048576     0.00     0.00  rayConstruction
  0.88      1.11     0.01  1241598     0.00     0.00  protect_color_overflow
  0.88      1.12     0.01  1204003     0.00     0.00  idx_stack_push
  0.88      1.13     0.01  1048576     0.00     0.00  idx_stack_init
  0.88      1.14     0.01        1     0.01     1.14  raytracing
  0.00      1.14     0.00  3838091     0.00     0.00  length
  0.00      1.14     0.00  2558386     0.00     0.00  idx_stack_empty
  0.00      1.14     0.00  1241598     0.00     0.00  reflection

可以看的出來,原本定義再math-toolkit的function都不是排名前幾名了,接著就是想辦法再減少現在當今最消耗時間的部份!!

參考資料

Last changed by 
 
張友誠
0
670
Published on HackMD