2016q3 Homework1 (compute-pi)

contributed by <RayPan>

開發環境

Ubuntu 16.04 LTS
CPU

Architecture:          x86_64
CPU op-mode(s):        32-bit, 64-bit
Byte Order:            Little Endian
CPU(s):                4
On-line CPU(s) list:   0-3
Thread(s) per core:    2
Core(s) per socket:    2
Socket(s):             1
NUMA node(s):          1
Vendor ID:             GenuineIntel
CPU family:            6
Model:                 60
Model name:            Intel(R) Core(TM) i5-4200H CPU @ 2.80GHz
Stepping:              3
CPU MHz:               2869.015
CPU max MHz:           3400.0000
CPU min MHz:           800.0000
BogoMIPS:              5587.49
Virtualization:        VT-x
L1d cache:             32K
L1i cache:             32K
L2 cache:              256K
L3 cache:              3072K
NUMA node0 CPU(s):     0-3

開發目標

透過離散微積分求圓周率
- Riemann integral
- Leibniz
透過SIMD指令做效能最佳化

AVX（Advanced Vector Extensions）

指令集
任何程式最後都要編成一條條的指令讓CPU辨識並執行，每一指令對應一個操作，指令集為CPU能執行的所有指令的集合。
簡介
是Intel和AMD x86架構處理器中的指令集，借鏡AMD SSE5設計思路，為一套新一代的完整SIMD指令集規範。
使用方法
- 需#define <immintrin.h>
- __attribute__機制，可以用來設置函數屬性（Function Attribute）、變數(Variable)屬性和類型(Type)屬性。
- aligned規定變數或結構最小對齊格式，以byte為單位。

Duration Time

計算程式的duration time通常可能是指wall-clock time或CPU time

wall-clock time

現實生活實際經過的時間，由kernel內的xtime紀錄，系統每次啟動時會先從設備上的Real Time Clock(RTC)讀取xtime。
CPU time

程式在CPU上運行消耗的時間，若有多條thread，則是計算每條thread的使用時間加總。
很多時候只計算CPU time不夠，因為執行時間還包括I/O time,communication channel delay,synchronization overhead等等。
- 在Unix系統存在兩個time指令，一是系統所提供/usr/bin/time，為了Bourne shell所寫的工具，另一個是C shell內建指令$ time
- $ time會報告實際時間（程式從開始到結束經歷時間），還會計算程式使用處理器時間量。
  1.real time:即wall-clock time。
  2.user time：程式在user mode佔用所有CPU time總和。
  3.sys time：程式在kernel mode佔用所有CPU time總和。
- CPU bound/ I/O bound
  - CPU bound:程式需要大量CPU computation（對CPU time需求大），相比之下僅需少量I/O operation，效能取決於CPU速度。
  - I/O bound：程式需要大量I/O operation，僅需少量CPU computation，效能取決於I/O device速度。
    - real < user：CPU bound，使用平行處理有得到好處，效能提升。
    - real ≒ user：表示程式是 CPU bound，即使使用平行處理，效能也沒有明顯提昇，常見的原因有可能是其實計算量沒有很大，生成、處理、結束多執行緒的 overhead 吃掉所有平行處理的好處，或是程式相依性太高，不適合拿來作平行處理。
    - real > user: 表示程式是 I/O bound，成本大部分為 I/O操作，使得平行處理無法帶來顯著的效能提昇 ( 或沒有提昇)。

Gnuplot

在繪圖中遇到了Skipping data file with no valid points
花了半小時debug
發現原因出在result_clock_gettime.csv
每筆資料間都用逗號隔開
所以必須在runtime.gp內加入set datafile separator "," RayPan

原始程式效能測試

$ make check

time ./time_test_baseline
N = 400000000 , pi = 3.141593
3.34user 0.00system 0:03.34elapsed 99%CPU (0avgtext+0avgdata 1796maxresident)k
0inputs+0outputs (0major+86minor)pagefaults 0swaps
time ./time_test_openmp_2
N = 400000000 , pi = 3.141593
3.42user 0.00system 0:01.71elapsed 199%CPU (0avgtext+0avgdata 1772maxresident)k
0inputs+0outputs (0major+88minor)pagefaults 0swaps
time ./time_test_openmp_4
N = 400000000 , pi = 3.141593
6.77user 0.00system 0:01.71elapsed 395%CPU (0avgtext+0avgdata 1740maxresident)k
0inputs+0outputs (0major+91minor)pagefaults 0swaps
time ./time_test_avx
N = 400000000 , pi = 3.141593
0.97user 0.00system 0:00.97elapsed 99%CPU (0avgtext+0avgdata 1796maxresident)k
0inputs+0outputs (0major+86minor)pagefaults 0swaps
time ./time_test_avxunroll
N = 400000000 , pi = 3.141593
0.94user 0.00system 0:00.94elapsed 99%CPU (0avgtext+0avgdata 1760maxresident)k
0inputs+0outputs (0major+85minor)pagefaults 0swaps

此為baseline的時間消耗（未做openmp)

real	0m3.344s
user	0m3.340s
sys	0m0.000s

此為做了openmp2的時間消耗（可以發現為CPU bound,使用平行處理效能提升）

real	0m1.714s
user	0m3.420s
sys	0m0.000s

此為做了openmp4的時間消耗,效果更為明顯

real	0m1.833s
user	0m7.084s
sys	0m0.016s

改善過程

1.使用Leibniz













double compute_pi_leibniz(size_t N)
{
    double pi = 0;
    double tmp;
    for(size_t i = 124 < N; i++){
        if(i%2 == 0)
            tmp = 1;
        else
            tmp = -1;
        pi += tmp / (2*(double)i+1);
    }
    return pi * 4.0;
}

可以發現做了Leibniz的效能
比做openmp2及openmp4略好一些

2.使用Leibniz AVX及 AVX unroll

可以發現做leibniz的avx及avx unroll都可以明顯提升效能
但仍是baseline版本的avx unroll最佳。

加工中

作業詳細資訊：A03:compute-pi