owned this note
owned this note
Published
Linked with GitHub
<style>
h2.part{color:#0099B0;}
h3.part{color:#D92424;}
h4.part{color:#005BB0;}
h5.part{color:#FD6F0A;}
h6.part{color:#4400B0;}
</style>
# 2017q1 Homework2 (raytracing)
contributed by <`paul5566`>
## 開發目標
敝魯非資工科系因此我會先以讀懂code為主學習做最簡單的方法,操作界面工具開發。
- **開發環境**
- **無腦測試**
- **使用==GDB==分析Raytracing程式**
- **分析程式找出優化方法**
- **多做簡單的範例了解優化方法**
### 開發環境
#### Lubuntu 16.04 LTS
系統效能-指令
```
$ lscpu
```
- CPU: Intel(R) Core(TM) i5-3210M CPU @ 2.50GHz
- Mem: 8 GB
- Cache:
L1d cache: 32 KB
L1i cache: 32 KB
L2 cache: 256 KB
L3 cache: 4096 KB
### 無腦照做
一開始在寫完loop unrolling的範例後,肥宅我好興奮R!!!
開始想說很無腦的把每個for迴圈都寫進去。但這樣跟世間情和好無助還有那些藍藍路政客有什麼兩樣。
我們應該要對症下藥,所以第一步應該先run程式碼,去看makefile跑一遍。再來根據前人經驗,使用gprof去針對最耗時的地方去處理。
```
ifeq ($(strip $(PROFILE)),1)
PROF_FLAGS = -pg
CFLAGS += $(PROF_FLAGS)
LDFLAGS += $(PROF_FLAGS)
endif
```
因此我們應該輸入下列指令
```
$ make PROFILE=1
```
然後compiler會吐出來
```
cc -std=gnu99 -Wall -O0 -g -pg -c -o main.o main.c
cc -o raytracing objects.o raytracing.o main.o -lm -pg
```
PS：可以對照makefile裡面的東西便會了解
這時候我們可以再執行raytracing這個檔案
```
./raytracing
```
執行後會compiler會執行一下然後吐出下列訊息
```
# Rendering scene
Done!
Execution time of raytracing() : 6.300673 sec
```
#### ►執行結果, 耗時 ==6.300673==秒
### gprof
其實一開始我開發就出現了問題,但我實在無解因此我無恥的請了高手幫我解決問題,不然實在在那邊瞎忙。之後應該要誠實面對自己再去探討怎麼解決一些相容性的問題。
- GCC要升級成6.X版
- makefile 加入新的 flag -no-pie
[GCC升級成6.X](http://askubuntu.com/questions/746369/how-can-i-install-and-use-gcc-6-on-xenial)
[gprof解決方案](http://linux.vbird.org/linux_basic/0120howtolinux/0120howtolinux_3.php)
因為實在是有點腦溢血於是偷(ㄑ一）懶（ㄆ一ㄢˋ）自己在參考了別人的[開發筆記](https://hackmd.io/CYFgRgzAnADATGAtDAHCCiRWAY0VAUwEYMBWAnANhgLBmDh1KA==?both)想先弄點成果出來
這邊"| less"這個用法是顯示比較少的東西讓我們方便閱讀
這個可以參考[25 Linux commands for System Administrators](https://www.getfilecloud.com/blog/2014/01/25-linux-commands-for-system-administrators/#.WLvalyGGO00)
```
$ gprof raytracing gmon.out | less
```
然後compiler會吐出這些東西
```
Each sample counts as 0.01 seconds.
% cumulative self self total
time seconds seconds calls s/call s/call name
24.15 0.56 0.56 69646433 0.00 0.00 dot_product
15.96 0.93 0.37 56956357 0.00 0.00 subtract_vector
9.70 1.16 0.23 13861875 0.00 0.00 rayRectangularIntersection
9.27 1.37 0.22 31410180 0.00 0.00 multiply_vector
8.19 1.56 0.19 10598450 0.00 0.00 normalize
5.61 1.69 0.13 17821809 0.00 0.00 cross_product
5.39 1.82 0.13 17836094 0.00 0.00 add_vector
4.74 1.93 0.11 1048576 0.00 0.00 ray_color
```
而我們將會發現這幾個程式就是所謂的熱點,也是我們要optimize的地方
#### dot_product
#### subtract_vector
#### rayRectangularIntersection
#### multiply_vector
### 分析程式找出優化方法
除了homework給的提示外,肥宅我想到用搜尋的方式找出程式在那
```
$ grep -rn 'dot_product'
```
於是compiler將會丟出一些資訊供我們參考
```
./math-toolkit.h:62:double dot_product(const double *v1, const double *v2)
./math-toolkit.h:83: return dot_product(v, tmp);
Binary file ./raytracing.o matches
./raytracing.c:27: double s = dot_product(l, ray_d);
./raytracing.c:28: double l2 = dot_product(l, l);
./raytracing.c:44: if (dot_product(ip->normal, ray_d) > 0.0)
./raytracing.c:61: double det = dot_product(e01, p);
./raytracing.c:74: double alpha = inv_det * dot_product(s, p);
./raytracing.c:82: double beta = inv_det * dot_product(ray_d, q);
./raytracing.c:86: *t1 = inv_det * dot_product(e03, q);
./raytracing.c:96: det = dot_product(e23, p);
./raytracing.c:104: alpha = inv_det * dot_product(s, p);
./raytracing.c:109: beta = inv_det * dot_product(ray_d, q);
./raytracing.c:114: *t1 = inv_det * dot_product(e21, q);
./raytracing.c:121: if (dot_product(ip->normal, ray_d)>0.0)
./raytracing.c:179: double tmp = dot_product(n, l_copy);
./raytracing.c:185: /* diffuse = max(0, dot_product(n, -l)) */
./raytracing.c:186: *diffuse = MAX(0, dot_product(n, l_copy));
```
而在反覆輸入數次其他熱點關鍵字後我們將會發現,關鍵在
##### math-toolkit.h ######
這個標頭檔內,因此我們應該從這邊著手優化
## Raytracing程式優化
### 根據作業要求提示的技巧
- [x]==**Loop unrolling**==
- scheduling
- pipeline
- Force inline
- Pthread
- [x]==**OpenMP**==
### 1. [Loop unrolling](https://www.cs.umd.edu/class/fall2001/cmsc411/proj01/proja/loop.html)
- #### 修改在dmath-toolkit.h dot_product：
```clike=
static inline
double dot_product(const double *v1, const double *v2)
{
double dp = 0.0;
dp += v1[0] * v2[0];
dp += v1[1] * v2[1];
dp += v1[2] * v2[2];
return dp;
}
```
修改完程式想要再測試後記得要下指令
```
$ grep -rn 'dot_product'
```
不然當你再下"make PROFILE=1"的指令回無法過,並且會出現
```
make: Nothing to be done for 'all'.
```
這時候我們可以再執行raytracing這個檔案
```
./raytracing
```
執行後會compiler會執行一下然後吐出下列訊息
```
# Rendering scene
Done!
Execution time of raytracing() : 6.046340 sec
```
這時候我們在用guuplot這個方式試試看
```
Each sample counts as 0.01 seconds.
% cumulative self self total
time seconds seconds calls s/call s/call name
19.82 0.41 0.41 56956357 0.00 0.00 subtract_vector
13.05 0.68 0.27 69646433 0.00 0.00 dot_product
11.84 0.93 0.25 31410180 0.00 0.00 multiply_vector
11.60 1.17 0.24 13861875 0.00 0.00 rayRectangularIntersection
9.43 1.36 0.20 17836094 0.00 0.00 add_vector
7.73 1.52 0.16 13861875 0.00 0.00 raySphereIntersection
6.77 1.66 0.14 10598450 0.00 0.00 normalize
4.35 1.75 0.09 17821809 0.00 0.00 cross_product
4.35 1.84 0.09 4620625 0.00 0.00 ray_hit_object
2.18 1.89 0.05 3838091 0.00 0.00 length
1.93 1.93 0.04 1048576 0.00 0.00 rayConstruction
1.45 1.96 0.03 1048576 0.00 0.00 ray_color
```
原本第一的dot_product降低到了第二個
Google Drive
Gist
Clipboard
Sign in with Wallet
