上西安交通大學本科生課程：計算機系統結構

計算機系統結構第五章一

《存儲體系》1

鄭慶華教授

西安交大計算機系

2009年5月

E-maiI:qhzheng@鄭慶華教授

上西安交通大學本科生課程：計算機系統結構

本章要點

■存儲系統的概念及原理

■高速緩存的概念及原理

■主存的原理

■虛擬存儲器的概念及原理

E-mail:qhzheng@mail.xjtu.鄭慶華教授

親西安交通大學本科生課程：計算機系統結構

5.1存儲系統的原理

5.1.1概念

由多個不同性能的存儲器組成的有機的一體化的存

儲體。這個存儲體系是通過硬件、軟件或軟硬件相結合

的方法形成的一體化存儲系統。具有以下主要特點：

■有多級不同的存儲器組成，一般為Cache--RAM-Disk

■不同的存儲體有不同的性能：容量、價格和速度。

■存儲體對應用程序員透明，對系統結構設計者不透明。

■就存儲體系的總體性能而言，其存儲容量相當于大

容量的存儲器，而其價格則接近于最廉價的存儲器，

速度則相當于最高速的存儲器。

E-mail:qhzheng(a>鄭慶華教授

上西安交通大學本科生課程：計算機系統結構

層次化存儲系統的基本特征

從用戶的視角看

T=min(T;,乃,…Tn)IS=max(S/,S2,,C=max(Ci,C2,...Cn)

E-mail:qhzheng@mail.xjtu.鄭慶華教授

親西安交通大學本科生課程：計算機系統結構

5.1.3存儲系統的一般組成

■存儲系統=(Cache-RAM)+(RAM?Disk)。

注：(Cache-RAM)的設置目標是提高速度，對操作

系統設計者透明；

■(RAM?Disk)的目標是擴充容量，對操作系統設計者

不透明。

Cache的速度：T=xns-xxns

■RAM的速度：T=xxns~xxxns,一般而言

Tc41/5~10TRAM

Disk的存取速度TDISK=xms-xxms

E-mail:qhzheng@鄭慶華教授

親西安交通大學本科生課程：計算機系統結構

5.1.4DesignprincipleofHierarchyMemorySystem

?BasicPrinciples:localityandcost/performanceof

memorytechnology

?Theprincipleoflocality:Programstendtoreusedata

andinstructionstheyhaveusedrecently.

?Aruleofthumb:aprogramspends80%ofits

executiontimeinonly20%ofthecode.

E-mail:qhzheng@鄭慶華教授

上西安交通大學本科生課程：計算機系統結構

Locality

?Animplicationoflocalityisthatwecanpredictwjth

reasonableaccuracywhatinstructionsanddataa

programwilluseinthenearfuturebasedonits

accessesintherecentpast.

?Temporallocality------Recentlyaccesseditemsare

likelytobeaccessedinthenearfuture.

?Spatiallocality------Itemswhoseaddressesarenear

oneanothertendtobereferencedclosetogetherin

time.

E-mail:qhzheng@鄭慶華教授

充西安交通大學本科生課程：計算機系統結構

Designresolution:

?Theprincipleoflocality+ThesmallerMemoryisfaster

ledtothehierarchybasedonmemoriesofdifferent

speedsandsizes.

LCPUYUI

弟I

容量：XKB64?512KB128?4096MBXXXGB

速度：5ns10ns50?100ns5ms

E-mail:qhzheng@mail.xjtu.鄭慶華教授

上西安交通大學本科生課程：計算機系統結構

?Theimportanceofmemoryhierarchyhasincreased

withadvancesinperformanceofprocessors.

W$2

H

621

T7

親西安交通大學本科生課程：計算機系統結構

TypicalLevelsinaHierarchicalMemory

CapacHyAccesslatencyCostperGB

1005BnsZk$Millions

10SKBafewns/c^\$1Q0SKS

MBs10sns/Cache2\$10sKs

100sMB100snsSpeed/Main\$1ooos

gap/\

10sGB10sms/Secondary\$10s

TBsmin+/Tertiary

Namesandkeycharacteristicsoflevelsinamemoryhierarchy.

E-mail:qhzheng@maiI.鄭慶華教授

上西安交通大學本科生課程：計算機系統結構

TheNeedforaMemoryHierarchy

ThewideningspeedgapbetweenCPUandmainrr|g|^fy

?Processoroperationstakeoftheorderof1ns

?Memoryaccessrequires10soreven100sofns

Memorybandwidthlimitstheinstructionexecutionrate

?Eachinstructionexecutedinvolvesatleastonememory

access

?Hence,afewto100sofMIPSisthebestthatcanbe

achieved

?AfastbuffermemorycanhelpbridgetheCPU-memorygap

?Thefastestmemoriesareexpensiveandthusnotverylarge

?Asecond(third?)intermediatecachelevelisthusoftenused

E-mail:qhzheng@mail.xjtu.鄭慶華教授

上西安交通大學本科生課程：計算機系統結構

?Thelevelsofthehierarchyusuallysubsetone

another,alldatainonelevelisalsofoundinthe

levelbelow,andalldatainthatlowerlevelis

foundintheonebelowit,andsoonuntilwe

reachthebottomofthehierarchy.

?Eachlevelmapsaddressesfromalargermemory

toasmallerbutfastermemoryhigherinthe

hierarchy.Atthesametimeofaddressmapping,

addresscheckingandprotectionschemesfor

scrutinizingaddressaretakenplacetoo.

E-mail:qhzheng@鄭慶華教授

■

充西安交通大學本科生課程：計算機系統結構

TemporallocalitySpatiallocality|

Addressmapping9-instruction

programloop

(many-to-on/KI

—

一一

—

——

■

CacheCacheline/block

memory(unitoftransfer

一

betweenmainand

一-)

Fig.AssumingnoconflictinMain—

addressmapping,thecachewillmemory—

holdasmallprogramloopinits

entirety,leadingtofastexecution.

E-mail:qhzheng@m鄭慶華教授

親西安交通大學本科生課程：計算機系統結構

Desktop,Drawer,andFileCabinetAnalogy

Fig.Itemsonadesktop(register)orinadrawer(cache)aremore

readilyaccessiblethanthoseinafilecabinet(mainmemory).

E-mail:qhzheng@mail.xjtu.鄭慶華教授

西安交通大學本科生課程：計算機系統結構

TemporalandSpatialLocalities

AddressesFromPeterDenning'sCACMpaper,

July2005(Vol.48,No.7,pp.19-24)

Temporal:

Accessestothe

sameaddress

aretypically

clusteredintime

Spatial:

Whenalocation

isaccessed,

nearbylocations

tendtobe

accessedalsoTime

鄭慶華教授

親西安交通大學本科生課程：計算機系統結構

5.1.5存儲系統性能的三個重要參數

----容量S、速度T以及價格C

.

■①存儲容量s

目標和要求：使存儲體系的存儲容量接近Max(S1,

S2),并對M2存儲器進行編址，對于Ml存儲器可以

不編址，或僅在系統內部編址。

編址要求：對程序員提供盡可能大的地址空間，而且

提供RandomAccess訪問方式。

E-mail:qhzheng@鄭慶華教授

上西安交通大學本科生課程：計算機系統結構

■舉例而言：

Ex:對Cache-RAM,僅對RAM編址，線性地址方式。■

RAM-Disk虛擬存儲（VM）而言，采用Linear線性地址方式。

■②單位容量的平均價格C

C?和5"邑

~51+S2

當S2?S1時，c?c2

E-mail:qhzheng@mail.xjtu.鄭慶華教授

上西安交通大學本科生課程：計算機系統結構

■③存取周期T(又稱存取時間，訪問周期)

T與命中率H的關系非常大。一

命中率H:CPU存取數據或指令碼時，在Mi存儲器中

訪問到的概率。即：H=NI/(NI+N2),其中Ni為在Mi存

儲器中訪問到的次數，N2為在M2中訪問的次數。

整個存儲系統的平均訪問周期T為：

T(MI,M2)=HTI+(1-H)?T2

進一步可以得到存儲系統(Mi,M2)的訪問效率為：

A=A=1=f(H,

THTI+(1-H)T2H+(\-H\T2ITXi

E-mail:qhzheng@鄭慶華教授

親西安交通大學本科生課程：計算機系統結構

?Effectivenessofthememoryhierarchy

CPUeXeCUtiOntime=inStnC0UntxCPIxCCtime

=(CPUclockcycles+memorystallcycles)xCCtime

Memorystallcycles=Instr,countxMemoryreferencesperinstr,x

Missratexmisspenalty

Missrate=cachemisscount/totalCacheaccesstimes

Misspenalty:Costofonecachemiss

Block:theminimumunitofinformationthatcanbepresentin

thecacheornot.

E-mail:qhzheng@鄭慶華教授

上西安交通大學本科生課程：計算機系統結構

本章要點

■存儲系統的概念及原理

■高速緩存的概念及原理

■主存的原理

■虛擬存儲器的概念及原理

■外存、內存(RAM)—高速緩存(Cache)三級存

儲體系的原理

E-mail:qhzheng@mail.xjtu.鄭慶華教授

上西安交通大學本科生課程：計算機系統結構

5.2高速緩沖存儲器Cache

■目的：提高RAM的訪問速度，減少CPU的等待（?B

■結構：

Cache和RAM間的數據交換單位：塊，即一個存

儲周期內可以訪問的字數或數據長度。

E-mail:qhzheng@mail.xjtu.鄭慶華教授

上西安交通大學本科生課程：計算機系統結構

5.2.1Cache的基本工作原理

■①Cache的地址格式：

塊號B塊內地址D主存地址

塊號b塊內地址dCache地址

E-mail:qhzheng@mail.xjtu.鄭慶華教授

上西安交通大學本科生課程：計算機系統結構

■②工作原理

訪存地址

數據一CPU（一個字）

E-mail:qhzheng@mail.xjtu.鄭慶華教授

親西安交通大學本科生課程：計算機系統結構

■③Cache地址映射與變換中的核心問題

a.主存(B,W)—>(b,w)

b.由于主存中的塊和Cache中的塊一樣大小，因此，

兩者具有同樣的W;

c.地址變換算法的考慮要點：

?硬件實現是否容易；

?速度；

?沖突概率小；

?存儲空間的利用率高。

E-mail:qhzheng@mail.xjtu.鄭慶華教授

■西安交通大學本科生課程：計算機系統結構

5.2.2地址變換的幾種方法

■全相聯映象及其變換

a.概念：指主存中的任意一塊都可以映象到Cache中

的任意一塊。

因此這種映射共有CbxMb種可能，其中Cb和Mb

分別為Cache中的塊數和主存中的塊數。

b.Cache地址目錄表及其結構

該表存儲主存塊號和Cache塊號間的對應關系

結構為：

主存塊號BCache塊號b有效位有關目錄表結構

E-mail:qhzheng@鄭慶華教授

西安交通大學本科生課程：計算機系統結構

全相聯的地址映象規則：

1）主存與緩存分成相同大小的數據塊。

2）主存的某一數據塊可以裝入緩存的任意一塊的空間中。

Cache王鄭慶華教授

親西安交通大學本科生課程：計算機系統結構

全相聯映像（續）

E-mail:qhzheng@mail.xjtu.鄭慶華教授

上西安交通大學本科生課程：計算機系統結構

■特點：

?塊的沖突率最小

?Cache的利用率也最高

?但需要一個訪問速度很快，容量為Cb的相聯存儲

器，代價較高。

?在虛擬存儲系統中，一般都采用全相聯映象方

式。原因在于為了支持多任務調度時，CPU可以

快速切換到另一個任務之中。

E-mail:qhzheng@鄭慶華教授

西安交通大學本科生課程：計算機系統結構

全相聯映像（續）

訪問順序

地址

塊分配情況

操作狀態

圖全相聯映象在地址序列下的塊分配情況

E-mail:qhzheng@mail.xjtu.鄭慶華教授

充|西安交通大學本科生課程：計算機系統結構

5.2.3直接映象及其變換

要點：■Cache和RAM仍以塊為單位，但在RAM中將空

間劃分為大小和Cache完全一樣的區，在RAM中,

將區再劃分為若干塊。

■Cache中的塊和RAM中的塊形成一對多的映射

關系，如下：

(B[AO],B[A1],…，B[An])—>b(Cache)

即滿足：b=BModCb其中，b為Cache中的塊號,

B為存儲器塊號，Cb為Cache中總塊數。

■Cache地址變換的實質：

RAM地址：(區號A，塊號B,塊內地址W)

Cache地址：(Cache塊號，塊內地址)

E-mail:qhzheng@鄭慶華教授

親西安交通大學本科生課程：計算機系統結構

直接映象

主存

第。塊

第1塊

cache

???〉第0區

第0塊

第1塊第N-1塊

??????

第N-1塊

<XxxX第(M-1)N塊

第(M-1)N+1塊

X

???第M-1區

第MN-1塊

J

圖cache的直接相聯映象

E-mail:qhzheng@maiI.鄭慶華教授

西安交通大學本科生課程：計算機系統結構

直接映象（續）

區號主存塊號塊內地址主存地址

不相等

比較塊號塊內地址cache地址

塊失效7T

塊表

0匚

按塊號查找…

N-1.

主存區號標志訪問cache

圖3-21直接映象的地址變換方法

塊地址的概念

存儲容量、塊數、塊容量與地址格式中區號、塊號、塊內

地址位數的關系。

E-mail:qhzheng@mail.xjtu.鄭慶華教授

■西安交通大學本科生課程：計算機系統結構

■如何將RAM地址轉換成Cache地址？

■有四種比較結果：―

Casel：區號相等，且tag=L則命中，即CPU從Cache

中獲取數據；

Case2:區號相等，但tag=O,則表示命中但數據無效，

則：RAM讀取^—>Cache,tag:=1

—>CPTT

Case3:區號不等，且tag=O,則表示此塊為空

Case4:區號不等，但tag=l,則表示Cache中原來存放

的那一塊是有效的，為此，要先將此塊寫回

RAM,然后再按Case2進行操作。

E-mail:qhzheng@鄭慶華教授

上西安交通大學本科生課程：計算機系統結構

直接映象（續）

圖直接映象在地址序列下的塊分配情況

Cache大小為8塊，分2個區，每一個區為4塊。

E-mail:qhzheng@mail.xjtu.鄭慶華教授

西安交通大學本科生課程：計算機系統結構

舉例:假設在某個計算機系統中Cache容量為64K字節，數據塊大

小是16個字節，主存容量是4M,地址映象為直接相聯方式。

(1)主存地址多少位？如何分配？

(2)Cache地址多少位？如何分配?

(3)目錄表的格式和容量？

解:

211615430

主存地址格式:

Cache地址格式:

目錄表的格

式：

容量：應與緩存塊數量相同即212=4096

E-mail:qhzheng@mail.xjtu.鄭慶華教授

親西安交通大學本科生課程：計算機系統結構

5.2.4組相聯映象及其變換

■①提出背景：

a.全相聯方式速度較慢，且造價較高,但命中率最高

b.直接相聯方式速度快，但命中率低。為此，提出

一種折中解決方案

■②要點：

a.Cache和RAM的基本單位仍然是塊；

b.Cache和RAM被組織成為大小相等的若干個組;

c.RAM的組一,Cache組間采用直接相聯的方法，

而組內采用全相聯技術。

E-mail:qhzheng@鄭慶華教授

上西安交通大學本科生課程：計算機系統結構

組相聯映像

＞第0區

》第知-1區

y

■要點：組間直接，組內全相聯

E-maiI:qhzheng@鄭慶華教授

親西安交通大學本科生課程：計算機系統結構

組相聯映像（續）

:nail.xjtu.ediiL!!

愛：西安交通大學本科生課程：計算機系統結構

'組相聯映像（續）

■Cache分為2個組，每個組的大小為4個塊

E-maiI:qhzheng@鄭慶華教授

上西安交通大學本科生課程：計算機系統結構

舉例:主存容量為1MB,緩存容量為32KB,每塊為

64個字節，緩存共分128組。

請寫出：

(1)主存與Cache的格式;

(2)相關存儲器的格式與容量

解:

14865o

緩存地址:組號塊號塊內地址

19151487650

主存地址：

相關存儲器的格式:

相關存儲器的容量，應與緩存的塊數相同，即：組數X組內塊數=128X4=512

E-mail:qhzheng@mail.xjtu.鄭慶華教授

親西安交通大學本科生課程：計算機系統結構

■特點：

?Cache中塊的利用率將大幅提高，命中率也將明顯

提高，組相聯方式與全相聯方式相比，實現起來

更容易的多，但Cache的命中率與全相聯映象方式

很接近。因此，這種方式得到較廣泛的應用。

?當每組的塊容量Gb為1時，就成了直接映象方式。

即：1組=1塊

?當組數G=1時，為全相聯方式

?當Gb上升時，沖突概率和Cache的失效率就降低,

但查表速度減慢。

E-mail:qhzheng@鄭慶華教授

系西安交通大學本科生課程：計算機系統結構

5.2.5Cache替換算法及其實現

■①提出的背景：當將主存塊裝入Cache時，有可能

Cache已滿，此時要將Cache中的某塊寫回RAM,

然后再將RAM塊裝入至Cache中。

■直接映象及變換算法，不需要采用替換算法。

■②替換算法概略

a.全相聯映象及變換方式中，替換算法最復雜；

b.組相聯映象及變換，需要從Cache同一組內的幾

個塊中選擇一塊替換。

c.Cache替換算法：有隨機算法，FIFO算法，

LRU、LFU、OPT等幾種方法，但常用的為LFU

和FIFO算法兩種。

E-mail:qhzheng@鄭慶華教授

西安交通大學本科生課程：計算機系統結構

■③方法1:輪換法

這種方法通常應用于組相聯映象及地址變換之tO

具體有以下兩種實現方法：W

a,每塊一個計數器

塊表的數據結構為：（區號E,塊號B，Cache塊號

b,有效位e,計數器）

替換方法：

①剛裝入的塊，其計數器清“0L同組的其它塊則+1。

②需要替換時，將同組中最大計數值的塊作為替換對

象。

E-mail:qhzheng@m鄭慶華教授

親西安交通大學本科生課程：計算機系統結構

b.每組一個計數器

本質上，同組內的所有塊是按順序輪流替換

的。因此，只要為每個組設置一個計數器即可.

計數器的值就是要被替換的塊。

特點：①實現簡單；

②不符合程序的局部性原理

E-mail:qhzheng@mail.xjtu.鄭慶華教授

充西安交通大學本科生課程：計算機系統結構

■④方法2：LRU算法及其實現

a.基本思想：通過在塊表中為每一Cache塊設置一個

計數器，記錄其訪問次數。然后根據計數器的值，

確定被替換的對象。

b.計數器的使用及管理規則：

①被裝入的塊，其對應的Counter為而其它塊的

Counter+1

②命中的塊，其Counterv—0,同組中其它所有計數

器,分以下兩種懵況處理?

Case1：All(Counter<命巾的Counter),貝ICounter+1

Case2:其余的Counter不變

③需要替換時，選擇max(counter)對應的塊，作為替

換對象。

E-mail:qhzheng@鄭慶華教授

桑)西安交通大學本科生課程：計算機系統結構

5.2.6Cache的一致性問題

■①問題的原因：

a.CPU一＞Cache,但沒有寫Memory。此時，若直接4尋

Mem中的數據寫入HD,就出問題。

b.HD—＞1/0處理機一〉RAM,但沒有到Cache,在這種情況

下，若直接訪問Cache中的數據也將出問題。

■②解決的方法

方法1:寫直達法(Write-through)

方法2:寫回法(Write-back)

Write-through:CPU一＞數據一＞(Cache,RAM),從而使兩者一致

Write-Back:CPU—＞數據一＞Cache,當沖突發生時，一次寫回

RAMO

E-mail:qhzheng@鄭慶華教授

上西安交通大學本科生課程：計算機系統結構

■兩種方法的比較。

方法可靠性］通信量復雜性實現代（介

A\ttte-through簡單rzo

Write-Back復雜

低11低1

E-mail:qhzheng@mail.xjtu.鄭慶華教授

親西安交通大學本科生課程：計算機系統結構

5.2.7Cache的性能分析

■主要分析：

a.Cache系統的加速比及其影響參數

b.Cache系統的數據一致性

①Cache系統的加速比

T=H.K+Q-H)1n

1

設Sp=Tm/T=Tm/(HTc+(l-H)yTm=

即Sp=f(H,T-Tm)=f(H,Tm/Tc)

E-mail:qhzheng@mail.xjtu.鄭慶華教授

親西安交通大學本科生課程：計算機系統結構

幾個主要的分析關系

VTIT

2pmax=m1c

2Pmax隨"增長，當H=0.9時，S〃期望達到

10,當"=1,則Sp=7；/7；

0H1

Cache的命中率和

Sp間的關系

命中率和以下因素相關：

H二f（地址流分布,替換算法,Cache的容量,分組的數目

及組內塊數,Cache的預取算法）

E-mail:qhzheng@mail.xjtu.鄭慶華教授

西安交通大學本科生課程：計算機系統結構

②Cache命中率與組數的關系

組數提升，組內塊數就減少，導致H降低。

原因：組間采用直接相聯方式，因此當分組數目提

升，主存中的某一塊可以映象到Cache中的

塊數就將減少，從而使H減少。

E-mail:qhzheng@鄭慶華教授

上西安交通大學本科生課程：計算機系統結構

?地址映象與命中率之間的關系

E-maiI:qhzheng@鄭慶華教授

西安交通大學本科生課程：計算機系統結構

Cache的相聯性與失效率

性2路4路8路

容量\\

LRURandomLRURandomLRURandom

16KB5.2%5.7%4.7%5.3%4.4%5.0%

64KB1.9%2.0%1.5%1.7%1.4%1.5%

256KB1.15%1.17%1.13%1.13%1.12%1.12%

更新策略與命中率（定量分析公式）增力口cache后的

CPU執行時間

一丁MemoryAccesses

TCPU=Inx(CPZ+----------J------------x(l-Hc)xTmzJxTC(LK

n

E-mail:qhzheng@mail.xjtu.鄭慶華教授

例5.1假設Cache的命中時間為1個時鐘周期，失效開銷

為50個時鐘周期，在混合Cache中一次load或store操作訪問

Cache的命中時間都要增加1個時鐘周期（因為混合Cache

只有一個端口，無法同時滿足兩個請求，會導致結構沖

突），根據表5.4所列的失效率，試問指令Cache和數據

Cache容量均為16KB的分離Cache和容量為32KB的混合

Cache相比，哪種Cache的失效率更低？又假設采用寫直達

策略，且有一個寫緩沖器，并且忽略寫緩沖器引起的等

待。請問上述兩種情況下平均訪存時間各是多少？

解:如前所述，約75%的訪存為取指令。

因此，分離Cache的總體失效率為：

(75%X0.64%)+(25%X6.47%)=2.10%

根據表5.4,容量為32KB的混合Cache的失效率略低一

些，只有1.99%。

平均訪存時間公式可以分為指令訪問和數據訪問兩部分：

平均訪存時間=指令所占的百分比X(指令命中時間+指

令失效率X失效開銷)+數據所占的百分比義(數據

命中時間+數據失效率X失效開銷)

所以，兩種結構的平均訪存時間分別為：

平均訪存時間分離=75%X(1+0.64%X50)+25%X(1+6.47%X50)

=(75%X1.32)+(25%X4.325)

=0.990+1.059=2.05

平均訪存時間混合=75%X(1+1.99%X5O)+25%X(1+1+1.99%X5O)

=(75%X1.995)+(25%X2.995)

=1.496+0.749=2.24

因此，盡管分離Cache的實際失效率比混合Cache的高，但其平均訪存

時間反而較低。分離Cache提供了兩個端口，消除了結構沖突。

3.程序執行時間

CPU時間=（CPU執行周期數+存儲器停頓周期數）X時鐘周期時間

其中：

＞存儲器停頓時鐘周期數=“讀”的次數X讀失效率X讀失效開

銷+“寫”的次數X寫失效率X寫失效開銷

＞存儲器停頓時鐘周期數=訪存次數X失效率X失效開銷

CPU時間=/Cx[c/7exec總〃I訪存次數

X失效率X失效開銷X時鐘周期時間

‘指令數7

失效次數_訪存次數失效率

每條指令的平均失效次數=X

指令數一指令數

存儲器停頓周期數）

"U時間=/CxCPIexecutionX時鐘周期時間

指令數7

例5.2我們用一個和AlphaAXP類似的機器作為第一個例子。假設

Cache失效開銷為50個時鐘周期，當不考慮存儲器停頓時，所有指令的執行

時間都是2.0個時鐘周期，訪問Cache失效率為2%,平均每條指令訪存L33

次。試分析Cache對性能的影響。

解存儲器停頓周期數」」

。尸U時間=/。義（。尸/exe+-----------------------------------------）X時鐘周期時間

指令數

考慮Cache的失效后，性能為：

CPU時間有cache=ICX（2.0+1.33X2%X50）X時鐘周期

=ICX3.33X時鐘周期時間

實際。尸/：3.33

3.33/2.0=1.67（倍）

CPU時間也增加為原來的1.67倍。

但若不采用Cache,則：CPI=2.0+50X1.33=68.5

4.Cache失效對于一個CPI較小而時鐘頻率較高的CPU來說，

影響是雙重的：

>CPLxecution越低，固定周期數的Cache失效開銷的相對

影響就越大。

>在計算CPI時，失效開銷的單位是時鐘周期數。因

此，即使兩臺計算機的存儲層次完全相同，時鐘頻率

較高的CPU的失效開銷較大，其CPI中存儲器停頓這

部分也就較大。

因此Cache對于低CPI、高時鐘頻率的CPU來說更加

重要。

例5.3考慮兩種不同組織結構的Cache：直接映象Cache和2

路組相聯Cache,試問它們對CPU的性能有何影響？先求平均

訪存時間，然后再計算CPU性能。分析時用以下假設：

(1)理想Cache(命中率為100%)情況下的CPI為2.0,時鐘

周期為2ns,平均每條指令訪存1.3次。

(2)兩種Cache容量均為64KB,塊大小都是32字節。

(3)圖5.8說明，在組相聯Cache中，必須增加一個多路選擇

器，用于根據標識匹配結果從相應組的塊中選擇所需的數據。

因為CPU的速度直接與Cache命中的速度緊密相關，所以對于

組相聯Cache,由于多路選擇器的存在而使CPU的時鐘周期增

加到原來的1.10倍。

(4)這兩種結構Cache的失效開銷都是70ns。

(5)命中時間為1個時鐘周期，64KB直接映象Cache的失效

率為1.4%,相同容量的2路組相聯Cache的失效率為1.0%。

解：平均訪存時間為：

平均訪存時間=命中時間+失效率X失效開銷

因此，兩種結構的平均訪存時間分別是：

平均訪存時間1路=2.0+(0.014X70)=2.98ns

平均訪存時間2路=2.021.10+(0.010X70)=2.90ns

2路組相聯Cache的平均訪存時間比較低。

CPU時間=ICX(CPIexe+每條指令的平均存儲器停頓周期數)X時

鐘周期時間=ICX(CPIexeX時鐘周期時間+每條指令的平均存儲

器停頓時間)

因此：CPU時間］路=ICX(2.0X2+(1.3X0.014X70))=5.27XIC

CPU時間2路=ICX(2.0X2X1.10+(1.3X0.010X70))=5.31XIC

CPU時間2路5.31xIC

CPU時間1路5.27xIC

直接映象Cache的平均性能好一些。

5.2.7改進Cache的性能

1.平均訪存時間=命中時間+失效率又失效開銷

2.可以從三個方面改進Cache的性能：

＞降低失效率

＞減少失效開銷

＞減少Cache命中時間

3.下面介紹17種Cache優化技術

□8種用于降低失效率

□5種用于減少失效開銷

□4種用于減少命中時間

5.3降低Cache失效率的方法

1.三種失效(3C)

＞強制性失效(Compulsorymiss)：當第一次訪問一^塊時，

該塊不在Cache中，需從RAM中調入Cache,這就是強制

性失效。(冷啟動失效，首次訪問失效)

＞容量失效(Capacitymiss)：如果程序執行時所需的塊不能

全部調入Cache中，則當某些塊被替換后，若又重新被訪

問，就會發生失效。這種失效稱為容量失效。

＞沖突失效(Conflictmiss)：在組相聯或直接映象Cache中，

若太多的塊映象到同一組(塊)中，則會出現該組中某個塊

被別的塊替換(即使別的組或塊有空閑位置)，然后又被重

新訪問的情況。這就是發生了沖突失效。

2.三種失效所占的比例

>圖示I（絕對值）圖示II（相對值）

各種類型的失效率（絕對值）

各種類型

的失效率

容量失效

各種類型的失效率（相對值）

強制性失效

A結論:

□相聯度越高，沖突失效就越少;

□強制性失效和容量失效不受相聯度的影響；

□強制性失效不受Cache容量的影響，但容量失效卻隨著容量的增

加而減少；

□表5.5中的數據符合2:1的Cache經驗規則，即大小為N的直接映象

Cache的失效率約等于大小為N/2的2路組相聯Cache的失效率。

5.3降低Cache失效率的方法

A減少三種失效的方法

□強制性失效：增加塊大小，預取

（本身很少）

□容量失效：增加容量

（抖動現象）

□沖突失效：提高相聯度

（理想情況：全相聯）

?許多降低失效率的方法會增加命中時間或失效開銷

方法1：增加Cache塊大小

1.失效率與塊大小的關系

>對于給定的Cache容量，當塊大小增加時，失效

率開始是下降，后來反而上升了。

原因：

□一方面它減少了強制性失效；

□另一方面，由于增加塊大小會減少Cache中塊的數

目，所以有可能會增加沖突失效。

>Cache容量越大，使失效率達到最低的塊大小就

越大。

Cache失效率與塊大小的關系

＞各種塊大小情況下Cache的失效率

塊大小Cache容量（字節）

（字節）1K4K16K64K256K

1615.05%8.57%3.94%2.04%1.09%

3213.34%7.24%2.87%1.35%0.70%

6413.76%7.00%2.64%1.06%0.51%

12816.64%7.78%2.77%1.02%0.49%

25622.01%9.51%3.29%1.15%0.49%

各種塊大小情況下Cache的平均訪存時間

塊大小失效開銷Cache容量（字節）

（字節）（時鐘周

1K4K16K64K256K

期）

16427.3214.5992.6551.8571.458

32446.8704.1862.2631.8571.308

64487.6054.3602.2671.5941.245

1285610.3185.3572.5511.5091.274

2567216.8477.8473.3691.5711.353

方法2：提高相聯度

1.采用相聯度超過8的方案的實際意義不大。

2.2:1Cache經驗規則

容量為N的直接映象Cache的失效率和容量為N/2的2

路組相聯Cache的失效率差不多相同。

3.提高相聯度是以增加命中時間為代價。

例如：

□TTL或ECL板級Cache,2路組相聯：增加10%

□定制的CMOSCache,2路組相聯：增加2%

例5.5假定提高相聯度會按下列比例增大處理器時鐘周

期：

時鐘周期2路=L10X時鐘周期］路

時鐘周期4路=1.12X時鐘周期1路

時鐘周期8路=L14X時鐘周期］路

假定命中時間為一個時鐘周期，直接映象情況下失效開

銷為50個時鐘周期，而且假設不必耨失效開銷取整。使

用表5.5中的失效率，試問當Cache為多大時，以下不等

式成立？

平均訪存時間8路<平均訪存時間4路

平均訪存時間4路<平均訪存時間2路

平均訪存時間2路<平均訪存時間1路

解：在各種相聯度的情況下，平均訪存時間分別為：

平均訪存時間8路=命中時間8路+失效率8路X失效開銷8路

=1.14+失效率g路X50

平均訪存時間4路=1.12+失效率4路X50

平均訪存時間2路=1.10+失效率2路x50

平均訪存時間1路=1.00+失效率1路X50

把相應的失效率代入上式，即可得平均訪存時間。

例如，1KB的直接映象Cache的平均訪存時間為：

平均訪存時間1路=L00+0.133X50=7.65

128KB的8路組相聯Cache的平均訪存時間為：

平均訪存時間8路=L14+0.006X50=1.44

失效率請查表5.5

在各種容量和相聯度情況下Cache的平均訪存時間

相聯度（路）

Cache谷里

1248

17.656.606.225.44

25.904.904.624.09

44.603.953.573.19

83.303.002.872.59

162.452.202.122.04

322.00