[發明專利]一種基于統計推演的期望堆棧距離快速提取方法

有效

• 申請號: 201511018082.3
• 申請日: 2015-12-29
• 公開（公告）號: CN105677584B
• 公開（公告）日: 2019-01-04
• 發明（設計）人: 季柯丞;王芹;凌明;時龍興
• 申請（專利權）人: 東南大學—無錫集成電路技術研究所
• 主分類號: G06F12/0862
• 分類號: G06F12/0862;G06F12/0893
• 代理公司: 南京瑞弘專利商標事務所(普通合伙) 32249
• 代理人: 彭雄

1.一種基于統計推演的期望堆棧距離快速提取方法，其特征在于：

步驟1，通過全功能仿真模型Gem5獲取程序執行過程中的訪存Trace流；并在記錄訪存Trace流的同時，對每個訪存請求進行執行順序標號；

步驟2，利用紅黑樹數據結構記錄步驟1中每次訪存的地址及順序標號，獲得重用距離分布；其中，紅黑樹數據結構事件復雜度為O(log n)，n為存儲的數據結構數目；當訪存重用產生時，將當前訪存請求的順序標號同紅黑樹中記錄的前次訪存請求的順序標號相減，獲取訪存重用距離；

重用距離指針對同一Cacheline的兩次連續訪存請求之間的訪存請求個數；依照指令執行順序對每個訪存請求進行標號；在紅黑樹結構中，訪存地址作為索引鍵值，被索引內容為前次針對當前地址的訪存序號；每當接收一次訪存請求時，將訪存地址進行Cacheline地址對齊，并將對齊后的地址送入紅黑樹進行索引；若返回為空，則表明該訪存請求前未有針對該地址的訪問，本次請求將會產生一次冷缺失；針對冷缺失，紅黑樹中會增加新的表項用于存儲該地址及訪存序號；若返回為訪存序號，則將當前訪存序號同紅黑樹中索引序號相減，即為當前請求的重用距離；完成重用距離計算后，將當前訪存序號插入紅黑樹中，覆蓋掉相同地址下前次訪問的訪存序號；

步驟3，通過采樣方法，找出重用距離與基于Cache組關聯的重用距離之間的轉換關系；將步驟2得到的重用距離分布通過該轉換關系得到基于Cache組關聯的重用距離分布；重用距離與基于Cache組關聯的重用距離之間的轉換關系為重用距離映射到基于Cache組關聯結構的重用距離的映射關系；

步驟4，設計推導訪存重用距離分布與期望堆棧距離分布之間的轉換關系；將步驟3得到的基于Cache組關聯的重用距離分布通過該轉換關系得到基于Cache組關聯的期望堆棧距離分布，進而評估LRU-Cache訪存行為；訪存重用距離分布與期望堆棧距離分布之間的轉換關系描述為重用距離為R的期望堆棧距離近似等于重用距離大于R的訪存請求次數求和。

2.根據權利要求1所述的基于統計推演的期望堆棧距離快速提取方法，其特征在于：所述步驟3中基于Cache組關聯的重用距離的提取方法：假設有一任意訪存重用區間Ri<a,m>，a為訪存地址，m為重復訪問該地址的次數；用概率定量描述重用區間內每個訪存請求與地址a在同一組中的可能性，f為地址映射函數，其結果依賴于A，S及f；A代表Cache路數，S代表Cache組數；

根據采樣的訪存序列，把某一Cache結構下的地址映射函數f應用到每個訪存地址中；在進行地址映射過程中，記錄映射到每個Cache set的地址數；如果把不同的set按照1到S進行標號，m(i)表示映射到標號為i的set中的地址數；M代表所有的地址總數，那么看成：

獲得后，根據推算出基于Cache組關聯的訪存重用距離；假設訪存重用區間Ri<a,m>的原始大小為k，也就是重用距離為k；依照概率推論可得其中有i個訪存請求被映射到與地址a同一個set的概率為所以基于Cache組關聯的訪存重用距離為：

其中，rdds(i)代表在同一個set中，重用距離為i的訪存請求個數，rdd(k)表示不考慮多路組關聯影響的重用距離為k的訪存請求個數。

3.根據權利要求1所述的基于統計推演的期望堆棧距離快速提取方法，其特征在于：所述步驟4中期望堆棧距離分布的提取方法如下：定義:x_i與x_j分別代表針對同一個訪存地址的兩次連續訪存請求；重用距離：x_j的重用距離等于x_i與x_j間訪存請求個數；前向重用距離：x_i的前向重用距離為x_i和x_j之間的訪存請求個數；堆棧距離：x_j的堆棧距離為x_i和x_j之間的訪存Cacheline地址個數；R(x_t)和分別代表訪存請求x_t的重用距離和前向重用距離；Q(x_t)表示介于x_t與前次相同地址訪存請求之間的訪存序列子集；最后一次訪存請求的判定方法:若該訪存請求的前向重用距離超過目標重用區間的范圍，即表示該請求是在目標重用區間內最后一次針對其地址的訪問的訪存請求；將訪存請求x_t的訪存堆棧距離表示為訪存請求x_i的數量，x_i滿足條件x_i∈Q(x_t)，當觀測到則表明x_i是最后一個針對地址的訪存請求；x_t的堆棧距離S(x_t)可按如下表示：

訪存重用距離為r的訪存請求，其期望堆棧距離為所有重用距離為r的訪存請求堆棧距離的平均值；

T(r)代表所有訪存重用距離為r的訪存請求集合，n_r表示訪存請求個數；則期望堆棧距離ES(r)為:

f_i表示前向訪存重用距離大于i的訪存請求個數，由于前向重用距離在分布上近似等于重用距離，公式可改寫成如下表達：

表示重用大于i的訪存請求個數。