臺灣博碩士論文加值系統

隨著製程的進步，處理器的速度遠快於存取記憶體的速度，使得記憶體的存
取嚴重影響到系統的效能。在Chip Multiprocessor (CMP)的私有快取架構下，若
能有效地利用整體的快取空間將可以大幅減少記憶體的存取次數。而空間區域性
與時間區域性都會影響到快取空間的使用率，故本文同時考量這兩種區域性對快
取使用率的影響。在空間區域性的部分，快取空間的使用會有不均衡的情況，此
不均衡的情況不只存在於快取與快取之間，甚至還存在於集合與集合之間。因此，
我們提出一個空間共享的機制，將沒有使用到的空間借給空間不足的集合，以改
善快取的命中率。而時間區域性的對快取使用率的影響，則表現在快取替換策略
上。對此，我們提出一個機制來動態決定每一個集合適合的替換策略，以期能讓
快取的使用更有效率。除此之外，我們亦設計了一個在空間共享的機制下，能有
效率地維護快取一致性的方法，此方法能減少廣播與標籤比較的次數，進一步減
少耗電並且改善效能。

誌謝 ................................................................................................................................. i
摘要 ................................................................................................................................ ii
Abstract ......................................................................................................................... iii
目錄 ............................................................................................................................... iv
圖目錄 ........................................................................................................................... vi
表目錄 ......................................................................................................................... viii
第一章 導論 ............................................................................................................ 1
1.1. 研究背景與動機 ............................................................................................ 1
1.2. 研究目標與方法 ............................................................................................ 4
1.3. 本文架構 ........................................................................................................ 5
第二章 相關研究 .................................................................................................... 6
2.1. 空間區域性 .................................................................................................... 6
2.2. 時間區域性 .................................................................................................... 8
2.3. 空間區域性併以時間區域性 ...................................................................... 10
2.4. 相關研究結論 .............................................................................................. 11
第三章 問題定義 .................................................................................................. 12
第四章 Set-Level Sharing and Cache Coherence Maintenance ........................... 14
4.1. 改善快取使用效率以提升命中率 .............................................................. 14
4.1.1. 使用影集合與飽和計數器來評估空間需求 .......................................... 15
4.1.2. 時間區域性之考量 .................................................................................. 16
4.1.3. 空間區域性 vs. 時間區域性 ................................................................. 17
4.1.4. 配對(coupling) ......................................................................................... 19
4.1.5. 解除配對(decoupling) ............................................................................. 22
4.2. 維護資料一致性 .......................................................................................... 23
4.2.1. Coherence Maintenance Table (CMT) .................................................... 24
4.2.2. cooperative data 之一致性維護 .............................................................. 31
第五章 模擬實驗與結果 ...................................................................................... 36
5.1. 模擬環境 ...................................................................................................... 36
5.2. 模擬結果 ...................................................................................................... 38
5.2.1. 空間共享 .................................................................................................. 38
5.2.2. 維護資料一致性之效能改善 .................................................................. 42
第六章 結論 .......................................................................................................... 46
參考文獻 ...................................................................................................................... 47

[1]W. Wulf and S. McKee. Hitting the wall: Implications of the obvious. ACM SIGArch Computer Architecture News, Mar. 1995, pp.20–24.
[2]D. Molka, D. Hackenberg, R. Schöne, and M.S. Müller, "Memory Performance and Cache Coherency Effects on an Intel Nehalem Multiprocessor System", in Proc. PaCT, 2009, pp.261-270.
[3]Next Generation Intel® Microarchitecture (Nehalem) Architectural Insights
[4]M. Zhang and K. Asanovic, "Victim Replication: Maximizing Capacity while Hiding Wire Delay in Tiled Chip Multiprocessors", in Proc. ISCA, 2005, pp.336-345.
[5]J. Chang and G.S. Sohi, "Cooperative Caching for Chip Multiprocessors", in Proc. ISCA, 2006, pp.264-276.
[6]M.K. Qureshi, "Adaptive Spill-Receive for robust high-performance caching in CMPs", in Proc. HPCA, 2009, pp.45-54.
[7]D. Rolán, B.B. Fraguela, and R. Doallo, "Adaptive line placement with the set balancing cache", in Proc. MICRO, 2009, pp.529-540.
[8]D. Zhan, H. Jiang, and S.C. Seth, "Exploiting set-level non-uniformity of capacity demand to enhance CMP cooperative caching", in Proc. IPDPS, 2010, pp.1-10.
[9]M.K. Qureshi, A. Jaleel, Y.N. Patt, S.C.S. Jr., and J.S. Emer, "Adaptive insertion policies for high performance caching", in Proc. ISCA, 2007, pp.381-391.
[10]A. Samih, A. Krishna, and Y. Solihin, “Understanding the limits of capacity sharing in CMP Private Caches”, in CMP-MSI, 2009.
[11]A. Samih, Y. Solihin, and A. Krishna, "Evaluating placement policies for managing capacity sharing in CMP architectures with private caches", presented at TACO, 2011, pp.15-15.
[12]D. Zhan, H. Jiang, and S.C. Seth, "STEM: Spatiotemporal Management of Capacity for Intra-core Last Level Caches", in Proc. MICRO, 2010, pp.163-174.
[13]Christian Fensch, Nick Barrow-Williams, Robert Mullins, Simon Moore, "Designing a Physical Locality Aware Coherence Protocol for Chip-Multiprocessors", IEEE Transactions on Computers, 21 Feb. 2012.