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

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

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

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

動(dòng)物分類法將線程的訪存行為特征與幾種動(dòng)物性格相對(duì)應(yīng)，具體如下：

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

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

針對(duì)UCP 中沒(méi)有提出一個(gè)形式化的算法來(lái)對(duì)線程進(jìn)行分類的缺點(diǎn)，文獻(xià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.

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

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

If ((Access>=1000) AND

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

Animal:=Devil;

Else

Animal:=Not_Devil.

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

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

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

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

l 為性能損失函數(shù)，g 為性能增益函數(shù)，wi 和wc分別表示一個(gè)線程獨(dú)占的緩存路數(shù)及系統(tǒng)總的緩存路數(shù)。

一個(gè)緩存分區(qū)方案所對(duì)應(yīng)的總的系統(tǒng)性能增益為：

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

1.3.3 公平性

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

Kim 等人在文獻(xiàn)中從改善系統(tǒng)公平性的角度對(duì)緩存分區(qū)進(jìn)行了研究。實(shí)驗(yàn)證明，以改善系統(tǒng)公平性為優(yōu)化目標(biāo)的緩存分區(qū)策略通常可以同時(shí)提高系統(tǒng)吞吐量，但是以最大化吞吐量為目標(biāo)的緩存分區(qū)策略則對(duì)無(wú)法保障公平性。