基本介紹
- 中文名：塊替換策略
- 外文名：block replacement strategy
- 學科：計算機組成原理
- 目的：獲得最高命中率
- 策略：隨機和最近最少使用
- 有關術語：高速快取
簡介,替換算法,塊映射策略,高速緩衝存儲器,命中率,
簡介
在高速緩衝存儲器（Cache）中，塊是指Cache存儲空間分為多個大小相同的存儲空間，是基本的 Cache 存儲單位。一個 Cache 塊能夠存儲若干位元組的數據。與主存空間中頁相對應。Cache工作原理要求它儘量保存最新數據，當從主存向Cache傳送一個新塊，而Cache中可用位置已被占滿時，就會產生Cache替換的問題。塊替換策略是指將Cache中最少使用的塊替換出去，使得訪問的頁不在Cache中在的次數為最少，即主要目標獲得最高的命中率。塊替換策略與塊映射策略密切相關。
替換算法
最不經常使用算法
LFU（Least Frequently Used，最不經常使用）算法將一段時間內被訪問次數最少的那個塊替換出去。每塊設定一個計數器，從0開始計數，每訪問一次，被訪塊的計數器就增1。當需要替換時，將計數值最小的塊換出，同時將所有塊的計數器都清零。這種算法將計數周期限定在對這些特定塊兩次替換之間的間隔時間內，不能嚴格反映近期訪問情況，新調入的塊很容易被替換出去。
最近最少使用算法
最近最少使用(Least Recently Used, LRU )替換策略能夠依據Cache塊的使用情況，選擇離最近時間點最近而最少被使用的Cache 塊進行替換這種策略較好地體現程式局部性而使得系統 Cache 丟失率較小。這種方法實現方法眾多有計數器法、暫存器棧法及硬體邏輯比較對法，其中計數器法實現 LRU 替換策略最為簡單，因此這種替換策略得到了廣泛的使用，現代多核處理器依然沿用了這種替換策略。這種算法保護了剛調入Cache的新數據塊，具有較高的命中率。LRU算法不能肯定調出去的塊近期不會再被使用，所以這種替換算法不能算作最合理、最優秀的算法。但是研究表明，採用這種算法可使Cache的命中率達到90%左右。
隨機替換算法
最簡單的替換算法是隨機替換。隨機替換算法完全不管Cache的情況，簡單地根據一個隨機數選擇一塊替換出去。隨機替換算法在硬體上容易實現，且速度也比前兩種算法快。缺點則是降低了命中率和Cache工作效率。Cache命中率除了和替換算法有關外，還與Cache的容量及塊的大小有關。
先進先出算法
先進先出策略(FIFO)：最先替換進入 Cache 的塊將最先被替換出。這就導致被多次命中的塊很可能是最先調入 Cache 的塊，而這個塊將被優先替換，不符合局部性規律。
塊映射策略
Cache的容量很小，它保存的內容只是主存內容的一個子集，且Cache與主存的數據交換是以塊為單位的。為了把信息放到Cache中，必須套用某種函式把主存地址定位到Cache中，這稱為地址映射，或塊映射。
當需要將來自記憶體的新數據塊裝入高速快取時，由塊映射策略決定它的存放位置。根據塊在高速快取內的位置，塊映射策略可分成如3類：
直接映射，每個塊在高速快取中只能有1個位置。該位置通常由求模運算得到，即：高速快取內塊號=塊地址(mod 高速快取中塊數)。
全相聯映射，塊可以放在高速快取中的任意位置。
組相聯映射，高速快取分為若干個組，塊先映射至組，在組中的位置任意。塊向組的映射通常也採用取模運算。塊地址中對應於組號的若干位稱為索引。若組中有n 塊，則稱高速快取是n路組相聯的。
高速快取對每個塊都設立1 個標誌域，其中包括塊地址和該地址是否有效的信息。為了實現快速訪問，在相聯映射型高速快取中，總是同時查找所有的標誌。
高速緩衝存儲器
高速緩衝存儲器（Cache）位於中央處理器與主存儲器之間，對程式設計師透明的一種高速小容量存儲器。高速緩衝存儲器簡稱高速快取。它是存儲器層次結構的最頂層，其下層是容量相對較大和訪問時間較長的主存儲器。在配備有高速快取的計算機中，每次訪問存儲器都先訪問高速快取，若欲訪問的數據在高速快取中，則訪問到此為止；否則，再訪問主存儲器，並把有關數據取入高速快取。這樣，如果大部分針對高速快取的訪問都能成功，則在保持主存儲器容量不變的前提下，訪存速度可接近高速快取的存取速度。高速快取的設定是所有現代計算機系統發揮高性能的重要因素之一。高速快取的工作機制體現了局部性原則。所謂局部性，是指程訪問代碼和數據的不均勻性，它包括：時間局部性：如果某位置已被訪問，則該位置很可能在短時間內還要再被訪問；空間局部性：如果某位置已被訪問，則其鄰近位置很可能還要被訪問。因此， 只要程式有較好的訪存局部性，高速快取就能發揮作用。
命中率
高速快取的組織及對高速快取的訪問都是以行或塊為單位的，通常1行包括1個或多個字。行也是高速快取與主存儲器交換數據的最小單位。訪存時，若能在高速快取中找到所需數據，稱為高速快取命中，否則就是不命中。命中次數與訪存總次數的比率稱為命中率，而不命中次數與訪存總次數的比率稱為不命中率。顯然，不命中率 = 1 - 命中率。命中時的訪問時間 (包括確定是否命中的時間)稱為命中時間，不命中時，將主存塊替換入高速快取並提供給中央處理器所需的時間稱為不命中損耗。不命中時的訪存時間是命中時間加上不命中損耗。命中率是高速快取性能的一個重要指標，它不僅依賴於硬體實現 ，而且與應用程式有關。但是，命中率是與硬體速度無關的參數，從而不能單獨用於高速快取的性能評估。較好的標準 是平均訪存時間：
平均訪存時間 = 命中時間 
不命中損耗 
不命中率
平均訪存時間的單位可以是絕對的(如25 ns)，也可以是相對的(如2個時鐘周期)。儘管把塊變大有助於提高命中率，但同時也增加了不命中時的傳送時間，所以塊的大小應有利於縮小平均訪存時間。
