# 2016q3 Homework2 (raytracing)
contributed by <`mingnus`>

###### tags: `raytracing` `gprof` `perf` `profiling` `sysprog`

## 環境設定

* Intel Celeron N3150 CPU, 8GB DDR3 RAM
* Ubuntu 16.04.1, kernel 4.4.0-38
* gcc (Ubuntu 5.4.0-6ubuntu1~16.04.2) 5.4.0 20160609
* GLIBC 2.23-0ubuntu3

## gprof

另開專頁記錄: [gprof 說明與心得](https://hackmd.io/s/HyFU355EQ)

## Raytracing program

由gprof flat profile可看出下列向量運算是最花時間的部分:

* subtract_vector()
* dot_product()
* multiply_vector()
* add_vector()
...

## Experiments

### Loop unrolling + pthread平行運算

1. 向量運算函式以loop unrolling改寫
2. 以多執行緒同時繪製畫面不同pixels (問題: raytracing每個pixel真的都是獨立運算? pixel運算順序是否影響結果?)

採用scanline rendering: 考量畫面各區域複雜度不同[[1]](
https://embedded2016.hackpad.com/ep/pad/static/bLGQtRraTES), 為平均運算複雜度, 每個thread各自負責scanlines #(thread_id + k * nr_threads)

如果採用tiled rendering且tile面積又很大時, 程式速度將受制於負責最複雜區域的thread (e.g., cinebench)

barrier實作參考concurrent-ll
https://github.com/gavra0/ConcLinkedList

FIXME: handle trailing rows

### Result

* Loop unrolling大約可節省1/3運算時間
* 4-threads比gcc -O3快, 輸出的ppm checksum也相同
但是用gprof看, 多執行緒的vector function呼叫次數卻比單執行緒少?


## 研究中項目

### SIMD

https://gcc.gnu.org/onlinedocs/gcc-5.4.0/gcc/x86-Options.html

gcc預設就有開啟SSE (根據build machine CPU決定, 待查), 以dot_product()為例:

* simd_t.c:

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; 
}

* Disassemble dot_product() (注意大小寫):

$ gcc -c simd_t.c -g -O0
$ objdump [-Mintel] -d simd_t.o > simd_t.s

00000000000000b6 <dot_product>:
  b6:	55                   	push   %rbp
  b7:	48 89 e5             	mov    %rsp,%rbp
  ba:	48 89 7d e8          	mov    %rdi,-0x18(%rbp)
  be:	48 89 75 e0          	mov    %rsi,-0x20(%rbp)
  c2:	66 0f ef c0          	pxor   %xmm0,%xmm0
  c6:	f2 0f 11 45 f8       	movsd  %xmm0,-0x8(%rbp)
  cb:	c7 45 f4 00 00 00 00 	movl   $0x0,-0xc(%rbp)
  d2:	eb 46                	jmp    11a <dot_product+0x64>
  d4:	8b 45 f4             	mov    -0xc(%rbp),%eax
  d7:	48 98                	cltq   
  d9:	48 8d 14 c5 00 00 00 	lea    0x0(,%rax,8),%rdx
  e0:	00 
  e1:	48 8b 45 e8          	mov    -0x18(%rbp),%rax
  e5:	48 01 d0             	add    %rdx,%rax
  e8:	f2 0f 10 08          	movsd  (%rax),%xmm1
  ec:	8b 45 f4             	mov    -0xc(%rbp),%eax
  ef:	48 98                	cltq   
  f1:	48 8d 14 c5 00 00 00 	lea    0x0(,%rax,8),%rdx
  f8:	00 
  f9:	48 8b 45 e0          	mov    -0x20(%rbp),%rax
  fd:	48 01 d0             	add    %rdx,%rax
 100:	f2 0f 10 00          	movsd  (%rax),%xmm0
 104:	f2 0f 59 c1          	mulsd  %xmm1,%xmm0
 108:	f2 0f 10 4d f8       	movsd  -0x8(%rbp),%xmm1
 10d:	f2 0f 58 c1          	addsd  %xmm1,%xmm0
 111:	f2 0f 11 45 f8       	movsd  %xmm0,-0x8(%rbp)
 116:	83 45 f4 01          	addl   $0x1,-0xc(%rbp)
 11a:	83 7d f4 02          	cmpl   $0x2,-0xc(%rbp)
 11e:	7e b4                	jle    d4 <dot_product+0x1e>
 120:	f2 0f 10 45 f8       	movsd  -0x8(%rbp),%xmm0
 125:	5d                   	pop    %rbp
 126:	c3                   	retq   

所以我們應該用資料寬度更大的ymm暫存器及AVX指令，才有機會勝過上述ASM code
如果用gcc -mavx option, 則gcc只是把SSE指令換成AVX指令, 並沒有使用ymm暫存器, 實測速度也沒有變快
* pxor => vxorpd
* movsd => vmovsd
* mulsd => vmulsd
* addsd => vaddsd

使用-mno-sse無法通過編譯 (待查)

### Fast inverse square root
https://en.wikipedia.org/wiki/Fast_inverse_square_root
http://213style.blogspot.tw/2014/07/john-carmack.html
*Hacker's Delight, 2/e*, Ch.11-1 and 17-4

## 其他

* 程式分析
* 世界座標: 右手座標, Z軸在上
* 場景物件(models.inc): 白球1, 金屬球2, 綠球3; 白矩型1, 紅矩型2, 藍矩型3