[科普中國]-塊替換策略

塊替換策略是高速緩存設(shè)計的一個重要方面。當(dāng)不命中時，必須將相應(yīng)的主存塊取入高速緩存，相應(yīng)地，要把其中已有的某一塊替換出去。若高速緩存內(nèi)有無效塊，則替換是不成問題的。對于直接映射高速緩存，只有1個塊可供替換。對于相聯(lián)映射型的高速緩存，主要有隨機(jī)和最近最少使用兩種替換策略。最近最少使用策略利用了時間局部性，可能實現(xiàn)較高的命中率，但當(dāng)需要追蹤的塊較多時，實現(xiàn)起來比較復(fù)雜。

簡介在高速緩沖存儲器（Cache）中，塊是指Cache存儲空間分為多個大小相同的存儲空間，是基本的 Cache 存儲單位。一個 Cache 塊能夠存儲若干字節(jié)的數(shù)據(jù)。與主存空間中頁相對應(yīng)。Cache工作原理要求它盡量保存最新數(shù)據(jù)，當(dāng)從主存向Cache傳送一個新塊，而Cache中可用位置已被占滿時，就會產(chǎn)生Cache替換的問題。塊替換策略是指將Cache中最少使用的塊替換出去，使得訪問的頁不在Cache中在的次數(shù)為最少，即主要目標(biāo)獲得最高的命中率。塊替換策略與塊映射策略密切相關(guān)。

替換算法最不經(jīng)常使用算法

LFU（Least Frequently Used，最不經(jīng)常使用）算法將一段時間內(nèi)被訪問次數(shù)最少的那個塊替換出去。每塊設(shè)置一個計數(shù)器，從0開始計數(shù)，每訪問一次，被訪塊的計數(shù)器就增1。當(dāng)需要替換時，將計數(shù)值最小的塊換出，同時將所有塊的計數(shù)器都清零。這種算法將計數(shù)周期限定在對這些特定塊兩次替換之間的間隔時間內(nèi)，不能嚴(yán)格反映近期訪問情況，新調(diào)入的塊很容易被替換出去。

最近最少使用算法

最近最少使用(Least Recently Used, LRU )替換策略能夠依據(jù)Cache塊的使用情況，選擇離最近時間點最近而最少被使用的Cache 塊進(jìn)行替換這種策略較好地體現(xiàn)程序局部性而使得系統(tǒng) Cache 丟失率較小。這種方法實現(xiàn)方法眾多有計數(shù)器法、寄存器棧法及硬件邏輯比較對法，其中計數(shù)器法實現(xiàn) LRU 替換策略最為簡單，因此這種替換策略得到了廣泛的使用，現(xiàn)代多核處理器依然沿用了這種替換策略1。這種算法保護(hù)了剛調(diào)入Cache的新數(shù)據(jù)塊，具有較高的命中率。LRU算法不能肯定調(diào)出去的塊近期不會再被使用，所以這種替換算法不能算作最合理、最優(yōu)秀的算法。但是研究表明，采用這種算法可使Cache的命中率達(dá)到90%左右。

隨機(jī)替換算法

最簡單的替換算法是隨機(jī)替換。隨機(jī)替換算法完全不管Cache的情況，簡單地根據(jù)一個隨機(jī)數(shù)選擇一塊替換出去。隨機(jī)替換算法在硬件上容易實現(xiàn)，且速度也比前兩種算法快。缺點則是降低了命中率和Cache工作效率。Cache命中率除了和替換算法有關(guān)外，還與Cache的容量及塊的大小有關(guān)。

先進(jìn)先出算法

先進(jìn)先出策略(FIFO)：最先替換進(jìn)入 Cache 的塊將最先被替換出。這就導(dǎo)致被多次命中的塊很可能是最先調(diào)入 Cache 的塊，而這個塊將被優(yōu)先替換，不符合局部性規(guī)律。

塊映射策略Cache的容量很小，它保存的內(nèi)容只是主存內(nèi)容的一個子集，且Cache與主存的數(shù)據(jù)交換是以塊為單位的。為了把信息放到Cache中，必須應(yīng)用某種函數(shù)把主存地址定位到Cache中，這稱為地址映射，或塊映射。

