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

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

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

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

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

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

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

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

在確定了系統公平性的衡量指標后，需要制定相應的緩存分區算法， 通過(guò)最小化表達式表達式1

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

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

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

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

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

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

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

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

2)對于每個(gè)線(xiàn)程i∈CS,按照選定的衡量指標計算其公平性ti X ;

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

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

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

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

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

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

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

1.3.4 細粒度緩存分區

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

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

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