該項研究首先對系統(tǒng)的公平性給出一個理想化的定義如下：

Tsolo_i 表示線程i 獨占全部共享資源時所需的執(zhí)行時間;Tshd_i 表示多個線程并行運行時執(zhí)行線程i所需的時間;當(dāng)所有線程在并行環(huán)境下的執(zhí)行時間按相等比例增長時，則認(rèn)為系統(tǒng)是絕對公平的。存在如下表達式：

Xi 表示線程i 在與其他線程協(xié)同運行時相對于它獨自運行時的減速比(slowdown); 0ij M 表示系統(tǒng)中任意兩個線程間減速比之差。0ij M 越小，表示兩個線程性能所受到的影響程度越相近。因此，一個追求公平性的緩存分區(qū)策略，應(yīng)該使得0ij M 之和最小化，則系統(tǒng)的公平性程度最高。

在實際并行系統(tǒng)中，Tshd_i 信息易于獲取，但是Tsolo_i 的相關(guān)信息很難取得。因此，需要尋找可以替代執(zhí)行時間T 同時又易于獲取的指標(biāo)。

Kim 等人在文獻中另外提出了5 項可用的指標(biāo)來衡量系統(tǒng)公平性。需要用到的信息包括各線程獨享緩存時產(chǎn)生的緩存失效數(shù)Missessolo 和緩存失效率MissRatesolo,以及多個線程并行運行時的緩存失效率Missesshd 和緩存失效率MissRateshd.對于任意一對線程i 和j,5 項指標(biāo)分別如下：

這里提出的幾個指標(biāo)都具有較為直觀的意義：

M1 用于平衡各線程緩存失效數(shù)增加的比例，M2 則是平衡各線程的緩存失效數(shù);類似的，M3 用于平衡各線程緩存失效率增加的比例，M4 平衡各線程的緩存失效率;而M5 則用于平衡各線程由于協(xié)同運行增加的緩存失效率。

在確定了系統(tǒng)公平性的衡量指標(biāo)后，需要制定相應(yīng)的緩存分區(qū)算法， 通過最小化表達式表達式1

的值來最大化系統(tǒng)公平性程度。文獻中提出的緩存分區(qū)算法由3 部分操作組成：初始化( initialization )， 回滾( rollback ) 和重分區(qū)(reparationing)。

初始化操作，將共享緩存平均分配給各個線程，

回滾操作，每一個時間段t 結(jié)束時：

1)將可能需要重分配的線程初始化為待調(diào)整線程集CS={1,2,…，n}.

2)對于每個線程i 檢測其是否在剛剛結(jié)束的時間段t 中通過重分區(qū)操作獲取了更多的緩存分區(qū)Aij(Aij 表示線程i 通過重分區(qū)操作從線程j 得到的緩存空間)，用集合AS 來記錄所有時間段t 中進行的緩存重分配，如果時間段t 的分區(qū)策略沒有取得預(yù)期效果，即：

則進行回滾操作，返回重分區(qū)之前的狀態(tài)并且將線程i,j 從待調(diào)整線程集CS 中剔除：

重分區(qū)操作，在每個時間段t 結(jié)束并且回滾操作完成之后進行：

1)初始化重分配集AS={};

2)對于每個線程i∈CS,按照選定的衡量指標(biāo)計算其公平性ti X ;

3)根據(jù)ti X 值排序，分別找出imax∈CS 以及imin∈CS;

4)若max_i min_i repartition X ? X ?T,則進行重分區(qū)：

這個緩存分區(qū)算法本質(zhì)上是用性能受影響最小線程的部分緩存空間來補償性能受影響最大的線程，從而提高系統(tǒng)公平性;回滾操作可以避免將緩存分配給收益很小的線程，從而提高了緩存利用率。

實驗結(jié)果還表明，采用不同的公平性衡量指標(biāo)制定的分區(qū)策略所取得的效果是不一樣的，其中采用M1取得的效果最佳，其次為M3,效果最差的則是M2.

上述方案是通過底層硬件來實現(xiàn)系統(tǒng)公平性。

之后Rafique 在文獻中還從操作系統(tǒng)層面實現(xiàn)了上述緩存分區(qū)策略，并以M4 為衡量標(biāo)準(zhǔn)，取得類似的優(yōu)化效果。

另外，對于前面提到的Tsolo_i 信息難以獲取的問題，我們可以通過增加一組計數(shù)器，來記錄每個線程由于其共享緩存中的數(shù)據(jù)被其他線程替換掉而產(chǎn)生的額外延遲Tdelay_i,用Tshd_i 減去Tdelay_i 則可以求出Tsolo_i,從而能夠更準(zhǔn)確地衡量公平性。

1.3.4 細粒度緩存分區(qū)

前面介紹的緩存分區(qū)分區(qū)策略，普遍存在的一個問題是緩存分區(qū)粒度較大。緩存的路數(shù)與其關(guān)聯(lián)度(associativity)相關(guān)。通過增加緩存路數(shù)能夠有效提高緩存關(guān)聯(lián)度，從而降低沖突帶來的緩存失效，但同時也會增加命中延遲和功耗。因此，緩存設(shè)計需要對各類代價進行折衷考慮，能夠維護的緩存路數(shù)總是一定的，不能隨意增加。在線程較少而緩存路數(shù)較多時，按路分區(qū)可以近似取得理想的分區(qū)效果;隨著線程數(shù)的增多，每個線程的平均可用緩存路數(shù)大大減少，按路分區(qū)的方式則不再可取。

緩存分區(qū)粒度過大還不可避免地會帶來緩存空間的浪費。例如一個線程分配到四路緩存，但是其中可能有一部分緩存空間的復(fù)用率很低或者根本就沒用到，則該線程分到的緩存空間存在冗余，得不到充分利用;與此同時，另一些線程的緩存需求可能無法得到滿足，卻無法使用其他線程的冗余緩存空間。

Xie 等人在文獻[10]中提出一種新的緩存管理策略稱為提升/ 插入偽分區(qū)策略(promotion/insertion pseudo-partitioning ,PIPP)。PIPP 結(jié)合UCP 的緩存分區(qū)策略思想，區(qū)別在于對緩存并不進行明確的嚴(yán)格分區(qū)，而是通過管理緩存的替換優(yōu)先級和插入策略來達到與緩存分區(qū)類似的效果。插入策略根據(jù)確定好的替換優(yōu)先級選擇應(yīng)該被逐出的緩存行;提升策略根據(jù)緩存命中情況更改緩存的替換優(yōu)先級。給緩存行設(shè)定不同替換優(yōu)先級實現(xiàn)類似緩存分區(qū)的效果。PIPP 沒有實際對緩存進行分區(qū)，因而，制定好分區(qū)策略后，線程在需要的時候仍然可以借用其他線程的冗余緩存空間。PIPP 允許從其他線程借用緩存空間在避免緩存空間浪費，提高緩存利用率的同時，卻難以防止某些侵略性較強的線程可能過多占用其他線程緩存空間，導(dǎo)致這些線程的性能受到嚴(yán)重影響的隱患。另外，PIPP 是針對UCP 策略的緩存分區(qū)粒度過大而提出的，對于其他的調(diào)度策略可能并不適用，可擴展性較差。