Try   HackMD

回顧 2016q1 Homework3

tags: sysprog2016

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

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 →
返回「進階電腦系統理論與實作」課程進度表

回顧與檢討

software-pipelining

  • 研讀 "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。

mergesort-concurrent

  • code review
  • 對程式碼做了很多調整，降低 lock contention 發生的機會，不過因為他還沒將 merge sort 內部實做切割，所以 scalability 很差，執行緒越多，排序則越慢。
  • 嘗試引入 SuperMalloc 後，他發現整體執行時間縮減了 (從左/上圖到右/下圖)，由此可見，實做細節不能忽略 concurrent memory allocation 的影響。
  • 發現 cut_func() 跟 merge_sort() 都進行切割 linked list，而 cut_func 裡面判斷 cut_count 是否小於 max_cut 其實沒有必要，所以把 cut_count 等相關變數刪掉，也把 merge_sort()刪掉，留下 cut_func() 就好。
  • 為了驗證程式正確性，她還特別設計 verification 用的程式
  • code refactoring
  • 建立自動化結果測試
Last changed by 
 
Jim Huang
0
1346
Published on HackMD