1.一種基于片上多核處理器共享cache的動態公平劃分方法，其特征在 于，包括以下步驟：初始化、回溯和重劃分；將應用程序的運行時間均勻分 塊，每一塊時間稱為一個時間片t；初始化只在應用程序運行前執行一次，回 溯和重劃分步驟則在每個時間片t結束后執行；設S²_t為時間片t的公平性指 標，回溯階段是若公平性指標S²_t大于前一時間片的公平性指標S²_t-1，且S²_t與 S²_t-1的差大于回溯閾值，則撤銷前一次重劃分；重劃分階段是若未發生回溯且 S²_t大于重劃分閾值，則對所有線程重新劃分高速緩存Cache；

在該方法中，有四個基本的參數：回溯閾值S_rollback、重劃分閾值S_repartition、 劃分粒度gran和時間片t；S_rollback取值在1％～50％之間，S_repartition取值在1％～10％ 之間，劃分粒度gran即是劃分的最小單位取值在64B～64KB之間，t取值在 100000～5000000個時鐘周期之間；具體過程如下：

(1)初始化：

1.1)所有線程等分高速緩存Cache，P_i＝Cache總容量/n，P_i表示線 程i所分配的Cache大小，n表示線程總數，P^t_i表示時間片t時線程i所分 配的Cache大小；

1.2)設M₁為每指令的一級Cache缺失次數，E₁為訪問一級Cache命 中開銷，E₂為一級Cache缺失時訪問二級Cache的命中開銷，E₃為二級 Cache缺失時訪問主存的命中開銷，CPI_base為平均每指令執行周期數；M₁、 E₁、E₂、E₃和CPI_base的值由所使用的計算機體系結構決定；

1.3)令α＝CPI_base+E₁+M₁×E₂，β＝E₃，計算出α和β；

(2)回溯階段：在時間片t結束時，

2.1)計算時間片t時劃分方案的公平性指標S²_t：

2.1.1)讀指令計數器獲得時間片t內各線程執行的指令數I_num，讀 獨占缺失計數器獲得各線程獨占cache狀態下的缺失數Miss_di；

2.1.2)根據公式(I)計算出T_dedi，T_shri等于時間片t的長度，公 式(I)如下：

T_dedi＝α×I_num+β×Miss_di????(I)

2.1.3)根據公式(II)計算X_i和X_i的均值，公式(II)如下：

Xi=TshriTdedi,X‾=1nΣi=1nXi---(II)]]>

2.1.4)根據公式(III)計算S²_t，公式(III)如下：

S2=1n-1Σi=1n(Xi-X‾)2---(III)]]>

2.2)若S²_t＜S²_t-1，或|S²_t-S²_t-1|/S²_t＜S_rollback則轉到步驟(3)；

2.3)若S²_t≥S²_t-1，且|S²_t-S²_t-1|/S²_t≥S_rollback，令P^t+1_i＝P^t-1_i， 轉到步驟(4)；

(3)重劃分階段：回溯階段結束后，

3.1)若S²_t＜S_repartition，則轉到步驟(4)；

3.2)若S²_t≥S_repartition，則設Y_i＝X_i-∑X_i/n，劃分集PS＝{P^t₁，P^t₂，…， P^t_n}和候選集CS＝{1，2，…，n}；

3.3)如|CS|≥2，選出Y_i中的最大值m?axY_k和最小值minY_j，k和j 分別是最大值和最小值的線程號；若maxY_k≤0或minY_j≥0則轉到步驟 3.6)；

3.4)如P^t_j＝gran，則CS′＝CS-{j}，轉到步驟3.3)；

3.5)P^t+1_k＝P^t_k+gran，P^t+1_j＝P^t_j-gran，CS′＝CS-{k，j}，轉到 步驟3.3)；

3.6)若CS′中還有剩余的線程號i，則令P^t+1_i＝P^t_i；

(4)轉到步驟(2)，直至n個線程運行結束。