# 2016q3 Homework1 (raytracing)
contributed by <`TotallyWrong`>
###### tags: `TotallyWrong` `On going`
### ::: Reviewd by <`andy19950`>
- 使用很多種方法來嘗試修改 dot_product 很好，但是這份程式碼還有很多修改後可以增加效能的地方，可以詳讀程式碼後嘗試看看其他部份的優化。
- 有把程式碼轉成組合語言來做判斷，如果能夠了解組語的變動的原因後簡單的告訴我們 "為何這樣會造成執行時間增加" 會更好。
- 這份報告比較欠缺圖表分析的方式來顯示不同方式之間的差異，比較不直觀一點。
- 最後就是這個部份的 github 連結是錯的，記得把它修改過來。
---
## 開發作業環境
**CPU** : Intel Core i5-5200U
**Cache size**: L1 Cache 128KB, L2 Cache 512K, L3 Cache 3072KB
**Operating System** : Ubuntu 15.10 Wily Werewolf
---
**Feature**:
* MMX instructions
* SSE / Streaming SIMD Extensions
* SSE2 / Streaming SIMD Extensions 2
* SSE3 / Streaming SIMD Extensions 3
* SSSE3 / Supplemental Streaming SIMD Extensions 3
* SSE4 / SSE4.1 + SSE4.2 / Streaming SIMD Extensions 4 ?
* AES / Advanced Encryption Standard instructions
* AVX / Advanced Vector Extensions
* AVX2 / Advanced Vector Extensions 2.0
---
## 使用 Ubuntu 15.10
### 安狀相關開發工具
```
$ sudo apt-get update
$ sudo apt-get install graphviz
$ sudo apt-get install imagemagick
```
---
### 程式測試
----
跑完第一次Test Run 結果
```
Each sample counts as 0.01 seconds.
% cumulative self self total
time seconds seconds calls s/call s/call name
27.18 0.69 0.69 69646433 0.00 0.00 dot_product
21.27 1.23 0.54 56956357 0.00 0.00 subtract_vector
9.45 1.47 0.24 13861875 0.00 0.00 rayRectangularIntersection
7.48 1.66 0.19 31410180 0.00 0.00 multiply_vector
6.70 1.83 0.17 13861875 0.00 0.00 raySphereIntersection
4.73 1.95 0.12 17836094 0.00 0.00 add_vector
4.73 2.07 0.12 10598450 0.00 0.00 normalize
4.33 2.18 0.11 17821809 0.00 0.00 cross_product
3.94 2.28 0.10 4620625 0.00 0.00 ray_hit_object
1.97 2.33 0.05 1048576 0.00 0.00 ray_color
1.58 2.37 0.04 4221152 0.00 0.00 multiply_vectors
1.18 2.40 0.03 2520791 0.00 0.00 idx_stack_top
1.18 2.43 0.03 2110576 0.00 0.00 localColor
1.18 2.46 0.03 1 0.03 2.53 raytracing
0.79 2.48 0.02 2110576 0.00 0.00 compute_specular_diffuse
0.79 2.50 0.02 1048576 0.00 0.00 rayConstruction
0.39 2.51 0.01 3838091 0.00 0.00 length
0.39 2.52 0.01 1241598 0.00 0.00 refraction
0.39 2.53 0.01 1204003 0.00 0.00 idx_stack_push
```
---
原始檔案跑完時的gprof_out.txt 結果顯示前幾個就如同老師的影片中顯示 dot_product function 被叫最多次。
而利用Perf跑cache-misses就算清空cache，cache- miss的比例還是有時多有時少，但是時間上則大致差不多。
---
再閱讀[rnic](https://embedded2016.hackpad.com/2016q1-Homework-2A-GalzL151aZc)學長的筆記，我也嘗試了建立利gprof2dot建立CallGraph來使用對了解來說很好用。
---
使用gprof2dot前請先裝 python
```
sudo apt-get install python graphviz
```
使用 Xdot 請先安裝
```
sudo apt-get install xdot
```
---
### 嘗試改善方法
### 方法一： ###
嘗依如老師再影片中所提到的強制compiler進行inline的作法，在Google搜尋後找到的[語法](https://gcc.gnu.org/onlinedocs/gcc/Inline.html)
---
結果大約有0.1秒的改進，但似乎點難已確認因為測試多次結果都有浮動，在改善很小時難已確認。
>有發現似乎電腦再執行他程式的話對cache test 的時間結果有影響
### 方法二： ###
接下來嘗試把幾個主要的記算函式的回圈展開，這個作法主要是為了減少branch所造成的Control Harzard。我把最常見的前3個Function dot_product，subtract_vector, multiply_vector都Ｕrolling 。
---
```
Performance counter stats for './raytracing' (50 runs):
122,126 cache-misses # 22.979 % of all cache refs
552,830 cache-references
11,826,508,383 instructions # 2.25 insns per cycle
5,238,499,149 cycles
1.969861040 seconds time elapsed ( +- 0.19% )
```
在加總方法一和方法二整體約改善一秒鐘。
---
### 方法三 ： ###
接下來就繼續嘗試使用SIMD，雖然在影片中似乎有人嘗試過而效果並不好，但還是需要了解一下使用方法而且測試一下。[**AVX**](https://software.intel.com/en-us/articles/using-avx-without-writing-avx-code)
在讀過相關資料後了解大致上，Scalar 就是拿一個比較大的記憶體來裝數個較小的值來進行同時運算, 以下兩個網頁是讓我了解SIMD和如何在GCC中使用這種記憶體。
---
第3個網頁是搜尋到有人對dot_product 的研究，似乎AVX在相當大的Vector的dot_product還是有幫助。
[**什麼是SIMD,**](https://www.kernel.org/pub/linux/kernel/people/geoff/cell/ps3-linux-docs/CellProgrammingTutorial/BasicsOfSIMDProgramming.html) [**怎麼在GCC上Code_Intel_SIMD,**](http://www.codeproject.com/Articles/874396/Crunching-Numbers-with-AVX-and-AVX) [**Dot Product 的改善**](http://blog.theincredibleholk.org/blog/2012/12/10/optimizing-dot-product/)
---
Dot Product 的程式碼被改成如下
```clike=
inline double dot_product(const double *v1, const double *v2) __attribute__((always_inline));
double dot_product(const double *v1, const double *v2)
{
double dp=0.0;
/* Initialize AVX vector */
__m256d v1vector = _mm256_set_pd(v1[0],v1[1],v1[2],0);
__m256d v2vector = _mm256_set_pd(v2[0],v2[1],v2[2],0);
/* Compute the product between the two vectors */
__m256d result = _mm256_mul_pd(v1vector,v2vector);
/* Sum the elements of the result vector */
double* f = (double*)&result ;
dp= f[0]+f[1]+f[2]+f[3] ;
return dp;
}
```
---
經過測試時間變長了
```
#Rendering scene
Done!
Execution time of raytracing() : 4.320740 sec
```
而檢查Assembly Code 似乎建構SIMD的Assembly Code很長跟原始資表雖然幾乎沒有使用到Jmp的code，不知道這是否可以解釋為使用這種資料結構的成本不小。
```
//static inline
inline double dot_product(const double *v1, const double *v2) __attribute__((always_inline));
double dot_product(const double *v1, const double *v2)
{
3f4: 4c 8d 54 24 08 lea r10,[rsp+0x8]
3f9: 48 83 e4 e0 and rsp,0xffffffffffffffe0
3fd: 41 ff 72 f8 push QWORD PTR [r10-0x8]
401: 55 push rbp
402: 48 89 e5 mov rbp,rsp
405: 41 52 push r10
407: 48 81 ec 28 01 00 00 sub rsp,0x128
40e: 48 89 bd d8 fe ff ff mov QWORD PTR [rbp-0x128],rdi
415: 48 89 b5 d0 fe ff ff mov QWORD PTR [rbp-0x130],rsi
41c: 64 48 8b 04 25 28 00 mov rax,QWORD PTR fs:0x28
423: 00 00
425: 48 89 45 e8 mov QWORD PTR [rbp-0x18],rax
429: 31 c0 xor eax,eax
double dp=0.0;
42b: c5 f9 57 c0 vxorpd xmm0,xmm0,xmm0
42f: c5 fb 11 85 e0 fe ff vmovsd QWORD PTR [rbp-0x120],xmm0
436: ff
/* Initialize AVX vector */
__m256d v1vector = _mm256_set_pd(v1[0],v1[1],v1[2],0);
437: 48 8b 85 d8 fe ff ff mov rax,QWORD PTR [rbp-0x128]
43e: 48 83 c0 10 add rax,0x10
442: c5 fb 10 00 vmovsd xmm0,QWORD PTR [rax]
446: 48 8b 85 d8 fe ff ff mov rax,QWORD PTR [rbp-0x128]
44d: 48 83 c0 08 add rax,0x8
451: c5 fb 10 08 vmovsd xmm1,QWORD PTR [rax]
455: 48 8b 85 d8 fe ff ff mov rax,QWORD PTR [rbp-0x128]
45c: c5 fb 10 10 vmovsd xmm2,QWORD PTR [rax]
460: c5 fb 11 95 e8 fe ff vmovsd QWORD PTR [rbp-0x118],xmm2
467: ff
468: c5 fb 11 8d 18 ff ff vmovsd QWORD PTR [rbp-0xe8],xmm1
46f: ff
470: c5 fb 11 85 20 ff ff vmovsd QWORD PTR [rbp-0xe0],xmm0
477: ff
478: c5 f9 57 c0 vxorpd xmm0,xmm0,xmm0
47c: c5 fb 11 85 28 ff ff vmovsd QWORD PTR [rbp-0xd8],xmm0
483: ff
/* Create the vector [A B C D]. */
extern __inline __m256d __attribute__((__gnu_inline__, __always_inline__, __artificial__))
_mm256_set_pd (double __A, double __B, double __C, double __D)
{
return __extension__ (__m256d){ __D, __C, __B, __A };
484: c5 fb 10 85 e8 fe ff vmovsd xmm0,QWORD PTR [rbp-0x118]
48b: ff
48c: c5 fb 10 8d 18 ff ff vmovsd xmm1,QWORD PTR [rbp-0xe8]
493: ff
494: c5 f1 14 c8 vunpcklpd xmm1,xmm1,xmm0
498: c5 fb 10 85 20 ff ff vmovsd xmm0,QWORD PTR [rbp-0xe0]
49f: ff
4a0: c5 fb 10 95 28 ff ff vmovsd xmm2,QWORD PTR [rbp-0xd8]
4a7: ff
4a8: c5 e9 14 c0 vunpcklpd xmm0,xmm2,xmm0
4ac: c4 e3 7d 18 c1 01 vinsertf128 ymm0,ymm0,xmm1,0x1
4b2: c5 fd 29 85 50 ff ff vmovapd YMMWORD PTR [rbp-0xb0],ymm0
4b9: ff
__m256d v2vector = _mm256_set_pd(v2[0],v2[1],v2[2],0);
4ba: 48 8b 85 d0 fe ff ff mov rax,QWORD PTR [rbp-0x130]
4c1: 48 83 c0 10 add rax,0x10
4c5: c5 fb 10 00 vmovsd xmm0,QWORD PTR [rax]
4c9: 48 8b 85 d0 fe ff ff mov rax,QWORD PTR [rbp-0x130]
4d0: 48 83 c0 08 add rax,0x8
4d4: c5 fb 10 08 vmovsd xmm1,QWORD PTR [rax]
4d8: 48 8b 85 d0 fe ff ff mov rax,QWORD PTR [rbp-0x130]
4df: c5 fb 10 10 vmovsd xmm2,QWORD PTR [rax]
4e3: c5 fb 11 95 f0 fe ff vmovsd QWORD PTR [rbp-0x110],xmm2
4ea: ff
4eb: c5 fb 11 8d 00 ff ff vmovsd QWORD PTR [rbp-0x100],xmm1
4f2: ff
4f3: c5 fb 11 85 08 ff ff vmovsd QWORD PTR [rbp-0xf8],xmm0
4fa: ff
4fb: c5 f9 57 c0 vxorpd xmm0,xmm0,xmm0
4ff: c5 fb 11 85 10 ff ff vmovsd QWORD PTR [rbp-0xf0],xmm0
506: ff
507: c5 fb 10 85 f0 fe ff vmovsd xmm0,QWORD PTR [rbp-0x110]
50e: ff
50f: c5 fb 10 8d 00 ff ff vmovsd xmm1,QWORD PTR [rbp-0x100]
516: ff
517: c5 f1 14 c8 vunpcklpd xmm1,xmm1,xmm0
51b: c5 fb 10 85 08 ff ff vmovsd xmm0,QWORD PTR [rbp-0xf8]
522: ff
523: c5 fb 10 95 10 ff ff vmovsd xmm2,QWORD PTR [rbp-0xf0]
52a: ff
52b: c5 e9 14 c0 vunpcklpd xmm0,xmm2,xmm0
52f: c4 e3 7d 18 c1 01 vinsertf128 ymm0,ymm0,xmm1,0x1
535: c5 fd 29 85 70 ff ff vmovapd YMMWORD PTR [rbp-0x90],ymm0
53c: ff
53d: c5 fd 28 85 50 ff ff vmovapd ymm0,YMMWORD PTR [rbp-0xb0]
544: ff
545: c5 fd 29 45 90 vmovapd YMMWORD PTR [rbp-0x70],ymm0
54a: c5 fd 28 85 70 ff ff vmovapd ymm0,YMMWORD PTR [rbp-0x90]
551: ff
552: c5 fd 29 45 b0 vmovapd YMMWORD PTR [rbp-0x50],ymm0
}
extern __inline __m256d __attribute__((__gnu_inline__, __always_inline__, __artificial__))
_mm256_mul_pd (__m256d __A, __m256d __B)
{
return (__m256d) ((__v4df)__A * (__v4df)__B);
557: c5 fd 28 45 90 vmovapd ymm0,YMMWORD PTR [rbp-0x70]
55c: c5 fd 59 45 b0 vmulpd ymm0,ymm0,YMMWORD PTR [rbp-0x50]
/* Compute the product between the two vectors */
__m256d result = _mm256_mul_pd(v1vector,v2vector);
561: c5 fd 29 85 30 ff ff vmovapd YMMWORD PTR [rbp-0xd0],ymm0
568: ff
/* Sum the elements of the result vector */
double* f = (double*)&result ;
569: 48 8d 85 30 ff ff ff lea rax,[rbp-0xd0]
570: 48 89 85 f8 fe ff ff mov QWORD PTR [rbp-0x108],rax
dp= f[0]+f[1]+f[2]+f[3] ;
577: 48 8b 85 f8 fe ff ff mov rax,QWORD PTR [rbp-0x108]
57e: c5 fb 10 08 vmovsd xmm1,QWORD PTR [rax]
582: 48 8b 85 f8 fe ff ff mov rax,QWORD PTR [rbp-0x108]
589: 48 83 c0 08 add rax,0x8
58d: c5 fb 10 00 vmovsd xmm0,QWORD PTR [rax]
591: c5 f3 58 c0 vaddsd xmm0,xmm1,xmm0
595: 48 8b 85 f8 fe ff ff mov rax,QWORD PTR [rbp-0x108]
59c: 48 83 c0 10 add rax,0x10
5a0: c5 fb 10 08 vmovsd xmm1,QWORD PTR [rax]
5a4: c5 fb 58 c1 vaddsd xmm0,xmm0,xmm1
5a8: 48 8b 85 f8 fe ff ff mov rax,QWORD PTR [rbp-0x108]
5af: 48 83 c0 18 add rax,0x18
5b3: c5 fb 10 08 vmovsd xmm1,QWORD PTR [rax]
5b7: c5 fb 58 c1 vaddsd xmm0,xmm0,xmm1
5bb: c5 fb 11 85 e0 fe ff vmovsd QWORD PTR [rbp-0x120],xmm0
5c2: ff
return dp;
5c3: c5 fb 10 85 e0 fe ff vmovsd xmm0,QWORD PTR [rbp-0x120]
5ca: ff
}
5cb: 48 8b 45 e8 mov rax,QWORD PTR [rbp-0x18]
5cf: 64 48 33 04 25 28 00 xor rax,QWORD PTR fs:0x28
5d6: 00 00
5d8: 74 05 je 5df <dot_product+0x1eb>
5da: e8 00 00 00 00 call 5df <dot_product+0x1eb>
5df: 48 81 c4 28 01 00 00 add rsp,0x128
5e6: 41 5a pop r10
5e8: 5d pop rbp
5e9: 49 8d 62 f8 lea rsp,[r10-0x8]
5ed: c3 ret
```
---
### 方法四 ： ###
Software Pipelinling
[**SoPiP**](http://www.cs.cmu.edu/afs/cs/academic/class/15745-s12/public/lectures/L19-Software-Pipelining-1up.pdf) [**DotPSoPip**](http://www.fic.udc.es/files/asignaturas/81STR/anexos/dsp6m09.pdf)
```clike=
static inline
double dot_product(const double *v1, const double *v2)
{
double dp = 0.0;
for (int i = 0; i < 3; i++)
dp+=v1[i]*v2[i];
return dp;
}
```
原始的Dot Prodcut碼。
---
```clike=
static inline
double dot_product(const double *v1, const double *v2)
{
double dp = 0.0;
double pro ;
for (int i = 0; i < 3; i++)
{
pro = v1[i] * v2[i];
dp = dp + pro;
}
return dp;
}
```
嘗試Software Pipeline。
---
Software Pipeline Dot Product 的效果似乎不是很好甚至比原始作法差，也許是我沒有做成功。
---
試著Output assembly code 看看Software Pipeline 是否有成功
[**GCC Assembly Code**](http://stackoverflow.com/questions/1289881/using-gcc-to-produce-readable-assembly)
```
objdump -d -M intel -S raytracing.o > AssembOr.txt
```
---
發現因為還要加作一個Pro的空間和多做加的動作，也許是因Software Pipeline的目的是增加Throughput而因為這個Forloop只跑三圈所以能夠增加的Throughput有限所以顯現不出效果。
```
for (int i = 0; i < 3; i++)
409: c7 45 f4 00 00 00 00 mov DWORD PTR [rbp-0xc],0x0
410: eb 46 jmp 458 <dot_product+0x64>
dp+=v1[i]*v2[i];
412: 8b 45 f4 mov eax,DWORD PTR [rbp-0xc]
415: 48 98 cdqe
417: 48 8d 14 c5 00 00 00 lea rdx,[rax*8+0x0]
41e: 00
41f: 48 8b 45 e8 mov rax,QWORD PTR [rbp-0x18]
423: 48 01 d0 add rax,rdx
426: f2 0f 10 08 movsd xmm1,QWORD PTR [rax]
42a: 8b 45 f4 mov eax,DWORD PTR [rbp-0xc]
42d: 48 98 cdqe
42f: 48 8d 14 c5 00 00 00 lea rdx,[rax*8+0x0]
436: 00
437: 48 8b 45 e0 mov rax,QWORD PTR [rbp-0x20]
43b: 48 01 d0 add rax,rdx
43e: f2 0f 10 00 movsd xmm0,QWORD PTR [rax]
442: f2 0f 59 c1 mulsd xmm0,xmm1
446: f2 0f 10 4d f8 movsd xmm1,QWORD PTR [rbp-0x8]
44b: f2 0f 58 c1 addsd xmm0,xmm1
44f: f2 0f 11 45 f8 movsd QWORD PTR [rbp-0x8],xmm0
```
原始Code的Assembly
```
double pro ;
for (int i = 0; i < 3; i++)
409: c7 45 ec 00 00 00 00 mov DWORD PTR [rbp-0x14],0x0
410: eb 4c jmp 45e <dot_product+0x6a>
{
pro = v1[i] * v2[i];
412: 8b 45 ec mov eax,DWORD PTR [rbp-0x14]
415: 48 98 cdqe
417: 48 8d 14 c5 00 00 00 lea rdx,[rax*8+0x0]
41e: 00
41f: 48 8b 45 d8 mov rax,QWORD PTR [rbp-0x28]
423: 48 01 d0 add rax,rdx
426: f2 0f 10 08 movsd xmm1,QWORD PTR [rax]
42a: 8b 45 ec mov eax,DWORD PTR [rbp-0x14]
42d: 48 98 cdqe
42f: 48 8d 14 c5 00 00 00 lea rdx,[rax*8+0x0]
436: 00
437: 48 8b 45 d0 mov rax,QWORD PTR [rbp-0x30]
43b: 48 01 d0 add rax,rdx
43e: f2 0f 10 00 movsd xmm0,QWORD PTR [rax]
442: f2 0f 59 c1 mulsd xmm0,xmm1
446: f2 0f 11 45 f8 movsd QWORD PTR [rbp-0x8],xmm0
dp += pro;
44b: f2 0f 10 45 f0 movsd xmm0,QWORD PTR [rbp-0x10]
450: f2 0f 58 45 f8 addsd xmm0,QWORD PTR [rbp-0x8]
455: f2 0f 11 45 f0 movsd QWORD PTR [rbp-0x10],xmm0
```
SoftWare Pipline的Assmbly
在閱讀**SoPiP**時我也看到那位講師是把Software Pipeline跟Loop Unrolling做比較而他說Software Pipeline 比較好是因為 Unrolling 的技巧還是要branch，但是目前我們dotProduct只有三圈所以可以完全Unroll也許因為這樣要做出比Ｕrolling 更有效的Software Pipeline 大概不太可能。
---
### 方法五 ： ###
在作業說明中還有OpenMP還有POSIX Thread 還沒有嘗試，先試試OpenMP
完全不懂OpenMP，所以用我最常解決問題的方法[Youtube](https://www.youtube.com/watch?v=nE-xN4Bf8XI&list=PLLX-Q6B8xqZ8n8bwjGdzBJ25X2utwnoEG)
```
gcc -fopenmp filename.c
```
要Compile OpenMP 只要Flag fopemp
```
export OMP_NUM_THREADS=4
```
設定線程的數量
---
在看了部份Inetel Youtube 的課程前就現來試試看，在看之前的Callgraph 顯示約 94%的 Function Call都是ray_color所以因此試著在此Funcation做Parallel。
Sign in with Wallet
Connect another wallet