cache基本知識培訓教程[2]

cache基本知識培訓教程[2]

相聯(lián)度越高（即 n 的值越大）， Cache 空間的利用率就越高，塊沖突概率就越低，因而 Cache 的失效率就越低。塊沖突是指一個主存塊要進入已被占用的 Cache 塊位置。顯然，全相聯(lián)的失效率最低，直接映象的失效率最高。雖然從降低失效率的角度來看， n 的值越大越好，但在后面我們將看到，增大 n 值并不一定能使整個計算機系統(tǒng)的性能提高，而且還會使 Cache 的實現(xiàn)復雜度和代價增大。因此，絕大多數(shù)計算機都采用直接映象、兩路組相聯(lián)或四路組相聯(lián)。特別是直接映像，采用得最多。

??? 4.2.2查找方法

??? 當CPU訪問Cache時，如何確定Cache中是否有所要訪問的塊？若有的話，如何確定其位置？這是通過查找目錄表來實現(xiàn)的。Cache中設有一個目錄表，該表所包含的項數(shù)與Cache的塊數(shù)相同，每一項對應于Cache中的一個塊。當一個主存塊被調(diào)入Cache中某一個塊位置時，它的標識就被填入目錄表中與該Cache塊相對應的項中，并且該項的有效位被置“1”。

根據(jù)映象規(guī)則不同，一個主存塊可能映象到Cache中的一個或多個Cache塊位置。為便于討論，我們把它們稱為候選位置。當CPU訪問該主存塊時，必須且只需查找它的候選位置所對應的目錄表項（標識）。如果有與所訪問的主存塊相同的標識，且其有效位為“1”，則它所對應的Cache塊即是所要找的塊。為了保證速度，對各候選位置的標識的檢查比較應并行進行。

并行查找的實現(xiàn)方法有兩種：

??? (1) 用相聯(lián)存儲器實現(xiàn)；

??? (2) 用單體多字存儲器和比較器來實現(xiàn)。

??? 圖4.2.6中畫出了用第二種方法來實現(xiàn)4路組相聯(lián)的情況。

?

??? 由圖中可以看出，n 越大，實現(xiàn)查找的機制就越復雜，代價就越高。直接映象 Cache 的查找最簡單：只需查找一個位置。所訪問的塊要么就在這個位置上，要么就不在 Cache 中。

4.2.3替換算法

??? 由于主存中的塊比 Cache 中的塊多，所以當要從主存調(diào)入一個塊到 Cache 中時，會出現(xiàn)該塊所映象到的一組（或一個） Cache 塊已全被占用的情況。這時，需強迫騰出其中的某一塊，以接納新調(diào)入的塊。那么應該替換哪一塊呢? 這就是替換算法所要解決的問題。直接映象 Cache 中的替換很簡單，因為只有一個塊，別無選擇。而在組相聯(lián)和全相聯(lián) Cache 中，則有多個塊供選擇，我們當然希望應盡可能避免替換掉馬上就要用到的信息。主要的替換算法有以下三種。

??? 1. 隨機法

??? 為了均勻使用一組中的各塊，這種方法隨機地選擇被替換的塊。有些系統(tǒng)采用偽隨機數(shù)法產(chǎn)生塊號，以使行為可再現(xiàn)。這對于調(diào)試硬件是很有用的。這種方法的優(yōu)點是簡單、易于用硬件實現(xiàn)，但這種方法沒有考慮 Cache 塊過去被使用的情況，反映不了程序的局部性，所以其失效率比 LRU 的高。

??? 2. 先進先出法FIFO（ First-In-First-Out）

??? 這種方法選擇最早調(diào)入的塊作為被替換的塊。其優(yōu)點也是容易實現(xiàn)。它雖然利用了同一組中各塊進入Cache的順序這一“歷史”信息，但還是不能正確地反映程序的局部性。因為最先進入的塊，很可能是經(jīng)常要用到的塊。

??? 3. 最近最少使用法LRU（Least Recently Used）

??? 這種方法本來是指選擇近期最少被訪問的塊作為被替換的塊。但由于實現(xiàn)比較困難，現(xiàn)在實際上實現(xiàn)的 LRU 都只是選擇最久沒有被訪問過的塊作為被替換的塊。這種方法所依據(jù)的是局部性原理的一個推論：如果最近剛用過的塊很可能就是馬上要再用到的塊，則最久沒用過的塊就是最佳的被替換者。LRU 能較好地反映程序的局部性，因而其失效率在上述三種方法中是最低的。但是 LRU 比較復雜，硬件實現(xiàn)比較困難，特別是當組的大小增加時，LRU 的實現(xiàn)代價會越來越高，而且經(jīng)常只是近似地實現(xiàn)。

??? LRU 和隨機法分別因其失效率低和實現(xiàn)簡單而被廣泛采用。

??? 4.2.4寫策略

??? 處理器對 Cache 的訪問主要是讀訪問，因為所有對指令的訪問都是“讀”，而且大多數(shù)指令都不對存儲器進行“寫”。第二章中指出，DLX 程序的 Store 和 Load 指令所占的比例分別為9%和26%，由此可得“寫”在所有訪存操作中所占的比例為

