# 回顧 2016q1 Homework1
###### tags: `sysprog2016`
:::info
主講人: [jserv](http://wiki.csie.ncku.edu.tw/User/jserv) / 課程討論區: [2016 年系統軟體課程](https://www.facebook.com/groups/system.software2016/)
:mega: 返回「[進階電腦系統理論與實作](http://wiki.csie.ncku.edu.tw/sysprog/schedule)」課程進度表
:::

## 風雨生信心
* 連續兩天颱風假，你在作什麼？ [有一群人風雨無阻](https://www.facebook.com/JservFans/posts/974778805981787)
* 堅定地用程式碼解決各種難題。人生不必一定完美，但必須精彩

## compute-pi
* [CheHsuan](https://github.com/CheHsuan/compute-pi): [共筆](https://hackmd.io/s/BkbydgVa)
* 研究 Monte Carlo 法求圓周率，並嘗試透過 GPU 來加速，獲得初步成果
* 「蒙地卡羅方法」(Monte Carlo method)，也就是透過利用亂數取樣 (random sampling) 模擬來解決數學問題。第二次世界大戰期間，Monte Carlo 方法被系統性地應用於科學研究中，誕生了 MANIAC (Mathematical Analyzer, Numerical Integrator and Computer)，而 Stanislaw Ulam、John von Neumann、Nicholas Metropolis、Enrico Fermi 等人發展法一種基於樣本統計的方法，來解決關於在原子彈設計中，中子隨機擴散問題和 Schrodinger 等式的特徵值估計問題。該方法的原理最初是 Stanislaw Ulam 闡述的，後來由 John von Neumann 深入研究，於 1949 年發表一篇名為 "The Monte Carlo method" 的論文而聞名，當然，到了進入電腦時代，這個方法才得以由原本手動產生亂數來解決問題，變成實際性的數值方法。
* Monte Carlo 方法是由 Nicholas Metropolis 所命名，取自其亂數機率有如賭博一般，而恰似北非最西側的摩洛哥首都 Monte Carlo，也就是知名賭城，種種奇豔動人的賭場生活寫照。所有具有隨機效應的過程，均可能以 Monte Carlo 方法大量模擬單一事件，並藉由統計上平均值，獲得某設定條件下實際最可能測量值，更廣泛來說，自然界裏的布朗運動、電波的噪音、基因的突變、交通即時路況等等，無處不含有隨機的變化，均有可適用的場合。
* 這方法可以高度平行化，CG裡的Ray Tracing與分子動態模擬都用到。

:::info
由交通大學陳穎平教授補充:

Nicholas Metropolis et al 於 1953 年 [1] 提出了 Metropolis algorithm [2]。
Metropolis algorithm 這個名詞可能知道的人比較少，但下個名詞應該就不少人知道了 -- simulated annealing (好像中文是叫「模擬退火法」) [3]。
Simulated annealing 因為容易實作又萬用，被用在極多工程和科學領域最佳化問題的處理上，它當年可是被發表在 Science 上哩

[1] [Metropolis N, Rosenbluth A, Rosenbluth M, Teller A, Teller E. Equations of state calculations
by fast computing machines. J Chem Phys. 1953;21(6):1087–92.](http://scitation.aip.org/content/aip/journal/jcp/21/6/10.1063/1.1699114)
[2] [Bhanot G, Reports on Progress in Physics, Volume 51, Number 3](http://iopscience.iop.org/article/10.1088/0034-4885/51/3/003/meta)
[3] [Kirkpatrick S, Gelatt CD Jr, Vecchi MP. Optimization by simulated annealing. Science. 1983;220:671–80.](http://science.sciencemag.org/content/220/4598/671)
:::
* [kaizsv](https://github.com/kaizsv/compute-pi): [共筆](https://hackmd.io/s/rJIFNnO6)
* 用幾何來逼近 PI，原理是圓的內接多邊形邊長CD。而圓周 `2 * PI * R` 就可以求出近似 PI 值
* [oiz5201618](https://github.com/oiz5201618): [共筆](https://hackmd.io/s/BJdYsOPa)
* 透過 clock_gettime() 函式取得數值時，研究了 95% 信賴區間，分析前，要了解自己的資料是透過取樣去預測母體或者對資料母體作運算，兩者的 95% 信賴區間的算法不同。
* 可分為「直接運算母體」和「從母體取樣本」，一併留意樣本資料數和標準差計算的議題。
* [shelly4132](https://github.com/shelly4132): [共筆](https://hackmd.io/s/HJrLU0dp)
* 研究 AVX loop-unrolling 的實做版本時，藉由 error rate 分析，她發現在 N 的值在 1000 結尾時，計算出來的結果與落差很大
* 額外研究 Leibniz formula for π 的證明方式
* [TempoJiJi](https://github.com/TempoJiJi): [共筆](https://hackmd.io/s/Hy7tssw6)
* 藉由 Leibniz formula for π 搭配不同的實做方式，從而比較 OpenMP 和 AVX 版本的效能落差，過程中，他也留意到 time(), gettimeofday(), clock_gettime() 函式執行時期的差異。

## raytracing
* [hugikun999](https://github.com/hugikun999/raytracing): [共筆](https://hackmd.io/s/HyHhgcv6)
* 利用 gprof2dot 工具，將最耗時的函式與呼叫的路徑視覺化，隨後他做了頗多 OpenMP 的實驗
* LanKuDot: [共筆](https://hackmd.io/s/rkggUeKa)
* 解讀了光線追蹤程式。以函式 raytracing 來說，傳入場景必要的物件：長方面 (牆)、球體、光源、背景色、攝影機位置及視角、攝影機畫面 (輸出圖片) 的長寬。
* 先計算以攝影機平面為基準的 vector space 的 basis vector，將結果存在 vector u, v, w。SAMPLES：為了反鋸齒 (MSAA，多重採樣反鋸齒法)，設定成取樣四個 pixel 作為該 pixel 的顏色。
* 觀察 raytracing 後，提出 raytracing 程式可進行平行化之處:
* 整張圖的運算切割：row 分, column 分或 block 分。缺點是每一個 pixel 的呼叫熱度不一樣，所以如果切出來熱度過於集中在某個 block，平行化的效果不高;
* 模糊化處理：每個 sample 做完運算後，再取平均;
* RGB：RGB 的計算結果是不互相干擾的，可以個別平行加。缺點 ray_color 計算完顏色一次輸出 RGB，如果每個 thread 只取其中一個值會太浪費;

## clz
* workfunction: [共筆](https://hackmd.io/s/Byyd3nua)
* 發現給定的作業程式碼存在一些缺陷，是的，這是我們在課堂常講「程式碼是寫來給你改良，不是給你欣賞或背誦用的」，於是他花了一些心思去修正。
* 工程師的使命是解決問題，而我們現在的訓練就是培養同學們具備相關的能力、視野，以及態度。
* ktvexe: [共筆](https://hackmd.io/s/BJBZn6Q6)
* 研究最多 5 次 branch 的 byte-shift 實做以及不需要 branch 的 Harley’s algorithm
* 輸入數值的區段為 100000000~100016382 與直覺有很大的落差，這表示我們要重新思考以下:
* 測量時間的方法: clz 的實做往往只要少許的 cycle count，光透過 clock_gettime 一類的函式在典型的 GNU/Linux 下，往往無法取得精準的時間;
* 考慮到現代處理器的設計，branch predictor 表現越來越好，如果我們對單一數值進行 clz 運算多次，往往會得到比預期好的結果，這時候要重新規劃實做方式
* 精確來說, 現今 Modern Processor 對於 Divergence 所套用的技巧已不只是 "Prediction", 在 Intel P6 架構建構了名為 "Dynamic Execution Engine", 在進展到了 Core 架構時名為"Wide Dynamic Execution"統合了包含 data flow analysis, speculative execution, out of order execution 以及 super scalar. 還有(Intel 獨家?) MacroFusion 的特性
* 而其中 out-of-order execution 搭配 predictor + speculative execution 對於 divergence 的效果是驚人的, 在能了解其原理, 減少 data dependency 的前提下, 就能寫出效能不錯的 branch code

## phonebook
* 0140454: [共筆](https://hackmd.io/s/Bkx3cYX6)
* 觀察程式中所使用的 words.txt，他發現，輸入已照字典序排序好，接著他思考：「如果把資料打亂再測試一次的話，結果是否會有所不同？」
* 他打亂後發現，未優化前與前兩種方式所受到的影響比較小。而，trie 和 red-black tree 的方式，均有明顯的不同。原因在於順序的不同，導致在維護樹的時候有所差異。
* 下一步，應該尋找一個適當的lastname dataset來做測試，因為words.txt中包含了許多沒有名字意義的單字。
* 考慮用詞彙庫代替phonebook，挑戰會高很多也實用多了，就隨機輸入一篇專業文章然後逐步搜尋字彙。詞彙庫可以用微軟的: https://www.microsoft.com/Language/zh-tw/Terminology.aspx
* nekoneko: [共筆](https://hackmd.io/s/rJCs_ZVa)
* 引入 hash function 來改寫電話簿的搜尋機制時，針對 h(x) = x mod M 形式的函數，用不同的 M 帶入，發現 hash value 分佈落差很大
* 延伸閱讀: MIT 線上課程 [10. Dictionaries](https://www.youtube.com/watch?v=Mf9Nn9PbGsE) (video)
* 單純將字元直接相加就是 lose-lose hash function
* 可參考這篇: [Hash Functions](http://www.cse.yorku.ca/~oz/hash.html)
* 另外 hash function 做 mod 出來如果呈現 uniform distribution 才是最好的，搜尋每一個 bucket 的 worst case 都差不多，而像 lose-lose 遇到 worst case 就糟糕了
* jkrvivian: [共筆](https://hackmd.io/s/SyOQgOQa)
* 觀察修改 data representation 對於 cache miss 和整體執行時間的衝擊外，她嘗試引入字串壓縮演算法，想研究 SMAZ 一類的字串壓縮演算法，對於 cache 的影響。
* 因為我們給定的字典檔跟現實落差太大，所以常見的字串壓縮演算法往往無法發揮作用，會得到比原本字串還長的輸出，導致反效果。不過，如果善用壓縮演算法，針對特定的情況，會有幫助。
* 實驗的精神、方法，以及最後如何解讀並且提出新的假設再持續調整，非常重要
* louielu: [共筆](https://hackmd.io/s/BJjL6cQ6)
* 研究 perf 資料的同時，花了很多時間研究究竟如何精準測量執行時間 (再多核心系統中，這件事越來越困難)，他從 PMU 的原理開始研讀，交叉對照 Intel® 64 and IA-32 Architectures Developer’s Manual，知曉 perf event 背後的議題，他也著手翻譯了部份技術文件，相當難得。
* __builtin___clear_cache 可清除指定範圍內的 instruction cache，實做在 GNU Toolchain 提供的 libgcc 中。呂同學還注意到給定的 linked list 實做上，透過 e = append(line, e) 這種方式來 append，可以降低一般 linked list append 需要 O(n) 的時間，可是必須要維護一個 list head，這是很重要的發現