2016q3 HW1-computing pi

目標

• 學習透過離散微積分求圓周率
  • Leibniz formula for π
  • 積分計算圓周率π
  • Function
• 著手透過 SIMD 指令作效能最佳化

按照作業步驟實作，併將問題紀錄

• 取得原始程式碼並編譯:

$ git clone https://github.com/sysprog21/compute-pi
$ cd compute-pi
$ make check

• 結果
  • 注意Makefile
    編譯多了-fopenmp、-mavx，觀察Makefile。
    • CFLAGS = -O0 -std=gnu99 -Wall -fopenmp -mavx
  • user、system、elapsed、cpu、swaps time表示？

gcc -O0 -std=gnu99 -Wall -fopenmp -mavx computepi.o time_test.c -DBASELINE -o time_test_baseline
gcc -O0 -std=gnu99 -Wall -fopenmp -mavx computepi.o time_test.c -DOPENMP_2 -o time_test_openmp_2
gcc -O0 -std=gnu99 -Wall -fopenmp -mavx computepi.o time_test.c -DOPENMP_4 -o time_test_openmp_4
gcc -O0 -std=gnu99 -Wall -fopenmp -mavx computepi.o time_test.c -DAVX -o time_test_avx
gcc -O0 -std=gnu99 -Wall -fopenmp -mavx computepi.o time_test.c -DAVXUNROLL -o time_test_avxunroll
gcc -O0 -std=gnu99 -Wall -fopenmp -mavx computepi.o benchmark_clock_gettime.c -o benchmark_clock_gettime

time ./time_test_baseline
N = 400000000 , pi = 3.141593
1.26user 0.00system 0:01.27elapsed 99%CPU (0avgtext+0avgdata 1716maxresident)k
0inputs+0outputs (0major+83minor)pagefaults 0swaps
time ./time_test_openmp_2
N = 400000000 , pi = 3.141593
1.40user 0.00system 0:00.70elapsed 198%CPU (0avgtext+0avgdata 1720maxresident)k
0inputs+0outputs (0major+86minor)pagefaults 0swaps
time ./time_test_openmp_4
N = 400000000 , pi = 3.141593
2.80user 0.00system 0:00.78elapsed 356%CPU (0avgtext+0avgdata 1844maxresident)k
0inputs+0outputs (0major+91minor)pagefaults 0swaps
time ./time_test_avx
N = 400000000 , pi = 3.141593
0.82user 0.00system 0:00.83elapsed 99%CPU (0avgtext+0avgdata 1640maxresident)k
0inputs+0outputs (0major+83minor)pagefaults 0swaps
time ./time_test_avxunroll
N = 400000000 , pi = 3.141593
0.68user 0.00system 0:00.68elapsed 99%CPU (0avgtext+0avgdata 1716maxresident)k
0inputs+0outputs (0major+87minor)pagefaults 0swaps

• make gencsv
  • 看不太懂這程式的功用，參考。

$ make gencsv

結果

for i in `seq 100 5000 25000`; do \
	printf "%d," $i;\
	./benchmark_clock_gettime $i; \
done > result_clock_gettime.csv	

理解

• Makefile有個gencsv，功用是將default的程式都代入i值，併透過gettime計算程式運算時間，將結果轉換成csv檔輸出。

• time的功能。

  • $ time 會報告實際時間，也就是程式從開始到結束的經歷時間，另外還會計算程式使用處理器時間量。
  ​$ time ./time_test_baseline
  

  結果

  ​N = 400000000 , pi = 3.141593
  
  ​real	0m1.268s
  ​user	0m1.268s
  ​sys	0m0.000s
  

• real user system time參考作業

  • real time：也就是 Wall-clock time，也就是現實世界中實際經過的時間，是由 kernel 裡的 xtime 來紀錄，系統每次啟動時會先從設備上的 RTC 上讀入 xtime。
  • user time：表示程式在 user mode 佔用所有的 CPU time 總和
  • system time：表示程式在 kernel mode 佔用所有的 CPU time 總和 ( 直接或間接的系統呼叫 )。

• real time = user time + system time? No.

  • 考慮如果有多條threads，程序在cpu運算時間會是所有threads的總和。
  • 如程序有包含sleep()，並不會佔用cpu time。

延伸思考:

• clock(), clock_gettime() 的使用
  • clock()計算user time，clock_gettime()計算real time
• time(), gettimeofday() 的使用
• 為什麼 clock_gettime() 結果飄忽不定？
• 為什麼 time() 和 gettimeofday() 不適合拿來作 benchmark ?

gnuplot

• using [a：b] : 以第a column當x座標,第b column當y座標
• 比較效能圖，發現圖形很抖，理想上應該要線性的才對。
• openmp2與avxunroll效果最佳。
• openmp4圖形跳動很大，要調查。

信賴區間(Confidence Interval)

Steps:

​​​​計算平均值

​​​​計算標準差(standard deviation)

​​​​平均值的正負標準差乘以 2 就是 95% 信賴區間

標準差算法
1.母體整體進行實驗。
2.從母體中取樣本數進行實驗。

使用信賴區間作量測。由於用到sqrt這個函式，include要加入math，因為sqrt的資料庫在math中，且編譯器要加-lm，不然會有linker error。要透過編譯器去編譯從math資料庫去選取所需資料這個行為。

The linker is missing the implementation of sqrt(). It resides in the library libm.

Tell GCC to add it by applying the option -lm.

double compute_aver(double time_pi[]) {
	double mean = 0;
	double variance_value=0;
	double standard_deviation=0; 
	double low_end=0;
	double up_end = 0;
	double final_array[sample];
	double result = 0;
	int final_array_length = 0;

	int i;
	//compute mean
	for(i=0; i < sample; i++) {
		mean += time_pi[i];
	}
	mean = mean / sample;

	//compute standard_deviation
	for(i=0; i < sample; i++) {
		variance_value += (time_pi[i] - mean) * (time_pi[i] - mean); 
	}
	variance_value = variance_value / sample;
	standard_deviation = sqrt(variance_value);

	//find lower_endpoint & upper_endpoint
	low_end = mean - 2 * standard_deviation;
	up_end = mean + 2 * standard_deviation;

	//delete point out of range
	for(i=0; i < sample; i++) { 
		if(time_pi[i] >= low_end && time_pi[i] < up_end) 
		final_array[final_array_length] = time_pi[i];
		final_array_length++;
		
	}

	//compute result
	for(i = 0; i < final_array_length; i++){
		result += final_array[i];
	}

	result = result / final_array_length;

	return result;

}