# 回顧 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)