# B06: 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)" (務必事先閱讀論文，否則貿然看程式碼，只是陷入一片茫然!)，紀錄你的認知和提問
* 在 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 來改寫程式碼
* 在 [Homework3 作業區](https://hackmd.io/s/HkYlSCJil) 詳細描述實驗設計、閱讀論文的心得和疑惑，以及你的觀察
* 截止日期：
* Mar 18, 2017 (含) 之前
越早在 GitHub 上有動態、越早接受 code review，評分越高

## 挑戰題
* 參考 [Matrix Multiplication using SIMD](https://hackmd.io/s/Hk-llHEyx)，自行實作高效能的矩陣運算套件

## 見賢思齊: 共筆選讀
- [ ] 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)

## 參考資料
* [許士杰共筆](https://embedded2015.hackpad.com/-Homework-7-8-XZe3c94XjUh)
* [周曠宇共筆](https://embedded2015.hackpad.com/Week8--VGN4PI1cUxh)