2016q1 Homework #2

預期目標

下方只要是 $ 開頭，就表示在 GNU/Linux 的終端機裡面輸入的指令，比方說 $ sudo apt-get update，就表示要輸入 sudo apt-get update。

參照 2016q1: Homework1 的指示，在實體機器安裝 GNU/Linux 和相關的開發套件
- 注意: 不得透過虛擬機器，因為我們在意實際機器上的效能
安裝以下開發工具

$ sudo apt-get update
$ sudo apt-get install graphviz
$ sudo apt-get install imagemagick

光線追蹤 (Ray tracing) 是三維電腦圖形學中的描繪演算法 (rendering algorithm)，跟蹤從眼睛發出的光線，而非是光源發出的光線，藉由預先編排好的場景，以數學模型顯現出來，可得到類似於光線投射與掃描線描繪方法的結果，對於反射與折射，可有更準確的模擬效果，效率非常高，所以當追求高品質的效果時，經常使用這種方法
在物理學中，光線追跡可以用來計算光束在介質中傳播的情況。在介質中傳播時，光束可能會被介質吸收，改變傳播方向或者射出介質表面等。我們通過計算理想化的窄光束（光線）通過介質中的情形來解決這種複雜的情況
在實際應用中，可將各種電磁波或者微小粒子看成理想化的窄波束（即光線），基於這種假設，人們利用光線追跡來計算光線在介質中傳播的情況。光線追跡方法首先計算一條光線在被介質吸收，或者改變方向前，光線在介質中傳播的距離，方向以及到達的新位置，然後從這個新的位置產生出一條新的光線，使用同樣的處理方法，最終計算出一個完整的光線在介質中傳播的路徑
成大資訊系師生合作開發原始程式碼僅 650 行的光線追蹤 C 語言程式: raytracing
取得原始程式碼、編譯和測試:

$ git clone https://github.com/embedded2016/raytracing.git && cd raytracing
$ make
$ ./raytracing

出現 # Rendering scene 字樣後，請保持耐心，等待程式輸出 Done! 字樣，參考輸出:

Execution time of raytracing() : 2.994175 sec

$ git clone https://github.com/embedded2016/unit-tests.git && cd unit-tests
$ make
$ make check

檔案 data-swap.in 為輸入，格式為:
- 第 1 行是用來給 list 的長度，如 4，GDB 會透過程式去建立一個有 4 個 node 的 linked list
- 第 2 行與第 3 行是預計要的 node，從 head 開始算 (包含自己) 的第 N 個 node
檔案 data-bubble.in 為輸入，格式為:
- 第 1 行指定 List 的長度，如 3，GDB 會透過程式去建立一個有 3 個 node 的 linked list
- 第 2 行為 linked list 每個 node 的初始值，如 12 4 5 就表示 list = {12, 4, 5}

在 GitHub 上 fork raytracing，並思考如何改善程式效能
以 make PROFILE=1 重新編譯程式碼，並且學習 gprof
- 參考使用 GNU gprof 進行 Linux 平台的程式分析
以 gprof 指出效能瓶頸，並且著手改寫檔案 math-toolkit.h 在內的函式實做，充分紀錄效能差異在共筆
- 注意: 請勿更動編譯器最佳化選項 -O0 (關閉最佳化)
- 檔案 math-toolkit.h 定義的若干數學操作函式很重要，可參考 SIMD optimized dot and cross product functions 和 2015q3 Homework #1 Ext
可善用 POSIX Thread, OpenMP, software pipelining, 以及 loop unrolling 一類的技巧來加速程式運作
將你的觀察、分析，以及各式效能改善過程，並善用 gnuplot 製圖，紀錄於「作業區」，記得標注「開發紀錄(A)」

在 GitHub 上 fork unit-tests，並依據第三週課堂 code review 的認知，指出給定程式不足之處
補強給定程式的 swap() 和 bubble_sort() 函式，並且研究如何用 GDB 進行自動測試
實做 Merge sort，可參見競技程式設計課程的解說，需要提供以下檔案:
- merge.c: merge_sort() 函式的實做
- test-merge.sh: 測試 merge_sort() 函式的 GDB script
- data-merge.in: 用來測試的輸入資料，原則上與 data-bubble.in 相仿
將你學習 GDB 的過程、指出原本程式不足之處 (程式碼寫出來就是給你改進的，可不是給你背誦用！)、如何修正和強化程式，以及在實做 merge sort 的各項啟發，紀錄於「作業區」，記得標注「開發紀錄(B)」