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

為每個處理器核配置一個MON 用于記錄運行在該核上的線程的訪存信息。從而，當該線程只能使用N 路緩存的其中幾路時，只需將另幾路緩存的路計數器中的緩存命中數相加，就可以得出由于減少的可用緩存空間所帶來的額外緩存失效數。

通過MON 獲取線程訪存信息并制定相應緩存分區策略的基本框架如圖1 所示。圖1 中，該CMP系統包括兩個處理器核，共享緩存和一個緩存分區模塊;每個核有一個MON,用于獲取運行在該核上線程的訪存信息;然后將各個線程的訪存信息集中到緩存分區模塊(cache partitioning module)，根據具體的優化目標，制定適當的緩存分區決策。

每路緩存對應一個計數器的結果是將一路緩存作為一個緩存分區單元，在系統的緩存路數足夠多且線程數較少時，這種做法可以取得較為理想的效果。但是當線程數增多時，緩存的路數很難跟著成規模地增長，這種按路分區的做法會顯得粒度過大。

為了獲取更為精確的細粒度信息，也可以再為每一個緩存組增加一個組計數器(set-counter)，這樣又會帶來過大的硬件開銷。一種折中的做法是，將M 組緩存看作一個集(group)，增加相應的集計數器(group-counter)，從而做到兼顧性能與開銷。

通過MON 既可以得到線程隨著可用緩存空間減小導致的緩存失效率的增加，也能反過來計算當線程的可用緩存空間增加時，該線程緩存失效率的降低。這種隨著緩存空間的增加帶來的性能提升稱為邊際效益。因而，MON 有時也被稱為邊際效益計數器(marginal gain counter)。當然，制定動態緩存分區策略還可以使用其他方式獲取所需訪存信息，此處不再贅述，后文用到時再做介紹。

前文提到，基于不同的性能優化目標，制定的緩存分區策略通常有著較大區別，下面將按照不同的優化目標來分別介紹一些相關工作。

1.3.2 最大化吞吐量

對系統性能進行優化的一個常用指標是使得系統可以在單位時間內完成更多的工作，即最大化系統吞吐量。在緩存分區中，可以用總的緩存失效率或者系統IPC 作為衡量標準。

2002 年，Hsu 等人在文獻中提出的緩存分區策略以最大化吞吐量為目標。其主要思想是：通過前述MON 可以得到各線程在前一執行階段的緩存需求以及各線程從額外的緩存空間可以獲取的邊際效益。此處的邊際效益指線程通過額外的緩存空間減少的緩存失效數。

定義Mi(c)為線程i 在給定緩存空間c 時產生的緩存失效數。當其可用緩存空間從c 增加至c+1 時，該線程減少的緩存失效數Gi(c)即為其所獲邊際效益：

滿足最大化吞吐量優化目標的最優分區策略則需要最小化如下表達式：

其中1 2 { , ,…， } N c c c 應該滿足限制條件

，C 是共享緩存之和。

通常線程的邊際效益是緩存空間的單調遞減函數，因而可以使用貪心算法獲得最優的緩存分區方式：

1)初始化時，各線程分得的緩存空間ci 都為0;2)根據MON獲取的上一執行階段的訪存信息，每次將單位粒度(通常按路分配)的緩存空間分給能夠取得最大邊際效益gk(ck)的線程，直至所有的緩存空間分配完畢;3)將各個MON 中的計數器清零或者將數值按一定比例減小(這種做法可以有效利用線程的過往歷史信息)，繼續獲取線程在新的執行階段的訪存信息;4)當各線程的訪存特征發生顯著改變時，按照步驟2)重新分配緩存空間，達到動態調整的效果。

當收益曲線不是一個單調遞減函數時，貪心算法并不一定能找到理想的分區策略，可能存在短視的問題，Hsu 也在文中給出了相應的改進算法。

總的看來，Hsu 等人提出的緩存分區方案可以有效提高系統吞吐量，是很有價值的一項研究成果。

實際上，之后很多這方面的研究都是基于他們的工作成果展開的。文獻中提出的MON 付出的硬件改動成本很低。然而，MON 直接從共享緩存獲取各個線程的緩存命中/失效信息在很大程度上受到并行運行的其他線程的影響，不能完全準確反映一個線程獨享不同緩存空間時分別應該產生的緩存失效率。

其后，Qureshi 等人在文獻[4]中提出一種緩存分區策略(utility-based cache partition,UCP)。

UCP 的優化目標也是最大化系統吞吐量。與Hsu 對于邊際效益的定義相同，UCP 中把隨著緩存空間增加而減少的緩存失效數稱之為收益(utility)。在UCP 中提出的收益監控器(utility monitor,UMON)針對MON 存在的缺點進行了改進，每個UMON 增加一組輔助標簽目錄(auxiliary tag directory,ATD)。

ATD 除了不包含具體的數據項，與共享緩存保持相同結構，仍然使用LRU 替換策略。各線程間的ATD保持獨立。從而，借助UMON 獲取的緩存收益信息避免了并行線程的影響，能夠更為準確地反映一個線程獨立的訪存行為特征。

在UCP 中根據不同程序從額外的緩存空間獲取的收益情況不同，可以把應用劃分為3 類：當分得的緩存空間增多時，其收益不會發生顯著變化的稱為低收益類(low utility);隨著所分配的緩存空間增加其收益顯著上升的應用稱為高收益類(highutility);當分配的緩存空間增加到某個臨界點后其收益不再繼續提升的稱為飽和收益類(saturating utility)。

低收益類應用在并行運行時，彼此間對于自身可用的緩存空間不敏感，因而緩存分區并非必需的;當幾個飽和收益類應用共同運行時，只要知道各應用的緩存需求，即可分別為其分配合理的緩存空間;當飽和收益類應用與低收益類應用共同運行時，優先滿足飽和收益類應用的緩存需求;而高收益類的應用在與其他類應用共同運行時，由于高收益類應用總是對于可用緩存空間大小很敏感，需要特別對待。