計算機組成原理-課件cache

3.4高速存儲器單機系統(tǒng)中，主存與CPU速度的不匹配是高速計算的瓶頸。提高存儲系統(tǒng)性能的主要措施采用更高速的主存和加長存儲器的字長采用并行操作的雙端口存儲器采用多模塊交叉存儲器采用高速緩沖存儲器P97應用：虛擬存儲器中存放段表、頁表和快表高速緩存中存入cache行地址相聯(lián)存儲器普通存儲器是以地址為檢索項來進行存取。相聯(lián)存儲器（CAM）的基本原理可將某一存儲項的內(nèi)容作為檢索項來存取和檢索信息的存儲器。物理地址職工號姓名出生年月工資數(shù)N800張明1940.22000N+1540王芳1960.11200N+2920李萍1942.51500N+3750趙虹1945.21400普通存儲器的檢索項相聯(lián)存儲器的檢索項3.5高速緩沖存儲器工作原理基于程序局部性原理短時間內(nèi)，CPU對存儲器的訪問總是局限在某個較小區(qū)域內(nèi)cache與主存分成大小相同的塊當CPU讀取一個字時，便發(fā)出此字的內(nèi)存地址到cache和主存。控制邏輯判斷此字當前是否在cache中若在，立即傳送給CPU若不在，則把此字從主存讀到CPU，同時，把含有該字的數(shù)據(jù)塊從主存送cache。CPU相聯(lián)存儲器主存LRU管理邏輯cacheDBABCache的命中率Cache始終保存主存最活躍的局部區(qū)域的副本，使CPU的訪存操作大多數(shù)針對Cache，提高整個程序的執(zhí)行速度。命中率，越接近1越好。Nc——Cache完成存取的總次數(shù)Nm——主存完成存取的總次數(shù)h——命中率系統(tǒng)平均訪問時間越接近cache訪問時間越好。tc——命中時，cache訪問時間tm——未命中時，主存訪問時間ta——系統(tǒng)平均訪問時間Cache的命中率系統(tǒng)訪問效率r——Tm/Tc，比值不宜太大，以5~10較好。e——系統(tǒng)訪問效率【例5】CPU執(zhí)行一段程序時，cache完成存取的次數(shù)為1900次，主存完成存取的次數(shù)為100次，已知cache存取周期為50ns，主存存取周期為250ns，求cache/主存系統(tǒng)的效率和平均訪問時間。h=Nc/(Nc+Nm)=1900/(1900+100)=0.95r=tm/tc=250ns/50ns=5e=1/(r+(1-r)h)=1/(5+(1-5)×0.95)=83.3%ta=htc+(1-h)tm=tc/e=50ns/0.833=60ns主存與Cache的地址映射地址映射應用某種函數(shù)，將主存地址映像到Cache中定位，從而可以將內(nèi)存地址變換成Cache地址，完成CPU的訪問。全相聯(lián)映射直接映射組相聯(lián)映射地址映射過程對程序員來說是完全透明的由硬件控制實現(xiàn)，程序員不需要編程介入全相聯(lián)映射主存中任一塊都可以映射到Cache中任一行上。例：內(nèi)存容量64KB，分為256塊，每塊256B，Cache容量2KB，分為8行，每行也是256B。優(yōu)點：比較靈活Cache利用率高塊沖突概率低使用淘汰算法缺點：Cache標記太長比較電路難于設(shè)計和實現(xiàn)M255…7塊…1塊0塊塊號…塊號塊號7行…1行0行Cache標記8位全相聯(lián)映射檢索過程塊號塊內(nèi)地址內(nèi)存地址8位8位7行塊號……2行塊號1行塊號0行塊號標記塊內(nèi)容量Cache比較命中0塊1塊2塊…L-1塊L塊L+1塊…255M未命中8位直接映射主存分區(qū)，每區(qū)內(nèi)塊數(shù)與Cahce內(nèi)行數(shù)相同。主存中每一個塊只能映射到Cache中某一個固定的行。i=jmodmi：Cache的行號j：主存的塊號m：Cache的總行數(shù)例：0=8mod8（主存第8塊映像到Cache的第0行）31區(qū)255…249248…15塊…9塊8塊7塊…1塊0塊M0區(qū)1區(qū)…區(qū)號…區(qū)號區(qū)號7行…1行0行Cache標識5位不靈活塊沖突概率高特點地址變換速度快無需替換算法直接映射檢索過程內(nèi)存地址區(qū)號區(qū)內(nèi)塊號塊內(nèi)地址5位3位8位7行區(qū)號……2行區(qū)號1行區(qū)號0行區(qū)號標記塊內(nèi)容量Cache7塊…1塊0塊…7塊…1塊0塊7塊…1塊0塊M0區(qū)1區(qū)31區(qū)…比較命中未命中組相聯(lián)映射主存分區(qū)，Cache分組，主存每個區(qū)的塊數(shù)與Cache的分組數(shù)相同。組間采用直接映射組內(nèi)采用全相聯(lián)映射特點：是全相聯(lián)映像與直接映像的折衷。較直接映像靈活較全相聯(lián)映像標記位短，速度快255254253252…7塊6塊5塊4塊3塊2塊1塊0塊M0區(qū)1區(qū)63區(qū)…區(qū)號區(qū)號區(qū)號區(qū)號區(qū)號1行0行1行0行Cache…1行…0組1組3組0行標識6位區(qū)號組相聯(lián)映射檢索過程區(qū)號區(qū)內(nèi)塊號Cache組號塊內(nèi)地址區(qū)號3塊2塊1塊0塊…3塊2塊1塊0塊3塊2塊1塊0塊區(qū)號區(qū)號區(qū)號區(qū)號1行0行1行0行CacheM0區(qū)1區(qū)63區(qū)…區(qū)號…1行…0組1組3組0行比較命中未命中6位2位8位標識6位塊內(nèi)容量Cache地址映射練習一個四路組相聯(lián)映射的Cache，由64行構(gòu)成。主存包含4096個存儲塊，每塊由128字組成。一個主存地址有多少位？主存地址格式中區(qū)號、組號和塊內(nèi)地址位數(shù)？1)19位，4096*128=2192)區(qū)號8位，組號4位，塊內(nèi)地址7位15組區(qū)號4095…40814080…31塊…17塊16塊15塊…1塊0塊區(qū)號區(qū)號區(qū)號區(qū)號3行2行1行0行CacheM0區(qū)1區(qū)255區(qū)…區(qū)號…63行…0組62行區(qū)號區(qū)號61行60行高速緩存替換算法替換算法：當Cache中的可用位置已被占滿時，需要利用某種算法，將舊的行用新的行來代替。最不經(jīng)常使用（LFU）算法將一段時間內(nèi)使用次數(shù)最少的行淘汰。近期最少使用（LRU）算法最近一段時間，使用機會最少的行被淘汰。隨機算法簡單地根據(jù)一個隨機數(shù)，指定需要替換出去的舊塊。Cache的讀寫策略讀操作：CPU發(fā)出讀命令后若Cache命中，直接對Cache進行讀操作未命中，訪問內(nèi)存，同時將內(nèi)存信息調(diào)入Cache若Cache已滿，采用替換算法，換掉原來的某塊寫操作：CPU發(fā)出寫命令后寫回法:先暫時寫入Cache，并用標記注明，直到該塊從Cache中替換出來時，才一次寫入內(nèi)存。全寫法:同時寫入內(nèi)存和Cache。寫一次法:是寫回法與全寫法的結(jié)合?；就趯懟胤ǎ谝淮螌懨袝r要同時寫入主存。3.6虛擬存儲器虛擬存儲系統(tǒng)建立在內(nèi)存——外存層次上的需要輔助硬軟件的支持將內(nèi)存與外存空間統(tǒng)一編址形成一個龐大的存儲空間用戶可在這個虛擬的龐大空間里編程，而不必考慮實際內(nèi)存的大小虛擬地址（邏輯地址）：用戶編程時使用的地址，在程序真正執(zhí)行時，在輔助軟硬件支持下，虛擬地址將映射為內(nèi)存的物理地址。實際地址（物理地址）：內(nèi)存的實際的地址編號。頁表頁式虛擬存儲器內(nèi)存空間和虛存空間都劃分成若干個大小相等的頁。設(shè)置地址變換機構(gòu)——頁表。頁表由多個頁表項構(gòu)成。每個頁表項包含實頁號、裝入位等。實頁號頁內(nèi)地址虛頁號頁內(nèi)地址虛地址實地址頁表項地址1裝入位1：該頁在內(nèi)存0：不在內(nèi)存，調(diào)入頁表起始地址頁表基址寄存器頁式虛擬存儲器頁表的改進——快表快速小容量的存儲器保存當前最常用的頁表項是慢表的副本頁表虛擬存儲的特點頁大小相等，地址變換簡單存在頁零頭頁的劃分不具有邏輯性，程序處理復雜段式虛擬存儲器內(nèi)存空間按程序邏輯結(jié)構(gòu)分段，段長度各異。地址變換機構(gòu)——段表。段表包括多個段表項。每個段表項包含段號、段起點、段長、裝入位等。2K1202441K1919233K161202011K110000段長裝入位段起點段號段表段0段1段2段3段41K2K3K1K2K程序空間段0段4段2內(nèi)存實空間1000202440716120919210215段3段式虛擬存儲器段表起始地址段表基址寄存器段號段內(nèi)地址段表虛地址段表項地址實地址內(nèi)存地址+優(yōu)點：段的分界與程序邏輯性相符，便于程序管理。缺點：段長不一，主存空間分配麻煩，存在段間零頭。段頁式虛擬存儲器程序按邏輯結(jié)構(gòu)先分段，段內(nèi)再劃分為若干大小相等的頁，內(nèi)存也劃分為同樣大小的頁。地址變換機構(gòu)——段表、頁表段表：每個程序一個頁表：每段一個優(yōu)點兼?zhèn)漤撌胶投问较到y(tǒng)的優(yōu)點缺點地址映射過程中需要多次查表多道程序的段頁式地址變換SASBSC基址寄存器邏輯地址12dC基號段號頁號頁內(nèi)地址+b程序C段表SA+0SA+1SA+2SA+3程序A段表SC+0SC+1SC+2…ca+b+0b+1b+210頁表a段b段c段a+0a+1c+0c+178物理地址10物理頁號d頁內(nèi)地址虛擬存儲器的頁面替換算法當產(chǎn)生頁面失效時，需要進行頁面替換，區(qū)別于Cache的替換至少要訪問外存一次，速度慢。由操作系統(tǒng)軟件實現(xiàn)頁面替換選擇余地大，屬于一個進程的頁面都可替換。虛擬存儲器中的替換策略LRU算法LFU算法FIFO算法虛擬存儲器的頁面替換算法【例7】假設(shè)主存只有a,b,c三個頁框，組成a進c出的FIFO隊列，進程訪問頁面的序列是0，1，2，4，2，3，0，2，1，3，2號。若采用①FIFO算法，②FIFO算法+LRU算法，用列表法分別求兩種替換策略情況下的命中率。命中

命中

命中

120