課程來源：華中科技大學(xué) 計(jì)算機(jī)組成原理公開課

計(jì)算機(jī)各個(gè)部件的速度存在差異，慢速的內(nèi)存會讓快速的CPU性能嚴(yán)重下降胃碾。緩存就是用來解決這種類型的問題易稠。根據(jù)局部性原理，程序下一次訪問的地址在上一次訪問地址的旁邊吟秩。把訪問地址附近的數(shù)據(jù)裝入緩存咱扣，下一次訪問時(shí)，CPU大概率能從緩存中找到數(shù)據(jù)涵防，速度大大提升闹伪。

Cache的工作過程：如果CPU訪問的數(shù)據(jù)在Cache中，則從Cache中讀取數(shù)據(jù)壮池。如果CPU訪問的數(shù)據(jù)不在Cache中偏瓤；如果CPU訪問的數(shù)據(jù)不在Cache中，則從內(nèi)存中讀取數(shù)據(jù)椰憋，然后在把內(nèi)存相關(guān)塊區(qū)域復(fù)制到緩存中厅克。

這里有一些問題：如何判斷數(shù)據(jù)是否在Cache中？ 如何判斷數(shù)據(jù)是否有效橙依？這就和Cache地址映射機(jī)制有關(guān)证舟。

首先要把Cache分行硕旗，內(nèi)存分塊；一行的容量等于一塊的容量褪储，這樣就可以把內(nèi)存中的某一塊調(diào)入Cache的某一行卵渴。再把內(nèi)存地址分為兩個(gè)部分：塊地址+塊內(nèi)偏移，或者進(jìn)一步劃分為：tag+index+offset鲤竹。tag判斷數(shù)據(jù)是否在Cache中浪读，index表示在Cache中哪一行讀寫數(shù)據(jù)。Offset是一行或一塊內(nèi)的地址辛藻。

Cache的結(jié)構(gòu)：CPU地址總線一部分連接到相聯(lián)存儲器碘橘，用來判斷地址是否在Cache中。相聯(lián)存儲器剝離地址作為key吱肌，以key為關(guān)鍵字全局硬件并發(fā)比較痘拆。

Cache 地址映射與變換方法

內(nèi)存數(shù)據(jù)如何遷至Cache才能實(shí)現(xiàn)快速查找？有常見的三種映射方式：全相連氮墨、直接相連纺蛆、組相連。這三種方式都要把內(nèi)存分塊规揪、Cache分行桥氏。

全相連映射：內(nèi)存地址表示為塊號+塊內(nèi)地址，映射算法是內(nèi)存的數(shù)據(jù)塊可映射到Cache任意行猛铅，同時(shí)將該數(shù)據(jù)塊地址對應(yīng)行的標(biāo)記存儲體中保存字支。特點(diǎn)：Cache利用率高、塊沖突率低奸忽、淘汰算法復(fù)雜堕伪。應(yīng)用場合：小容量Cache。

直接映射：內(nèi)存分塊后再按照Cache行數(shù)分區(qū)栗菜，內(nèi)存地址表示為：區(qū)號+區(qū)內(nèi)塊號+塊內(nèi)地址欠雌，內(nèi)存的數(shù)據(jù)映射到Cache的特定行。特點(diǎn)：Cache利用率低疙筹、塊沖突率高桨昙、淘汰算法簡單，應(yīng)用場合：大容量Cache腌歉。

組相連映射：Cache分成k組蛙酪，內(nèi)存每k塊分成一組。內(nèi)存地址：內(nèi)存組號+Cache組號+塊內(nèi)地址翘盖。它既有直接映射的特點(diǎn)也有全相連的特點(diǎn)桂塞。

程序運(yùn)行一段時(shí)間后，Cache存儲控件被占滿馍驯，當(dāng)再有新數(shù)據(jù)要調(diào)入時(shí)阁危，就需要通過某種機(jī)制決定替換的對象玛痊。有幾種常見的替換算法：先進(jìn)先出法、最不經(jīng)常使用法狂打、近期最少使用法擂煞、隨機(jī)替換法。

先進(jìn)先出算法：每行Cache有一個(gè)計(jì)數(shù)器趴乡，調(diào)入時(shí)置0对省，每次加1。Cache裝滿后計(jì)數(shù)器最大的行被替換晾捏。

最不經(jīng)常使用：每行Cache有一個(gè)計(jì)數(shù)器蒿涎，調(diào)入時(shí)置0，命中此行計(jì)數(shù)器加1惦辛。Cache裝滿后計(jì)數(shù)器最小的行被替換劳秋。

近期最少使用法：每行Cache有一個(gè)計(jì)數(shù)器，調(diào)入時(shí)置0胖齐，每次加1玻淑，命中此行計(jì)數(shù)器置0。Cache裝滿后計(jì)數(shù)器最大的行被替換呀伙。