[發明專利]基于內存訪問堆棧距離的數據Cache性能探索方法

有效

• 申請號: 201410014367.9
• 申請日: 2014-01-13
• 公開（公告）號: CN103793339A
• 公開（公告）日: 2014-05-14
• 發明（設計）人: 姚英彪;韓琪
• 申請（專利權）人: 杭州電子科技大學
• 主分類號: G06F13/16
• 分類號: G06F13/16
• 代理公司: 杭州求是專利事務所有限公司 33200
• 代理人: 杜軍

技術領域

本發明涉及嵌入式系統的存儲系統設計領域，特別是涉及一種基于內存訪問堆棧距離的數據Cache性能探索方法。

背景技術

片上內存結構是嵌入式系統關鍵部件之一，它對系統的整體性能、制造成本、系統功耗等多個參數具有很大的影響。為得到給定應用的最優片上內存結構，嵌入式系統設計者必須對片上內存結構設計空間的每一種方案進行性能評價，以得到滿足系統性能、功耗和成本等約束的最佳方案。然而，由于設計空間巨大，如片上內存類型是SPM（Scratch?Pad?Memory）還是高速緩存Cache、容量怎么劃分、Cache或SPM的具體設計參數等，如果僅僅靠仿真的方法去評價每一種片上內存配置，無疑是一件耗時耗力的事情，特別是在產品有上市時間限制的條件下，這種全仿真的方法更不可實現。

為在巨大的片上內存設計空間找出滿足性能、功耗和成本要求的配置，設計者需要用快速準確的方法去評價不同片上內存配置的相對性能，這點對成本敏感的嵌入式系統設計尤為重要。例如，如果分析表明一個小的片上內存結構就能獲得滿意的性能，那么設計時就可以采用小的片上內存結構，從而減少芯片面積和降低芯片的生產成本，使產品更有競爭力。在片上內存結構性能估計中，由于SPM是軟件管理的片上內存，其上的數據對設計者是已知的，因此性能很好估計；難點在于硬件管理的Cache的性能估計，其上的數據對設計者未知，因此它的性能估計是片上內存結構性能估計的難點問題。由于Cache的性能公式為：

T＝hit×T_hit+(1-hit)×T_miss

上述公式中，T_hit和T_miss分別為Cache命中時和失配時的訪問延遲，它們很容易通過Cache的硬件結構和工藝庫得到；hit為Cache針對不同應用的命中率，它是Cache性能估計的難點。可見，探索Cache在不同配置下的性能，關鍵是要估計Cache在不同配置下的命中率。針對這個問題，本發明專利提出一種基于內存訪問堆棧距離的數據Cache命中率估計方法，以此實現對Cache性能的探索。

內存訪問堆棧距離是指同一個內存地址兩次連續訪問之間的獨一無二的其它內存地址的訪問個數；如果該地址為第一次訪問，堆棧距離記為∞，如圖1所示。在圖1中，前2次內存訪問都是新地址，因此內存訪問堆棧距離為∞；第3次訪問在地址堆棧的第0個位置命中，因此內存訪問的堆棧距離為0；依次類推。

內存訪問堆棧距離之所以能用來進行Cache命中率估計，在于它具有這樣的性質：對于一個采用最近最少使用（LRU）替換策略的全相聯Cache，其大小為s組；如果內存訪問堆棧距離計算時的地址大小與Cache的塊大小一致，則當內存訪問的堆棧距離d≤s時，它在Cache里面命中；d＞s時，它在Cache里面失配。由于內存訪問堆棧也是按最近最少使用排序的，即將最近訪問的排在最前面，離現在訪問最遠的排在最后面，因此本發明專利提出的基于內存訪問堆棧距離的Cache性能探索方法僅適合于采用LRU替換算法的Cache。

發明內容

本發明的目的在于針對現有技術不足，實現Cache性能快速且準確估計，提供一種基于內存訪問堆棧距離的數據Cache性能探索方法。

本發明解決其技術問題所采用的技術方案具體包括如下步驟：

步驟1.計算內存訪問堆棧距離及其概率分布；

步驟2.確定探索的Cache容量及其三個參數組數S（Set?size）、關聯度A（Associativity）和塊大小B（Block?size）的范圍；

步驟3.計算估計參數e_s(S)、e_a(A)和e_b(B)，利用e_s(S)、e_a(A)和e_b(B)估計Cache三個參數組數S（Set?size）、A（Associativity）和B（Block?size）對命中率的影響，并計算命中率est₁；

步驟4.利用內存訪問堆棧距離的概率分布計算命中率est₂；

步驟5.比較命中率est₁和est₂，最終估計出Cache命中率。

步驟1所述的計算內存訪問堆棧距離及其概率分布的具體如下：

1-1.讀入一條內存訪問蹤跡，得到當前內存訪問地址；