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

接上文

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

1 基于緩存分區(qū)的分配調(diào)度策略概述

1.1 緩存分區(qū)的背景

在CMP 系統(tǒng)中，一級(jí)緩存通常是私有的，而最后一級(jí)緩存(last level cache,LLC)則在各個(gè)核間共享(下文提到的緩存如無特別說明都是指LLC)。

共享緩存使得多個(gè)線程可以共享某些數(shù)據(jù)，降低通訊延遲，同時(shí)減少數(shù)據(jù)的冗余備份，提高緩存空間利用率。但是，線程間對(duì)于有限共享緩存空間的爭奪，也會(huì)導(dǎo)致緩存失效率的上升，影響系統(tǒng)的吞吐量和公平性。

在單核單線程處理器中最為常用的緩存替換算法是LRU.LRU 不區(qū)分訪存請(qǐng)求的線程來源，同等對(duì)待所有訪存請(qǐng)求，每次發(fā)生緩存失效時(shí)替換最近最少訪問的緩存塊。LRU 在單線程環(huán)境中能夠有效地提高緩存利用率。然而，在多線程環(huán)境下，由于線程間對(duì)于共享緩存空間的爭奪，仍然采用LRU 算法的話，一個(gè)頻繁發(fā)生緩存失效的線程(例如，流媒體應(yīng)用)會(huì)不公平地替換掉其他線程的有用數(shù)據(jù)塊，占用大量乃至全部緩存空間，從而導(dǎo)致其他線程的緩存失效率(MissRate)①大幅上升，破壞系統(tǒng)的公平性;另外，一個(gè)產(chǎn)生大量緩存失效的線程，其數(shù)據(jù)的復(fù)用率(reused)可能很低，而其他線程被替換掉的卻可能是一些常用數(shù)據(jù)，從而降低了共享緩存的利用率，導(dǎo)致總的緩存失效率上升。無論哪種情況，最終結(jié)果都會(huì)使得系統(tǒng)的性能受到嚴(yán)重影響。

1.2 緩存分區(qū)的基本思想

為了降低線程間爭奪緩存空間帶來的影響，一種直觀的想法是對(duì)緩存進(jìn)行分區(qū)，通過明確地把緩存空間分配給各個(gè)核來避免線程間的干擾。一旦某部分緩存被劃分給某個(gè)線程，由該線程獨(dú)享這部分緩存空間，其他線程無權(quán)替換這部分緩存空間中的數(shù)據(jù)，避免了由于緩存爭奪所帶來的額外緩存失效，使得所有線程的請(qǐng)求都能夠得到合理服務(wù)。緩存分區(qū)之后，對(duì)單個(gè)線程而言，相當(dāng)于運(yùn)行在單線程環(huán)境中一樣，因此，在各緩存分區(qū)內(nèi)可以仍然采用LRU算法。

最簡單也最容易實(shí)現(xiàn)的的緩存分區(qū)方式是在程序運(yùn)行前將緩存平均劃分給CMP 系統(tǒng)中的各個(gè)核，稱之為靜態(tài)分區(qū)。但這種做法的缺點(diǎn)是明顯的，不同線程對(duì)于緩存空間需求不一樣，并且即使同一個(gè)線程在不同的執(zhí)行階段對(duì)緩存空間的需求也可能不一樣，而靜態(tài)分區(qū)策略不能有效反映這種情況。部分線程可能劃分到超出需求的緩存空間，導(dǎo)致緩存空間的浪費(fèi)，而另一部分線程對(duì)于緩存空間的需求卻沒有得到滿足。靜態(tài)緩存分區(qū)策略實(shí)際上是把二級(jí)緩存當(dāng)做了各個(gè)處理器的一級(jí)私有緩存的擴(kuò)充，失去了多核共享緩存所能帶來的好處。近年來的大量研究中都不再采用靜態(tài)分區(qū)策略。

1.3 動(dòng)態(tài)緩存分區(qū)

顯然，只有知道各線程的具體訪存行為特征和緩存需求，才能作出最優(yōu)的緩存分區(qū)決策。制定一個(gè)公平有效的緩存分區(qū)策略，需要一個(gè)明確的性能優(yōu)化目標(biāo)，并且根據(jù)線程所處的具體執(zhí)行環(huán)境與執(zhí)行階段，充分利用線程訪存行為的動(dòng)態(tài)特征。在共享緩存分區(qū)中用到的程序動(dòng)態(tài)特征一般指線程在劃定不同大小的緩存空間下所對(duì)應(yīng)產(chǎn)生的緩存失效率。