??? 9%／(100% ＋ 26% ＋ 9%) ≈ 7%，

??? 而在訪問數(shù)據(jù) Cache 操作中所占的比例為

??? 9%／(26% ＋ 9%) ≈ 25%。

??? 基于上述百分比，特別是考慮到處理器一般是對“讀”要等待，而對“寫”卻不必等待，應該說設計 Cache 要針對最經(jīng)常發(fā)生的“讀”進行優(yōu)化。然而，Amdahl定律告訴我們，高性能 Cache 的設計不能忽略“寫”的速度。

??? 幸運的是，最經(jīng)常發(fā)生的“讀”也是最容易提高速度的。訪問 Cache 時，在讀出標識進行比較的同時，可以把相應的 Cache 塊也讀出。如果命中，則把該塊中所請求的數(shù)據(jù)立即送給 CPU；若為失效，則所讀出的塊沒什么用處，但也沒什么壞處，置之不理就是了。

然而，對于“寫”卻不是如此。只有在讀出標識并進行比較，確認是命中后，才可對Cache塊進行寫入。由于檢查標識不能與寫入 Cache 塊并行進行，“寫”一般比“讀”花費更多的時間。

??? 按照存儲層次的要求， Cache 內(nèi)容應是主存部分內(nèi)容的一個副本。但是“寫”訪問卻有可能導致它們內(nèi)容的不一致。例如，當處理機進行“寫”訪問，往 Cache 寫入新的數(shù)據(jù)后，則 Cache 中相應單元的內(nèi)容已發(fā)生變化，而主存中該單元的內(nèi)容卻仍然是原來的。這就產(chǎn)生了所謂的 Cache 與主存內(nèi)容的一致性問題。顯然，為了保證正確性，主存的內(nèi)容也必須更新。至于何時更新，這正是寫策略所要解決的問題。

??? 寫策略是區(qū)分不同 Cache 設計方案的一個重要標志。寫策略主要有兩種：

??? 1. 寫直達法

??? 寫直達法也稱為存直達法。它是指在執(zhí)行“寫”操作時，不僅把信息寫入 Cache 中相應的塊，而且也寫入下一級存儲器中相應的塊。

??? 2. 寫回法

??? 寫回法也稱為拷回法。它只把信息寫入 Cache 中相應的塊。該塊只有在被替換時，才被寫回主存。

??? 為了減少在替換時塊的寫回，常采用污染位標志。即為 Cache 中的每一塊設置一個“污染位”（設在與該塊相應的目錄表項中），用于指出該塊是“臟”的（被修改過）還是“干凈”的（沒被修改過）。替換時，若被替換的塊是“干凈”的，則不必寫回下一級存儲器，因為這時下一級存儲器中相應塊的內(nèi)容與 Cache 中的一致。

寫回法和寫直達法各有特色。兩者相比，寫回法的優(yōu)點是速度快，“寫”操作能以 Cache 存儲器的速度進行。而且對于同一單元的多個寫最后只需一次寫回下一級存儲器，有些“寫”只到達 Cache ，不到達主存，因而所使用的存儲器頻帶較低。這使得寫回法對于多處理機很有吸引力。寫直達法的優(yōu)點是易于實現(xiàn)，而且下一級存儲器中的數(shù)據(jù)總是最新的。后一個優(yōu)點對于 I/O 和多處理機來說是重要的。I/O 和多處理機經(jīng)常難以在這兩種方法之間選擇：它們既想要用寫回法來減少訪存的次數(shù)，又想要用寫直達法來保持 Cache 與下一級存儲器的一致性。

??? 采用寫直達法時，若在進行“寫”操作的過程中 CPU 必須等待，直到“寫”操作結束，則稱 CPU 寫等待。減少寫等待的一種常用的優(yōu)化技術是采用寫緩沖器。 CPU 一旦把數(shù)據(jù)寫入該緩沖器，就可以繼續(xù)執(zhí)行，從而使下一級存儲器的更新和 CPU 的執(zhí)行重疊起來。不過，在后面很快就會看到，即使有寫緩沖器，也可能發(fā)生寫等待。

??? 由于“寫”訪問并不需要用到所訪問單元中原有的數(shù)據(jù)。所以，當發(fā)生寫失效時，是否調(diào)入相應的塊，有兩種選擇：

??? (1) 按寫分配法：寫失效時，先把所寫單元所在的塊調(diào)入 Cache，然后再進行寫入。這與讀失效類似。這種方法也稱為寫時取方法。

??? (2) 不按寫分配法：寫失效時，直接寫入下一級存儲器而不將相應的塊調(diào)入 Cache。這種方法也稱為繞寫法。

??? 雖然上述兩種方法都可應用于寫直達法和寫回法，寫回法 Cache 一般采用按寫分配法（這樣，以后對那個塊的“寫”就能被 Cache 捕獲）。而寫直達法一般采用不按寫分配法（因為以后對那個塊的“寫”仍然還要到達下一級存儲器）。