片上多核處理器共享資源分配與調(diào)度策略研究綜述（二）

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

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

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

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

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

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

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

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

的值來最大化系統(tǒng)公平性程度。文獻(xiàn)中提出的緩存分區(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 中進(jìn)行的緩存重分配，如果時間段t 的分區(qū)策略沒有取得預(yù)期效果，即：

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

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

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,則進(jìn)行重分區(qū)：

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

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

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

之后Rafique 在文獻(xiàn)中還從操作系統(tǒng)層面實(shí)現(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 細(xì)粒度緩存分區(qū)

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

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

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