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

通過(guò)對程序的訪(fǎng)存特征進(jìn)行研究并分類(lèi)，解釋不同的程序從緩存分區的獲益狀況，可以幫助制定有效的緩存分區策略。但是，UCP 中提出的分類(lèi)方式更多地是對于一個(gè)線(xiàn)程收益曲線(xiàn)的直觀(guān)判斷，并沒(méi)有提出一個(gè)形式化的算法來(lái)對程序進(jìn)行準確歸類(lèi)。因而，很難在硬件上實(shí)現基于該分類(lèi)準則對程序的歸類(lèi)。另外，UCP 通過(guò)在每個(gè)核的UMON 中增加ATD,以獲取更為準確的訪(fǎng)存信息，但是帶來(lái)了較大的硬件開(kāi)銷(xiāo)?？梢酝ㄟ^(guò)抽樣調查線(xiàn)程在部分緩存中的訪(fǎng)存行為近似估計其全局效果，例如在每個(gè)UMON 中的ATD 只保留共享緩存的奇數組(set)的標簽目錄，從而可以把硬件開(kāi)銷(xiāo)減半。

類(lèi)似地，Lin 等人在文獻中從OS 層面通過(guò)頁(yè)染色對程序進(jìn)行分類(lèi)。在該研究中，將一個(gè)程序分別單獨運行在配置為1MB 和4MB 的共享緩存系統中，并觀(guān)察其運行在1MB 配置下相對于運行于4MB緩存配置時(shí)的性能降低程度，然后按其性能降低程度對程序分為4 種 以顏色命名的類(lèi)。然而，因其需要將程序單獨在不同緩存配置下運行多次，來(lái)得出相關(guān)分類(lèi)信息，這種分類(lèi)方式也很難實(shí)際用于動(dòng)態(tài)緩存分區。

Xie 等人在文獻中提出了一種動(dòng)物分類(lèi)法(animal_based taxonomy)。借助UCP 中提出的UMON 獲取訪(fǎng)存信息，按照程序的訪(fǎng)存行為特征對線(xiàn)程分類(lèi)，并根據分類(lèi)結果制定相應緩存分區策略。

動(dòng)物分類(lèi)法將線(xiàn)程的訪(fǎng)存行為特征與幾種動(dòng)物性格相對應，具體如下：

Turtles,對應于對共享緩存空間需求很低的線(xiàn)程;Sheep,對應只需要分配給很少的共享緩存即可達到較低的緩存失效率的線(xiàn)程，這類(lèi)線(xiàn)程對于可用緩存空間大小不敏感;Rabbit,這類(lèi)線(xiàn)程對可用的緩存空間大小敏感，但是只要分配了充足的緩存空間就可以達到較低緩存失效率;Devil,這類(lèi)線(xiàn)程頻繁發(fā)出對共享緩存的訪(fǎng)存請求，但是無(wú)論占用多少可用緩存空間，總是會(huì )產(chǎn)生大量緩存失效。這類(lèi)線(xiàn)程難以從分配到的更多緩存空間獲得明顯收益，并且侵略性很強，對于并行運行的其他線(xiàn)程有著(zhù)消極影響。

動(dòng)物分類(lèi)法中用于對線(xiàn)程進(jìn)行分類(lèi)的指標包括：Access,一個(gè)線(xiàn)程對于共享緩存總的訪(fǎng)存次數;Missessolo,一個(gè)線(xiàn)程獨享全部共享緩存時(shí)產(chǎn)生的緩存失效數;MissRatesolo=Missessolo/Access,緩存失效率;WayNeededk,其中k 為一個(gè)百分數，該式表示至少需要多少路緩存才可以達到該線(xiàn)程獨享緩存時(shí)性能的相應百分比。以上信息都可以通過(guò)UMON 獲得。

針對UCP 中沒(méi)有提出一個(gè)形式化的算法來(lái)對線(xiàn)程進(jìn)行分類(lèi)的缺點(diǎn)，文獻中給出了一個(gè)具體的算法：

If (Access1000)

Animal:=Turtle;

Else if ((MissRatesolo>10%)OR (Missessolo>4000))

Animal:=Devil;

Else if (WayNeeded95%>N/2)

Animal:=Rabbit;

Else

Animal:=Sheep.

