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

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

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

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

動物分類法將線程的訪存行為特征與幾種動物性格相對應，具體如下：

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

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

針對UCP 中沒有提出一個形式化的算法來對線程進行分類的缺點，文獻中給出了一個具體的算法：

If (Access1000)

Animal:=Turtle;

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

Animal:=Devil;

Else if (WayNeeded95%>N/2)

Animal:=Rabbit;

Else

Animal:=Sheep.

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

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

If ((Access>=1000) AND

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

Animal:=Devil;

Else

Animal:=Not_Devil.

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

簡化后的算法復雜度和硬件開銷都將大大降低，并且在線程較少時能取得較優的效果;當線程數目增多時，這種算法的效果則很難得到保證。

在文獻中將線程的緩存失效分為兩類：一種稱為局部失效(local misses)，這類緩存失效只要增加分配一路緩存，即可以變為命中狀態;另一種稱為全局失效(global misses)，這類緩存失效需要增加分配一路以上的緩存才能由失效變為命中。

緩存分區模塊監測每個線程的局部與全局失效，從而知道每一個線程的緩存需求。用CL,CL-1 分別統計單個線程在其緩存分區內LRU 和LRU-1 位置的緩存命中數;用一個計數器CG 來確定全局失效數。

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

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

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

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

1.3.3 公平性

系統的性能好壞不止與吞吐量相關，公平性也是一個重要的衡量指標。前述研究的優化目標都主要集中于最大化系統吞吐量而忽略了公平性。這可能導致系統中某些線程的訪存請求長時間得不到服務乃至餓死的情況發生，對該線程的性能造成影響，進而也會影響到系統的性能。本節的研究主要著眼于系統的公平性，以達到同時改善所有線程性能的目的。

Kim 等人在文獻中從改善系統公平性的角度對緩存分區進行了研究。實驗證明，以改善系統公平性為優化目標的緩存分區策略通常可以同時提高系統吞吐量，但是以最大化吞吐量為目標的緩存分區策略則對無法保障公平性。