動(dòng)態(tài)緩存分區(qū)策略的優(yōu)化目標(biāo)一般包括兩類，吞吐量和公平性。吞吐量是針對(duì)系統(tǒng)的整體性能而言。對(duì)于動(dòng)態(tài)緩存分區(qū)策略，一個(gè)常用的評(píng)估吞吐量的指標(biāo)是共享緩存產(chǎn)生的總緩存失效率，通過最小化緩存失效率達(dá)到最大化系統(tǒng)吞吐量的目標(biāo);同時(shí)，緩存失效率低，意味著處理器核等待數(shù)據(jù)返回的阻塞等待時(shí)間減少，提交指令的速度更快，因此，另一個(gè)與系統(tǒng)吞吐量相關(guān)的指標(biāo)是IPC(instructiONsper cycle)。公平性則是指系統(tǒng)中并行運(yùn)行的多個(gè)線程能夠公平的使用共享緩存，不會(huì)存在某些線程占有大部分緩存空間，導(dǎo)致其他線程的緩存失效率大幅增長，性能受到重大影響;公平性同時(shí)關(guān)注系統(tǒng)中的每個(gè)線程，盡量保證所有線程的服務(wù)質(zhì)量得到同等程度的改善。

基于不同的性能優(yōu)化目標(biāo)，提出的緩存分區(qū)策略通常有很大分別。Hsu 等人在其相關(guān)研究中即根據(jù)優(yōu)化目標(biāo)的不同，命名了3 類調(diào)度策略：第1類緩存調(diào)度策略可稱為“capitalist”,該類策略對(duì)于各線程的訪存請(qǐng)求無限制，任其自由爭奪共享資源，“適者生存”,最為常見的即為通用的LRU 替換策略，但是這類調(diào)度策略在多線程環(huán)境下通常對(duì)于系統(tǒng)的吞吐量和公平性都有影響;第2 類是以最大化系統(tǒng)吞吐量為優(yōu)化目標(biāo)的“utilitarian”,該類策略忽視公平性，無法保證單個(gè)線程的性能表現(xiàn);最后一類是以系統(tǒng)公平性為目標(biāo)的“communist”,該類策略盡量確保并行執(zhí)行的各線程的服務(wù)質(zhì)量得到同等程度的改善，不會(huì)有某些線程的性能受到嚴(yán)重影響。

在現(xiàn)代商業(yè)通用處理器上通常有用于計(jì)算系統(tǒng)總緩存失效率的部件，但是制定動(dòng)態(tài)緩存分區(qū)策略需要更詳細(xì)地知道各個(gè)線程的訪存特征信息。一些特別用于獲取線程訪存行為特征的輔助硬件是必要的，本文將在1.3.1 節(jié)中給出相關(guān)介紹。

在取得必需的訪存信息后，即可以根據(jù)不同的優(yōu)化目標(biāo)制定相應(yīng)的緩存分區(qū)策略，在1.3.2 節(jié)和1.3.3 節(jié)中將分別從追求最大化吞吐量和公平性的角度對(duì)緩存分區(qū)進(jìn)行研究。在1.3.4 節(jié)則針對(duì)緩存分區(qū)粒度過大(通常是按路分區(qū))的問題介紹了一些解決方案。

1.3.1 訪存監(jiān)控器

大多數(shù)商業(yè)通用處理器都有一個(gè)硬件緩存監(jiān)控器。緩存監(jiān)控器包括兩類計(jì)數(shù)器，一類用于計(jì)數(shù)系統(tǒng)總的訪存數(shù)，另一類計(jì)數(shù)系統(tǒng)總的緩存失效數(shù)，由此可以計(jì)算出系統(tǒng)的緩存失效率。但如前所述，要制定動(dòng)態(tài)緩存分區(qū)策略，還需要一些特別的輔助硬件來獲取各個(gè)線程訪存行為的特征信息。對(duì)于緩存分區(qū)而言，線程在各種可能的緩存空間下對(duì)應(yīng)產(chǎn)生的緩存失效率是一個(gè)極其有用的信息。一種簡單的做法是把每個(gè)線程在各種緩存配置下分別執(zhí)行一次以獲取相應(yīng)緩存失效率。顯然，這種方法過于低效，沒有實(shí)用性。

當(dāng)多個(gè)線程并行運(yùn)行時(shí)，為了在不實(shí)際改變緩存配置的前提下，獲取各線程在不同緩存空間對(duì)應(yīng)的緩存失效率，Hsu 等人在文獻(xiàn)[2-3]中提出一種訪存監(jiān)控器(memory monitor,MON)。對(duì)于N 路組相聯(lián)緩存，每個(gè)MON 有N 個(gè)路計(jì)數(shù)器(way-counter)。

這組路計(jì)數(shù)器根據(jù)線程對(duì)緩存各路的使用情況按照LRU 次序排列。當(dāng)對(duì)一個(gè)MRU(most recently used)緩存路中的緩存行發(fā)生緩存命中時(shí)，counter(0)增加1;當(dāng)對(duì)一個(gè)LRU 緩存路中的緩存行發(fā)生緩存命中時(shí)，counter(N-1)增加1,以此類推。MON 另有一個(gè)計(jì)數(shù)器用于計(jì)數(shù)一個(gè)線程對(duì)共享緩存的總訪存次數(shù)。