線(xiàn)程只產(chǎn)生很少的訪(fǎng)存請求( 例如，Access1000)，將其歸類(lèi)為T(mén)urtle 類(lèi);若線(xiàn)程即使占有全部緩存空間仍然產(chǎn)生大量緩存失效或者較高的緩存失效率( 例如， (MissRatesolo>10%) OR(Missessolo>4000))，則將其歸類(lèi)為Devil 類(lèi);當線(xiàn)程占有一定可用緩存空間時(shí)的性能表現即能夠接近獨占全部緩存空間時(shí)的性能時(shí)( 例如，WayNeeded95%>N/2)，將其歸類(lèi)為Rabbit;否則，線(xiàn)程為Sheep 類(lèi)。根據具體情況，還可以通過(guò)調節分類(lèi)參數以取得合適的分類(lèi)效果。

實(shí)際上很多情況下，過(guò)于具體的分類(lèi)信息對于緩存分區并無(wú)太大幫助。最重要的是要篩選出并行運行線(xiàn)程中侵略性最強的Devil 類(lèi)線(xiàn)程。因為這類(lèi)線(xiàn)程會(huì )占用大量緩存空間，嚴重影響其他線(xiàn)程的性能。因此，上述算法也可以簡(jiǎn)化到只區分Devil 類(lèi)和非Devil 類(lèi)線(xiàn)程：

If ((Access>=1000) AND

((MissRatesolo>10%) OR (Missessolo>4000)))

Animal:=Devil;

Else

Animal:=Not_Devil.

當系統中不存在Devil 類(lèi)線(xiàn)程時(shí)，可以認為線(xiàn)程間對共享緩存不會(huì )發(fā)生激烈爭奪，因而直接采用LRU 替換策略;當存在Devil 類(lèi)線(xiàn)程時(shí)，需要限制Devil 類(lèi)線(xiàn)程對于系統中其他線(xiàn)程的影響，給其劃分一塊固定的可用緩存空間，其他線(xiàn)程共享剩余緩存。

簡(jiǎn)化后的算法復雜度和硬件開(kāi)銷(xiāo)都將大大降低，并且在線(xiàn)程較少時(shí)能取得較優(yōu)的效果;當線(xiàn)程數目增多時(shí)，這種算法的效果則很難得到保證。

在文獻中將線(xiàn)程的緩存失效分為兩類(lèi)：一種稱(chēng)為局部失效(local misses)，這類(lèi)緩存失效只要增加分配一路緩存，即可以變?yōu)槊袪顟B(tài);另一種稱(chēng)為全局失效(global misses)，這類(lèi)緩存失效需要增加分配一路以上的緩存才能由失效變?yōu)槊小?p>緩存分區模塊監測每個(gè)線(xiàn)程的局部與全局失效，從而知道每一個(gè)線(xiàn)程的緩存需求。用CL,CL-1 分別統計單個(gè)線(xiàn)程在其緩存分區內LRU 和LRU-1 位置的緩存命中數;用一個(gè)計數器CG 來(lái)確定全局失效數。

將緩存分區策略的分區單位粒度設定為最多2路緩存，則存在-2,-1,0,1,2 路5 種可能的分區單位。當一個(gè)線(xiàn)程的緩存減少或增加時(shí)，其性能損失或增益情況表示如下：

l 為性能損失函數，g 為性能增益函數，wi 和wc分別表示一個(gè)線(xiàn)程獨占的緩存路數及系統總的緩存路數。

一個(gè)緩存分區方案所對應的總的系統性能增益為：

緩存分區策略需要在滿(mǎn)足限制條件的前提下最大化G.這種算法是一種窮舉的做法，需要列出所有的分區可能性并進(jìn)行比較，在系統線(xiàn)程數目較少的情況下可以取得很好的效果;隨著(zhù)線(xiàn)程增加將發(fā)生狀態(tài)空間的爆炸。

1.3.3 公平性

系統的性能好壞不止與吞吐量相關(guān)，公平性也是一個(gè)重要的衡量指標。前述研究的優(yōu)化目標都主要集中于最大化系統吞吐量而忽略了公平性。這可能導致系統中某些線(xiàn)程的訪(fǎng)存請求長(cháng)時(shí)間得不到服務(wù)乃至餓死的情況發(fā)生，對該線(xiàn)程的性能造成影響，進(jìn)而也會(huì )影響到系統的性能。本節的研究主要著(zhù)眼于系統的公平性，以達到同時(shí)改善所有線(xiàn)程性能的目的。

Kim 等人在文獻中從改善系統公平性的角度對緩存分區進(jìn)行了研究。實(shí)驗證明，以改善系統公平性為優(yōu)化目標的緩存分區策略通?？梢酝瑫r(shí)提高系統吞吐量，但是以最大化吞吐量為目標的緩存分區策略則對無(wú)法保障公平性。