[發明專利]一種實現高速緩存替換的方法及裝置

在審

• 申請號: 201611206733.6
• 申請日: 2016-12-23
• 公開（公告）號: CN106844235A
• 公開（公告）日: 2017-06-13
• 發明（設計）人: 程旭;李凌達;陸俊林
• 申請（專利權）人: 北京北大眾志微系統科技有限責任公司
• 主分類號: G06F12/121
• 分類號: G06F12/121;G06F12/0891
• 代理公司: 北京安信方達知識產權代理有限公司11262
• 代理人: 韓輝峰,李丹

技術領域

本發明涉及計算機領域，尤指一種實現高速緩存替換的方法及裝置。

背景技術

由于處理器和主存之間的性能差距越來越大，在高速緩存失效時處理器往往要等待較長時間。因此如何通過改進高速緩存的替換方法來提高高速緩存的性能成為了當前的一個重要課題。當前大部分高速緩存替換方法的主要目標是減少高速緩存的總失效數量，它們假設所有失效的代價都是相同的。但是在現代處理器中由于訪存延遲可變，并且處理器使用多種訪存延遲隱藏技術(如非阻塞高速緩存和預取)，導致高速緩存的失效代價可變。因此只考慮減少總失效數量是不夠的，高速緩存替換方法應該以減少高速緩存的整體失效代價作為設計的目標。

按照高速緩存的替換方法的目標，高速緩存替換方法可以分為面向失效數的和面向失效代價的兩種：

面向失效數的高速緩存替換方法主要包括以下幾種：1、動態插入策略(DIP)通過把局部性差的塊的插入最近最少使用(Least Recently Used，LRU)位置來避免緩存的顛簸。2、再訪問插入預測(Re-Reference Interval Prediction，RRIP)通過區分在緩存中被訪問過的塊和沒被訪問過的塊，使得前者在高速緩存中停留的時間更長來改善性能。3、偽后進先出(Pseudo Last-In-First-Out)通過優先排出棧頂端的塊，使得棧低端的塊被保存的時間更長。4、基于簽名的命中預測(Signature-based Hit Predictor，SHiP)通過預測塊的重用距離來在RRIP的基礎上改善性能。5、死亡塊預測(Dead Block Prediction)技術通過預測一個塊的最后一次訪問來提高性能?；陬A測的方法，死亡塊預測技術可以分為基于蹤跡的、基于時間的和基于計數器的。6、合并連續訪問方法通過對連續的訪問進行預測來提高準確率。7、基于采樣的死亡塊預測(Sampling Dead Block Prediction，SDBP)通過采樣一部分訪問來訓練預測器，從而減少硬件開銷和提高預測準確率。8、旁路方法通過預測并旁路那些在被排出之前沒被使用的塊來提高性能。根據預測的方法可以分為基于程序計數器(Program Counter，PC)的和基于地址的。9、較少再用過濾器(Less Reused Filter，LRF)通過既使用基于PC的又使用基于地址的預測器來提高性能。10、使用自適應旁路的分段替換(Dueling Segment replacement with adaptive Bypassing)在失效時記錄進入塊和排出塊的對，通過比較它們被訪問的順序來決定旁路的使用概率。

面向失效代價的高速緩存替換方法主要包括：1、Jeong等人提出在訪存時延變化時區分長失效代價和短失效代價，并用于輔助LRU算法來指導替換塊選擇。2、關鍵高速緩存(Critical Cache)和局部性感知和代價敏感型高速緩存替換(Locality-Aware Cost-Sensitive cache replacement)通過使用失效期間處理器發射的指令數來表示失效代價。3、存儲并行性感知替換(MLP-aware replacement)用存儲并行性代價(MLP cost)來表示由于處理器訪存延遲隱藏能力造成的失效代價的差異，然后使用MLP cost來指導替換方法。

以上這些緩存替換的方法要么是針對失效數的，要么只關注失效代價，而只關注失效代價是不夠的。在如下例子中，假設塊A在被裝入高速緩存時失效代價為200周期，并且塊A只被訪問一次，因此沒有得到命中；而塊B在被裝入高速緩存時失效代價為50周期，然后塊B得到了9次命中，每次命中時可以防止處理器停頓50周期。對于上述例子，保留B可以總共防止處理器停頓500周期，而保留A只能防止處理器停頓200周期，因此高速緩存應該優先保留B而不是A。但是如果只考慮失效代價，那么高速緩存將優先保留A而不是B。只考慮訪問失效時的失效代價并不能對高速緩存的整個過程進行評價，影響高速緩存替換的高效合理進行。

發明內容

為了解決上述技術問題，本發明提供一種實現高速緩存替換的方法及裝置，能夠針對高速緩存的不同的訪問結果進行綜合考慮，降低高速緩存替換對高速緩存的整體失效代價。

為了達到上述發明目的，本發明公開了一種實現高速緩存替換的方法，包括：獲取對高速緩存的塊的訪問結果，當訪問結果為訪問失效時，移動訪問失效所在組的所述高速緩存的塊中收益值RBV最小的塊，并將訪問失效的塊放置在訪問失效所在組的RBV最小的塊移動前所在的位置；對訪問失效的塊計算失效代價，將計算出的失效代價賦值給訪問失效的塊裝入的位置對應的RBV；