# 回顧 2016q1 Homework3

###### 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)」課程進度表
:::

## 回顧與檢討
* [案例研究: Miquido內的程式碼審查](https://softnshare.wordpress.com/2016/10/12/miquidocodereviewbyupsource/)
* xkcd: [前人的智慧](http://xkcd.tw/979), [自動化](http://xkcd.tw/1319), [技術支援流程圖](http://xkcd.tw/627), [學術界 vs 商業界](http://xkcd.tw/664)
* [Strategy: Stop Using Linked-Lists](http://highscalability.com/blog/2013/5/22/strategy-stop-using-linked-lists.html)
* video: [Bjarne Stroustrup: Why you should avoid Linked Lists](https://www.youtube.com/watch?v=YQs6IC-vgmo)
* [Performance of array vs linked-list on modern computers](https://www.linkedin.com/pulse/performance-array-vs-linked-list-modern-computers-dat-hoang-tien)
* [A tale of an impossible bug: big.LITTLE and caching](http://www.mono-project.com/news/2016/09/12/arm64-icache/)

## software-pipelining
- [ ] carolc0708: [共筆](https://hackmd.io/s/B1lDZtO0)
* 研讀 "When Prefetching Works, When It Doesn’t, and Why" 論文，詳實紀錄不理解之處，接著開始進行一系列實驗，包含 SIMD-friendly 的寫法。
* 為了理解 prefetch distance 該如何設定，就需要先知道 memory latency 的時間和 loop 中 instruction 執行的時間，透過 Intel® Memory Latency Checker (mlc) 得知 latency 後，重新做了 AVX 實驗。

- [ ] kobeyu: [共筆](https://hackmd.io/s/BycRx2EC)
* 比照直覺的 C 程式, SSE, SSE + prefetch 效能分佈製圖。
* 在程式碼中，prefetch 的距離是根據 PFDIST 的設定值，實驗分別測試 D=0/4/8/12/16 的執行時間，以結果來看，執行時間的關係為 `D=8 < D=4,12 < D=16 < D=0`
* 說明了 prefetch 的距離會影響到執行效能，其中 D=0 尤其明顯。另外觀察到一個有趣的現象，就是無論D是等於多少，都會比沒有加 prefetch 的 SSE 版本還要來得快。
* 接著他將 Distance 固定在 8，改變 prefetch 的位置(TO/T1/T2/NTA)，執行的結果是 NTA 最花時間。
* prefetch 先將所需要的資料載入快取記憶體降低了 cache-misses 進而減少了執行時間。重新思考cache miss的定義,要存取的資料若不在快取記憶體中，就會導致 cache misses。如果預先知道要存取的資料並載入快取記憶體中，就可以避免cache misses。

- [ ] c14006078: [共筆](https://hackmd.io/s/ryTASBCT)
- [ ] kaizsv: [共筆](https://hackmd.io/s/r1IWtb9R)

## mergesort-concurrent
- [ ] mingnus: [共筆](https://hackmd.io/s/SJeOsFOR)
* code review

- [ ] TempoJiJi: [共筆](https://hackmd.io/s/B1-Kytv0)
* 對程式碼做了很多調整，降低 lock contention 發生的機會，不過因為他還沒將 merge sort 內部實做切割，所以 scalability 很差，執行緒越多，排序則越慢。
* 嘗試引入 SuperMalloc 後，他發現整體執行時間縮減了 (從左/上圖到右/下圖)，由此可見，實做細節不能忽略 concurrent memory allocation 的影響。

- [ ] shelly4132: [共筆](https://hackmd.io/s/HkX7l7YA)
* 發現 cut_func() 跟 merge_sort() 都進行切割 linked list，而 cut_func 裡面判斷 cut_count 是否小於 max_cut 其實沒有必要，所以把 cut_count 等相關變數刪掉，也把 merge_sort()刪掉，留下 cut_func() 就好。
* 為了驗證程式正確性，她還特別設計 verification 用的程式

- [ ] LanKuDot: [共筆](https://hackmd.io/s/S1ezGhIA)
* code refactoring
* 建立自動化結果測試

- [ ] andy19950: [共筆](https://hackmd.io/s/rJ6m3IvC)