486 views
# C05: software-pipelining ###### tags: `sysprog2017` :::info 主講人: [jserv](http://wiki.csie.ncku.edu.tw/User/jserv) / 課程討論區: [2017 年系統軟體課程](https://www.facebook.com/groups/system.software2017/) :mega: 返回「[進階電腦系統理論與實作](http://wiki.csie.ncku.edu.tw/sysprog/schedule)」課程進度表 ::: ## 預期目標 * 學習計算機結構並且透過實驗來驗證所學 * 理解 prefetch 對 cache 的影響,從而設計實驗來釐清相關議題 * 論文閱讀和思考 * 持續練習技術報告寫作 ## 作業要求 * 閱讀論文 "[When Prefetching Works, When It Doesn’t, and Why](http://www.cc.gatech.edu/~hyesoon/lee_taco12.pdf)" (務必事先閱讀論文,否則貿然看程式碼,只是陷入一片茫然!),紀錄你的認知和提問 * [論文重點提示和解說](https://hackmd.io/s/HJtfT3icx) * 詳細閱讀 [software pipelining](https://hackmd.io/s/S1fZ1m6pe) 共筆以及裡頭對應的==錄影== * 在 Linux/x86_64 (注意,要用 64-bit 系統,不能透過虛擬機器執行) 上編譯並執行 [prefetcher](https://github.com/sysprog21/prefetcher) * 說明 `naive_transpose`, `sse_transpose`, `sse_prefetch_transpose` 之間的效能差異,以及 prefetcher 對 cache 的影響 * 在 github 上 fork [prefetcher](https://github.com/sysprog21/prefetcher),參照下方「見賢思齊:共筆選讀」的實驗,嘗試用 AVX 進一步提昇效能。分析的方法可參見 [Matrix Multiplication using SIMD](https://hackmd.io/s/Hk-llHEyx) * 修改 `Makefile`,產生新的執行檔,分別對應於 `naive_transpose`, `sse_transpose`, `sse_prefetch_transpose` (學習 [phonebook](s/S1RVdgza) 的做法),學習 [你所不知道的 C 語言:物件導向程式設計篇](https://hackmd.io/s/HJLyQaQMl) 提到的封裝技巧,以物件導向的方式封裝轉置矩陣的不同實作,得以透過一致的介面 (interface) 存取個別方法並且評估效能 * 用 perf 分析 cache miss/hit * 學習 `perf stat` 的 raw counter 命令 * 參考 [Performance of SSE and AVX Instruction Sets](http://arxiv.org/pdf/1211.0820.pdf),用 SSE/AVX intrinsic 來改寫程式碼 * 將原本 8x8 矩陣推廣到更大的範圍,如 16x16, 32x32, 64x64 等等,並透過實際的實驗來驗證前述推論 * 在 [Homework2 作業區](https://hackmd.io/s/HkVvxOD2-) 詳細描述實驗設計、閱讀論文的心得和疑惑,以及你的觀察 ## 截止日期: * Oct 16, 2017 (含) 之前 * 越早在 GitHub 上有動態、越早接受 code review,評分越高 ## 見賢思齊: 共筆選讀 - [ ] 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) - [ ] [laochanlam](https://github.com/laochanlam): [共筆](https://hackmd.io/s/HJKw_Qejl) * AVX 優化 - [ ] [stanleytazi](https://github.com/stanleytazi): [共筆](https://hackmd.io/s/SyYw98Yox) * 研讀 Intel® 64 and IA-32 Architectures Optimization Reference Manual - [ ] [0xff07](https://github.com/0xff07): [共筆](https://hackmd.io/s/H1d_W-gsg) * Prefetch 想要處理的問題跟 Cache 一樣,都是要降低 CPU 與記憶體日益擴大的存取時間差異。 * 處理這個問題有兩個策略:多層用幾層 Cache,或是 Prefetching. 前者已經在很多處理器上出現,比如說有 L1 ~ L3 的 Cache。但 Prefetch 根據論文表示是相對稀少的。然而,Prefetching 在一些狀況下,能夠提升的效能會比多層 cache 來的好。 - [ ] [illusion030](https://github.com/illusion030): [共筆](https://hackmd.io/s/HkHDV-moe) * Raw counter * Intel® Memory Latency Checker v3.1a - [ ] [twzjwang](https://github.com/twzjwang): [共筆](https://hackmd.io/s/HJDVmyZje) * 8*8 矩陣轉置,使用 AVX * 8*8 矩陣轉置,使用 AVX + SW prefetch - [ ] [baimao8437](https://github.com/baimao8437) * [開發紀錄(software-pipelining)](https://hackmd.io/s/Skky1srig) / [github](https://github.com/baimao8437/prefetcher)