當(dāng)需要將來自內(nèi)存的新數(shù)據(jù)塊裝入高速緩存時，由塊映射策略決定它的存放位置。根據(jù)塊在高速緩存內(nèi)的位置，塊映射策略可分成如3類：

直接映射，每個塊在高速緩存中只能有1個位置。該位置通常由求模運算得到，即：高速緩存內(nèi)塊號=塊地址(mod 高速緩存中塊數(shù))。

全相聯(lián)映射，塊可以放在高速緩存中的任意位置。

組相聯(lián)映射，高速緩存分為若干個組，塊先映射至組，在組中的位置任意。塊向組的映射通常也采用取模運算。塊地址中對應(yīng)于組號的若干位稱為索引。若組中有n 塊，則稱高速緩存是n路組相聯(lián)的。

高速緩存對每個塊都設(shè)立1 個標(biāo)志域，其中包括塊地址和該地址是否有效的信息。為了實現(xiàn)快速訪問，在相聯(lián)映射型高速緩存中，總是同時查找所有的標(biāo)志。

高速緩沖存儲器高速緩沖存儲器（Cache）位于中央處理器與主存儲器之間，對程序員透明的一種高速小容量存儲器。高速緩沖存儲器簡稱高速緩存。它是存儲器層次結(jié)構(gòu)的最頂層，其下層是容量相對較大和訪問時間較長的主存儲器。在配備有高速緩存的計算機(jī)中，每次訪問存儲器都先訪問高速緩存，若欲訪問的數(shù)據(jù)在高速緩存中，則訪問到此為止；否則，再訪問主存儲器，并把有關(guān)數(shù)據(jù)取入高速緩存。這樣，如果大部分針對高速緩存的訪問都能成功，則在保持主存儲器容量不變的前提下，訪存速度可接近高速緩存的存取速度。高速緩存的設(shè)置是所有現(xiàn)代計算機(jī)系統(tǒng)發(fā)揮高性能的重要因素之一。高速緩存的工作機(jī)制體現(xiàn)了局部性原則。所謂局部性，是指程訪問代碼和數(shù)據(jù)的不均勻性，它包括：時間局部性：如果某位置已被訪問，則該位置很可能在短時間內(nèi)還要再被訪問；空間局部性：如果某位置已被訪問，則其鄰近位置很可能還要被訪問。因此， 只要程序有較好的訪存局部性，高速緩存就能發(fā)揮作用。

命中率高速緩存的組織及對高速緩存的訪問都是以行或塊為單位的，通常1行包括1個或多個字。行也是高速緩存與主存儲器交換數(shù)據(jù)的最小單位。訪存時，若能在高速緩存中找到所需數(shù)據(jù)，稱為高速緩存命中，否則就是不命中。命中次數(shù)與訪存總次數(shù)的比率稱為命中率，而不命中次數(shù)與訪存總次數(shù)的比率稱為不命中率。顯然，不命中率 = 1 - 命中率。命中時的訪問時間 (包括確定是否命中的時間)稱為命中時間，不命中時，將主存塊替換入高速緩存并提供給中央處理器所需的時間稱為不命中損耗。不命中時的訪存時間是命中時間加上不命中損耗。命中率是高速緩存性能的一個重要指標(biāo)，它不僅依賴于硬件實現(xiàn) ，而且與應(yīng)用程序有關(guān)。但是，命中率是與硬件速度無關(guān)的參數(shù)，從而不能單獨用于高速緩存的性能評估。較好的標(biāo)準(zhǔn) 是平均訪存時間：

平均訪存時間 = 命中時間 不命中損耗 不命中率

平均訪存時間的單位可以是絕對的(如25 ns)，也可以是相對的(如2個時鐘周期)。盡管把塊變大有助于提高命中率，但同時也增加了不命中時的傳送時間，所以塊的大小應(yīng)有利于縮小平均訪存時間。

本詞條內(nèi)容貢獻(xiàn)者為:

王慧維 - 副研究員 - 西南大學(xué)