Try   HackMD

C05: software-pipelining

tags: sysprog2017

主講人: jserv / 課程討論區: 2017 年系統軟體課程

Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More →
返回「進階電腦系統理論與實作」課程進度表

預期目標

  • 學習計算機結構並且透過實驗來驗證所學
  • 理解 prefetch 對 cache 的影響，從而設計實驗來釐清相關議題
  • 論文閱讀和思考
  • 持續練習技術報告寫作

作業要求

  • 閱讀論文 "When Prefetching Works, When It Doesn’t, and Why" (務必事先閱讀論文，否則貿然看程式碼，只是陷入一片茫然!)，紀錄你的認知和提問
  • 詳細閱讀 software pipelining 共筆以及裡頭對應的錄影
  • 在 Linux/x86_64 (注意，要用 64-bit 系統，不能透過虛擬機器執行) 上編譯並執行 prefetcher
    • 說明 naive_transpose, sse_transpose, sse_prefetch_transpose 之間的效能差異，以及 prefetcher 對 cache 的影響
  • 在 github 上 fork prefetcher，參照下方「見賢思齊：共筆選讀」的實驗，嘗試用 AVX 進一步提昇效能。分析的方法可參見 Matrix Multiplication using SIMD
  • 將原本 8x8 矩陣推廣到更大的範圍，如 16x16, 32x32, 64x64 等等，並透過實際的實驗來驗證前述推論
  • 在 Homework2 作業區 詳細描述實驗設計、閱讀論文的心得和疑惑，以及你的觀察

截止日期：

  • Oct 16, 2017 (含) 之前
  • 越早在 GitHub 上有動態、越早接受 code review，評分越高

見賢思齊: 共筆選讀

  • 研讀 "When Prefetching Works, When It Doesn’t, and Why" 論文，詳實紀錄不理解之處，接著開始進行一系列實驗，包含 SIMD-friendly 的寫法。
  • 為了理解 prefetch distance 該如何設定，就需要先知道 memory latency 的時間和 loop 中 instruction 執行的時間，透過 Intel® Memory Latency Checker (mlc) 得知 latency 後，重新做了 AVX 實驗。
  • 比照直覺的 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。
  • 研讀 Intel® 64 and IA-32 Architectures Optimization Reference Manual
  • Prefetch 想要處理的問題跟 Cache 一樣，都是要降低 CPU 與記憶體日益擴大的存取時間差異。
  • 處理這個問題有兩個策略：多層用幾層 Cache，或是 Prefetching. 前者已經在很多處理器上出現，比如說有 L1 ~ L3 的 Cache。但 Prefetch 根據論文表示是相對稀少的。然而，Prefetching 在一些狀況下，能夠提升的效能會比多層 cache 來的好。
  • Raw counter
  • Intel® Memory Latency Checker v3.1a
  • 8*8 矩陣轉置，使用 AVX
  • 8*8 矩陣轉置，使用 AVX + SW prefetch
Last changed by 
 
Jim Huang
0
1576
Published on HackMD