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ì)于有限共享緩存空間的爭(zhēng)奪，也會(huì)導(dǎo)致緩存失效率的上升，影響系統(tǒng)的吞吐量和公平性。

在單核單線程處理器中最為常用的緩存替換算法是LRU.LRU 不區(qū)分訪存請(qǐng)求的線程來源，同等對(duì)待所有訪存請(qǐng)求，每次發(fā)生緩存失效時(shí)替換最近最少訪問的緩存塊。LRU 在單線程環(huán)境中能夠有效地提高緩存利用率。然而，在多線程環(huán)境下，由于線程間對(duì)于共享緩存空間的爭(zhēng)奪，仍然采用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ū)的基本思想

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

最簡(jiǎn)單也最容易實(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ū)策略。