分享到plurk 分享到twitter 分享到facebook

2016q1 Homework #2

預期目標

  • 學習效能分析工具
  • 學習 GNU Toolchain

標注須知

下方只要是 $ 開頭,就表示在 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
  • raytracing 程式執行完畢,將輸出名為 out.ppm 的檔案,可透過 eog 或在圖形界面點擊開啟。參考輸出: ray_tracing
  • 操作提示:
    • 透過 convert 這個工具可將 PPM 轉為 PNG 或其他格式,如:

      convert out.ppm out.png
    • make check 會檢驗程式碼輸出的圖片是否符合預期,符合的話會得到綠色的 “OK!” 字樣

GDB (GNU Debugger)

  • GDB Rocks!
  • GDB 筆記
  • 以 GDB 重新學習 C 語言程式設計
  • GDB Manual
  • 透過 GDB 進行 unit testing,可參見張晏誠同學的共筆
  • 取得預先準備好的 unit-tests,來驗證我們開發的 singly-linked list:

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

作業要求 (A)

  • 在 GitHub 上 fork raytracing,並思考如何改善程式效能
  • make PROFILE=1 重新編譯程式碼,並且學習 gprof
  • gprof 指出效能瓶頸,並且著手改寫檔案 math-toolkit.h 在內的函式實做,充分紀錄效能差異在共筆
  • 可善用 POSIX Thread, OpenMP, software pipelining, 以及 loop unrolling 一類的技巧來加速程式運作
  • 將你的觀察、分析,以及各式效能改善過程,並善用 gnuplot 製圖,紀錄於「作業區」,記得標注「開發紀錄(A)」

作業要求 (B)

  • 在 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)」

截止日期

  • Mar 21, 2016 (含) 之前
  • 越早在 GitHub 上有動態、越早接受 code review,評分越高

參考資料