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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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