2024年-Cache的原理與地址映像機制

Cache原理

與地址映像機制1

2重點 Cache的工作原理 Cache的基本結構

地址映像機制

替換策略22024/5/141.問題的提出避免CPU“空等”現(xiàn)象CPU和主存（DRAM）的速度差異程序訪問的局部性原理一、Cache的工作原理空間局部性時間局部性32024/5/141.問題的提出避免CPU“空等”現(xiàn)象CPU和主存（DRAM）的速度差異緩存CPU主存容量小速度高容量大速度低一、Cache的工作原理字塊42024/5/14主存塊

調入

緩存主存塊與緩存塊建立

了對應關系標記記錄與某緩存塊建立了對應關系的主存塊號命中未命中主存塊與緩存塊未建立對應關系主存塊

未調入

緩存2.

Cache的命中率52024/5/14(1)主存和緩存的編址主存和緩存按塊存儲塊的大小相同B

為塊長~~~~……主存塊號主存儲器012m－1字塊0字塊1字塊M－1主存塊號塊內地址m位b位n位M塊B個字緩存塊號塊內地址c位b位C塊B個字~~~~……字塊0字塊1字塊C－1012c－1標記Cache緩存塊號62024/5/14

命中率命中率：CPU訪問cache的次數(shù)占總訪問次數(shù)的比例。設NC表示cache完成存取的總次數(shù)，NM表示主存完成存取的總次數(shù)，h為命中率，則有：h=NC/（NC+NM）若tC表示命中時的cache訪問時間，tm表示未命中時的主存訪問時間，則cache/主存系統(tǒng)的平均訪問時間ta為：

ta=htc+（1-h）tm目標：以較小的硬件代價使cache/主存系統(tǒng)的平均訪問時間ta越接近tc越好，用e表示訪問效率表示。設tm/tc=r則有：e=tc/ta=1/(r+(1-r)h)命中率h越接近于1越好，r值以5～10為宜，不宜太大。72024/5/143.Cache的讀操作

訪問Cache取出信息送CPU

訪問主存取出信息送CPU將新的主存塊調入Cache中執(zhí)行替換算法騰出空位

結束命中？Cache滿？CPU發(fā)出訪問地址

開始是否是否82024/5/144.Cache的基本結構Cache替換機構Cache存儲體主存Cache地址映像變換機構由CPU完成92024/5/14二、地址映射機制主存和緩存的編址~~~~……主存塊號主存儲器012m－1字塊0字塊1字塊M－1主存塊號塊內地址m位b位n位M塊B個字緩存塊號塊內地址c位b位C塊B個字~~~~……字塊0字塊1字塊C－1012c－1標記Cache緩存塊號102024/5/14二、地址映像機制地址映像機制AC=f(AM)常用的地址映像方式直接映像方式全相聯(lián)映像方式組相聯(lián)映像方式112024/5/14二、地址映像機制1.直接相聯(lián)

字塊2m－1

字塊2c+1

字塊2c+1－1

字塊2c

+1

字塊2c

字塊2c－1

字塊1

字塊0………主存儲體

字塊1

標記

字塊0

標記字塊2c－1標記Cache存儲體t位012c－1…

字塊字塊地址

主存字塊標記t

位c

位b

位主存地址

比較器（t位）=≠不命中有效位=1？*m位Cache內地址否是命中

字塊2c+1

字塊2c

字塊0

字塊0122024/5/14檢索過程：根據內存地址中的t位標記與cache的標記位相比較，然后將塊地址與cache的塊地址相比較，判斷是否命中。特點：硬件實現(xiàn)簡單，成本低。但每個主存塊只有一個固定的行可以存放。當cache的行數(shù)較少時發(fā)生沖突的可能性很大，頻繁的置換會使cache的效率下降。直接映射方式一般用于大容量的cache中。

132024/5/14二、地址映像機制1.直接相聯(lián)特點：主存地址塊映射到Cache的固定塊

j＝imod(M)實現(xiàn)簡單空間利用率低，沖突概率高142024/5/14二、地址映像機制2.全相聯(lián)字塊2m－1字塊2c－1字塊1

字塊0……字塊2c－1字塊1字塊0…標記標記標記主存字塊標記

字塊內地址主存地址m=t+c

位b位m

=

t+cCache存儲器主存儲器

字塊0152024/5/14全相聯(lián)映射方式的檢索過程：CPU發(fā)出內存地址的塊號部分（s位）與cache中所有行中的標記部分同時比較，若某行的標記與要訪問的塊號相同，命中，則再根據塊內地址（b位）從該行中讀取相應字；否則，未命中，則按內存地址從主存中讀取一個字。優(yōu)點:靈活，cache可以得到充分利用。但當行數(shù)較多時要實現(xiàn)所有行中的標記部分同時參與比較，電路實現(xiàn)困難。

全相聯(lián)映射方式一般用于小容量cache。162024/5/14二、地址映像機制2.全相聯(lián)特點：主存地址塊映射到Cache的任意塊空間利用率高，沖突概率低實現(xiàn)復雜

172024/5/14二、地址映像機制3.組相聯(lián)字塊2m－1字塊2c-r+1

字塊2c-r+1

字塊2c-r字塊2c-r

－

字塊1

字塊0………

字塊3標記

字塊1標記字塊2c－1標記

字塊2標記

字塊0標記字塊2c－2標記…………

字塊內地址組地址主存字塊標記s=t+r

位q=

c－r

位b

位組012c-r－1主存地址Cache主存儲器m

位共Q

組，每組內兩塊（r=1)1

字塊0

字塊1

字塊0

字塊2c-r

字塊2c-r+1182024/5/14組相聯(lián)映射192024/5/14檢索過程：根據地址中的組地址找到cache的相應組，然后將該組的標記部分與內存地址的塊號同時比較，判斷是否命中。特點：組內有一定的靈活性，而且因組內行數(shù)的減少，比較的硬件電路比全相聯(lián)方式簡單些。組相聯(lián)映射的每組的行數(shù)v一般取值較小，典型值為2，4，8，16。為強調比較器的規(guī)模和存放的靈活性，常稱組相聯(lián)為v路組相聯(lián)。組相聯(lián)映射202024/5/14例如：設有一個cache的容量為2K字，每個塊為16字，求

(1)該cache可容納多少個塊？

(2)如果主存的容量是256K字，則有多少個塊？

(3)主存的字地址有多少位？Cache字地址有多少位？

(4)在直接映象方式下，主存中的第i塊映象到cache中哪一個塊中？

212024/5/14★先進先出（FIFO）算法把最先調入cache的字塊替換出去優(yōu)點：實現(xiàn)容易、開銷小缺點：可能把一些常用的程序，如子程序、循環(huán)程序塊，作為最早進入Cache塊，替換出去替換策略222024/5/14先進先出替換策略232024/5/14★近期最少使用(LRU)算法

LRU算法將近期內長久未被訪問過的行換出。每行也設置一個計數(shù)器，cache每命中一次，命中行計數(shù)器清零，其它各行計數(shù)器