[發明專利]面向多核處理器的共享Cache沖突預測方法

有效

• 申請號: 201110382674.9
• 申請日: 2011-11-25
• 公開（公告）號: CN103136113A
• 公開（公告）日: 2013-06-05
• 發明（設計）人: 郭銳鋒;董磊;秦承剛;張鴻楠;劉嫻;岳東峰
• 申請（專利權）人: 中國科學院沈陽計算技術研究所有限公司
• 主分類號: G06F12/08
• 分類號: G06F12/08
• 代理公司: 沈陽科苑專利商標代理有限公司 21002
• 代理人: 許宗富

1.一種面向多核處理器的共享Cache沖突預測方法，其特征在于，包括以下步驟：

獲取任務獨立執行時的共享Cache靜態復用距離；

根據各任務的共享Cache靜態復用距離，確定多核處理器環境下并發任務的共享Cache狀態；

建立模型參數；

計算模型得到觀察值向量；

根據觀察值向量預測任務的Cache空間占用率，失效率和并發任務間發生Cache訪問沖突的概率。

2.根據權利要求1所述的面向多核處理器的共享Cache沖突預測方法，其特征在于，所述共享Cache狀態為在LRU替換策略下的共享Cache狀態，記為S(L(1，1)，L(1，2)......L(i，j))，其中，元組L(i，j)表示任務i占共享Cache中第j組位置，0≤i≤任務總數，0≤j≤共享Cache相聯度。

3.根據權利要求1所述的面向多核處理器的共享Cache沖突預測方法，其特征在于，所述模型參數包括：

內存中所有任務的并發度：在內存中共駐有M個任務，而這些任務的并發度為M；

N+1個計數器：在LRU替換策略下，命中的Cache訪問計數，記為C(1)，C(2)......C(N)；失效的Cache訪問計數C(N+1)，記為C(＞N)，即公式(1)

其中，i為內存中并發的任務的標號；

狀態間的轉移矩陣為A：由狀態轉移概率構成M^N×M^N的狀態轉移矩陣，第i行第j列元素為a_ij，意義是從狀態S_i到S_j的狀態轉移概率。

觀察概率B：Cache訪問觀察概率B{b_j(k)}，b_j(k)表示在狀態j時，模型輸?出符號o_k的概率為b_j(τ)＝P(o_k|j)1≤k≤τ，1≤j≤M^N；

初始狀態概率分布π：系統初始時，共享Cache各狀態的概率。

4.根據權利要求3所述的面向多核處理器的共享Cache沖突預測方法，其特征在于，所述狀態間的轉移矩陣為A由M^N×M^N個狀態轉移概率

構成，其中Af_i表示任務i平均每周期發生Cache訪問的概率，

其中Execution?cycle?count是任務的執行周期計數。

5.根據權利要求3所述的面向多核處理器的共享Cache沖突預測方法，其特征在于，所述觀察概率B由正則Markov鏈性質及觀察概率概念得到，

求解b_i得到觀察概率，其中b為B的第i行行向量。

6.根據權利要求1所述的面向多核處理器的共享Cache沖突預測方法，其特征在于，所述計算模型得到觀察值向量的步驟具體為：

設t＝1，按照初始狀態概率分布π，選擇一個初始狀態S₁＝S_i；

按照狀態i輸出符號的概率分布b_i(k)，選擇t時刻輸出值o_k；

按照狀態轉移概率分布a_ij選擇一個后繼狀態S_t+1＝S_j；

若t＜T，令t＝t+1，并且轉移到本算法步驟的第2步繼續執行，否則結?束；

每發生一次Cache訪問就能確定一個Cache觀察序列值，最終模型輸出觀察序列向量O(o₁，o₂…o_τ)。

7.根據權利要求1所述的面向多核處理器的共享Cache沖突預測方法，其特征在于，所述根據觀察值向量預測任務的Cache空間占用率通過

計算得出，其中，Space_i(t)＝{L_x，y|L_x，y∈o_t∧x＝i}，表示任務i所在觀察序列t時刻所占共享Cache的大小。