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

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

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

每路緩存對應一個(gè)計數器的結果是將一路緩存作為一個(gè)緩存分區單元，在系統的緩存路數足夠多且線(xiàn)程數較少時(shí)，這種做法可以取得較為理想的效果。但是當線(xiàn)程數增多時(shí)，緩存的路數很難跟著(zhù)成規模地增長(cháng)，這種按路分區的做法會(huì )顯得粒度過(guò)大。

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

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

前文提到，基于不同的性能優(yōu)化目標，制定的緩存分區策略通常有著(zhù)較大區別，下面將按照不同的優(yōu)化目標來(lái)分別介紹一些相關(guān)工作。

1.3.2 最大化吞吐量

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

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

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

滿(mǎn)足最大化吞吐量?jì)?yōu)化目標的最優(yōu)分區策略則需要最小化如下表達式：

其中1 2 { , ,…， } N c c c 應該滿(mǎn)足限制條件

，C 是共享緩存之和。

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

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

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

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

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

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

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

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

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

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