[發明專利]改善緩存預取數據局部性的方法和系統及緩存訪問方法

有效

• 申請號: 201310298246.7
• 申請日: 2013-07-16
• 公開（公告）號: CN103383666A
• 公開（公告）日: 2013-11-06
• 發明（設計）人: 嚴得辰;劉立坤
• 申請（專利權）人: 中國科學院計算技術研究所
• 主分類號: G06F12/08
• 分類號: G06F12/08
• 代理公司: 北京泛華偉業知識產權代理有限公司 11280
• 代理人: 王勇

技術領域

本發明涉及緩存技術，尤其涉及改善緩存命中率的預取數據局部性組織方法。

背景技術

緩存是多級存儲系統中非常重要的組成部分，緩存預取是一項重要的提高緩存效率的技術。訪問數據記錄p_ij時首先查找其訪問位置(索引查找或元數據查找等)，當未能在緩存中命中時，緩存預取通過一次存儲訪問將p_ij所在低級存儲層次中的預取數據記錄集合P_i：{p_i1，...，p_in}預取到緩存中，并將p_i1p_in的訪問位置修改為緩存中對應的位置，期望其后出現較多對p_i1～p_in的訪問。其中，稱P_i為p_i1，...，p_in的預取入口，p_ij為此次預取的預取首記錄。所訪問的數據記錄可以是定長數據記錄，也可以是變長數據記錄。緩存預取數據內的空間局部性決定了預取機制是否有效：具有較好空間局部性的緩存預取數據能夠使一次預取帶來較多的緩存命中，減少低層次存儲的訪問，而空間局部性較差的緩存預取數據使預取機制得不到收益。為了使預取機制發揮更大的作用，需要改善預取數據的空間局部性。

發明內容

因此，本發明的目的在于克服上述現有技術的缺陷，提供一種改善緩存預取數據局部性的方法。

本發明的目的是通過以下技術方案實現的：

一方面，本發明提供了一種改善緩存預取數據局部性的方法，所述方法包括：

統計緩存中每個預取數據記錄集合的預取命中次數，所述預取命中次數為該集合中被訪問的數據記錄的總數；

對于其預取命中次數小于設定的命中閾值的預取數據記錄集合，在將該集合換出緩存時，將該集合中被訪問的數據記錄寫入到新的存儲區域，與該存儲區域中的其他數據形成新的預取數據記錄集合。

上述方法中，還可包括：

對于緩存中每個預取數據記錄集合：

將該集合中首次被訪問的數據記錄標記為特殊記錄；

計算該集合中當前被訪問的數據記錄與上次被訪問的數據記錄之間的訪問間隔，如果該訪問間隔大于設定的間隔閾值，則將當前被訪問的數據記錄標記為特殊記錄；

對于其預取命中次數小于命中閾值的預取數據記錄集合，在將該集合換出緩存時，將被標記為特殊記錄的數據記錄的預取入口修改為所述新的預取數據記錄集合。

上述方法中，所述訪問間隔可為時間間隔、訪問次數間隔、自定義的邏輯間隔或者上述間隔的組合。

上述方法中，還可包括對于其預取命中次數小于命中閾值的預取數據記錄集合，在將該集合換出緩存時，將該集合中被訪問的數據記錄預取入口都修改為所述新的預取數據記錄集合。

又一方面，本發明還提供了一種改善緩存預取數據局部性的系統，所述系統包括：

用于統計緩存中每個預取數據記錄集合的預取命中次數的裝置，所述預取命中次數為該集合中被訪問的數據記錄的總數；

用于對于其預取命中次數小于設定的命中閾值的預取數據記錄集合，在將該集合換出緩存時，將該集合中被訪問的數據記錄寫入到新的存儲區域，與該存儲區域中的其他數據形成新的預取數據記錄集合的裝置。

上述系統中，還可包括標記裝置和修改裝置，所述標記裝置可用于對于緩存中每個預取數據記錄集合：

將該集合中首次被訪問的數據記錄標記為特殊記錄；

計算該集合中當前被訪問的數據記錄與上次被訪問的數據記錄之間的訪問間隔，如果該訪問間隔大于設定的間隔閾值，則將當前被訪問的數據記錄標記為特殊記錄；

所述修改裝置可用于對于其預取命中次數小于命中閾值的預取數據記錄集合，在將該集合換出緩存時，將被標記為特殊記錄的數據記錄的預取入口修改為所述新的預取數據記錄集合。

在又一方面，本發明還提供了一種緩存訪問方法，該方法包括：

對于待訪問的數據記錄，如果緩存命中，則將緩存中包含該待訪問的數據記錄的預取數據記錄集合的預取命中次數增加1；

如果緩存未命中且有空的緩存項，則將包含該待訪問的數據記錄的預取數據記錄集合預取到該緩存項中，并將該預取數據記錄集合的預取命中次數增加1；

如果緩存未命中且沒有空的緩存項，則執行：