1.盡管在理想情況下，我們希望儲容量無限大，這

樣一個特定的……字都可以立刻獲取……我們……

不得不考慮到構(gòu)建存儲器層次結(jié)構(gòu)的可能性，它們

中的每一層都比其上一層具有更大的容量和更慢的

訪問速度。

A.W.Burks,H.H.Goldstine和JeonNeumann

PreliminaryDiscussionoftheLogicalDesignofanElectronicComputingInstruction[i946]

2.Cache是什么？

隱藏或存儲東西的安全地點。

韋伯斯特新世界美語詞典?第二版（1976）

5

1.存儲器層次結(jié)構(gòu)的基本概念

2.Cache/主存存儲器層次結(jié)構(gòu)

3.改進(jìn)Cache/主存性能的技術(shù)

4.主存的組織方式

5.虛擬存儲器

6.基于程序行為特性的優(yōu)化技術(shù)

.7.Alpha機的存儲器層次結(jié)構(gòu)

本章要點：

L存儲器層次結(jié)構(gòu)的基本概念

存儲器是計算機系統(tǒng)的核心組成部分。本章介紹儲器

層次結(jié)構(gòu)的基本概念和原理，討論和分析如何利用局部性

原理提高Cache/主存存儲器層次結(jié)構(gòu)、虛擬存儲器的性

能，最后以Alpha機的存儲系統(tǒng)為實例介紹存儲器的工作過

程。

?存儲器的基本性能參數(shù)

?存儲器層次結(jié)構(gòu)的基本原理

?存儲器存儲結(jié)構(gòu)的性能

?存儲器層次結(jié)構(gòu)對CPU設(shè)計的影響

?存儲器存儲結(jié)構(gòu)設(shè)計的基本問題

2013年5月7日星期二12時54分30秒計算機體系結(jié)構(gòu)

1.1存儲器的基本性能參數(shù)

評價存儲器性能的參數(shù)主要有三個方面:

S=IVx/x表示。其中怫存儲器字長，/為存

儲器字節(jié)，m為存儲器個數(shù)。

訪問時間(accesstime)Ta：從存儲器接到讀請求到所讀的

字傳送到數(shù)據(jù)總線上的時間間隔。

存儲周期Tm：連續(xù)兩次訪問存儲器之間所必需的最小時

間間隔。一般，Tm>Tao

存儲帶寬Bm：存儲器被連續(xù)訪問時所提供的數(shù)據(jù)傳輸速

率，單位是位(或字節(jié))/S。

：通常用單位字節(jié)價格來表示。若總?cè)萘繛镾的存

儲器的總價格為C,則單位字節(jié)價格c=C/S。________

2013年5月7日星期二12時54分30秒計算機體系結(jié)構(gòu)4

1.2存儲器層次結(jié)構(gòu)的基本原理

程序設(shè)計人員總是希望存儲器的速度盡可能的高，以

與處理器的速度相匹配；存儲器的容量盡可能的大，以裝

下可能極大的程序，因此,高速度!大容量：低價格始終

是存儲體系的。

存儲器的工藝實現(xiàn)技術(shù)有了突飛猛進(jìn)的發(fā)展，高速、

大容量、低價格的存儲器件以驚人的速度生產(chǎn)出來。盡管

如此，一方面，經(jīng)過幾十年的發(fā)展，存儲技術(shù)的發(fā)展證明

單一工藝的單一存儲器很難同時滿足容量、價格、速度三

方面的性能要求（見圖5-1存儲器的速度與價格的關(guān)系曲線）。

事實上，對容量與速度、速度與價格、容量與價格的性能

要求是相互有矛盾的。而且，存儲器速度的改進(jìn)始終跟不

上CPU速度的提高。

2013年5月7日星期二12時54分30秒計算機體系結(jié)構(gòu)5

1.2存儲器層次結(jié)構(gòu)的基本原理

圖5-1存錯器的藻彥價格的關(guān)系曲終

2013年5月7日星期二12時54分30秒計算機體系結(jié)構(gòu)6

存儲器層次結(jié)構(gòu)的基本原理

內(nèi)存

RAMROM（只讀存儲器）

2013年5月7日星期二12時54分30秒計算機體系結(jié)構(gòu)7

1.2存儲器層次結(jié)構(gòu)的基本原理

另一方面，根據(jù)局部性原理，即所有程序都具有這樣

的行為特性：程序傾向于再次使用最近剛用過的數(shù)據(jù)和指

令。這樣的局部性反映在空間和時間兩個方面：

如果某個數(shù)據(jù)或指令被引

用，那么地址鄰近的數(shù)據(jù)或指令不久很可能也揩被引用。

如果某個數(shù)據(jù)或指令被引

用，那么不久它可能還揩再次被引用。

為了滿足對存儲器的性能要求，隨著技術(shù)的不斷發(fā)

展，根據(jù)程序本身這種局限性的行為特性及小硬件速度更

快的設(shè)計原則，基于不同容量和速度的多種存儲器所構(gòu)成

的存儲器層次結(jié)構(gòu)很自然就產(chǎn)生了，如圖5?2。

2013年5月7日星期二12時54分30秒計算機體系結(jié)構(gòu)8

1.2存儲器層次結(jié)構(gòu)的基本原理

>

(a)抽象結(jié)構(gòu)圖

10ms40Gb-2Tb

1ns<1Kb10ns128Mb-64Gb100

01)

4

0

CPU2設(shè)備

。I/O

QQ主存

、I_~I口OI

寄存器Cache存儲器磁盤存情

容量：500byte64KB512MB100GB

速度：0.25ns1ns100ns5ms

(b)典型的存儲器層次結(jié)構(gòu)

圖5?2

2013年5月7日星期二12時54分30秒計算機體系結(jié)構(gòu)9

1.2存儲器層次結(jié)構(gòu)的基本原理引自(美)JohnL.Hennessy

DavidA.Patterson

表0.5?1計算機系統(tǒng)中存儲器層次結(jié)構(gòu)中每一級的容量和訪問時間范圍

層次1234

名稱寄存器Cache內(nèi)存磁盤

典型容量<1KB<16MB<16GB>100GB

多端口定制片內(nèi)或片外

共現(xiàn)技術(shù)CMOSDRAM磁盤

存儲器,CMOSCMOSSRAM

訪問時間(ns)0.25^0.50.5-2580-2505000000

帶寬(MB/s)20000-1000005000-100001000-500020-150

管理編譯器硬件操作系統(tǒng)操作系統(tǒng)/操作者

下一級Cache內(nèi)存磁盤CD-ROM或磁帶

2013年5月7日星期二12時54分30秒計算機體系結(jié)構(gòu)10

存儲器層次結(jié)構(gòu)的基本原理

一個存儲器層次結(jié)構(gòu)由多級不同類型的存儲器構(gòu)

成；越靠近CPU的存儲器容量越小、速度越快、價格

越高，離CPU越遠(yuǎn)的容量越大、速度越慢、價格越

低；

第i級存儲器存儲的信息是i"級存儲信息的子集

（根據(jù)），相鄰兩級存儲器之間以塊為單

位進(jìn)行信息交換（根據(jù)）；

各級存儲器借助輔助軟硬件構(gòu)成一個整體，使得

該存儲體系具有接近于第"級存儲器速度、接近于第1

1.2存儲器層次結(jié)構(gòu)的基本原理

處

理

器

高層存儲器

低層存儲器

圖5?3兩級存儲器層次結(jié)構(gòu)

2013年5月7日星期二12時54分30秒計算機體系結(jié)構(gòu)12

1.2存儲器層次結(jié)構(gòu)的基本原理

存儲器的層次結(jié)構(gòu)是由多級存儲器構(gòu)成的，但管理是以兩級存儲器

為單位來進(jìn)行的，而且一般只有在相鄰兩級存儲器之間可以進(jìn)行信息交

換。下面以兩級存儲器結(jié)構(gòu)為例介紹存儲器結(jié)構(gòu)的一些基本概念：

■相鄰兩級存儲器之間信息交換的最小單位。塊大小一

般是固定的，但也可以是可變的。若塊的大小固定，則兩級存儲器

的容量為塊大小的整數(shù)百倍。

H:CPU產(chǎn)生的有效地址可以在高層存儲器中訪

問到的概率。

?M：CPU產(chǎn)生的有效地址不能直接在高

層存儲器中訪問到的概率。

?HT:訪問到高層存儲器所需的時間，其中包

括本次訪問是命中還是失配的判定時間。

2013年5月7日星期二12時54分30秒計算機體系結(jié)構(gòu)14

1.2存儲器層次結(jié)構(gòu)的基本原理

4:訪問明的次數(shù)

“：訪問的次數(shù)

命中率：〃=%/（4+丹）

失配率：M=1-H

圖0?5.2命中率與失配率miss的描述圖

2013年5月7日星期二12時54分30秒計算機體系結(jié)構(gòu)15

1.2存儲器層次結(jié)構(gòu)的基本原理

-：用低層存儲器中的相應(yīng)的塊替換高層

存儲器中的塊，并將所訪問數(shù)據(jù)傳送到請求訪問的設(shè)備（通常是

CPU）的時間。又可細(xì)分為訪問時間和傳送時間。

訪問高層存儲器失配時，在低層存儲器

中訪問到塊中第一個字的時間（又稱訪問延遲access

latency）,它與低層存儲器的延遲有關(guān)，而與塊大小無關(guān)。

傳送塊內(nèi)字的時間，它依賴于兩級存儲

器之間的傳輸帶寬和塊大小，一定傳輸帶寬下與塊大小

成正比。

2013年5月7日星期二12時54分30秒計算機體系結(jié)構(gòu)16

1.3存儲器存儲結(jié)構(gòu)的性能

存儲器層次結(jié)構(gòu)的設(shè)計目標(biāo)之一就是使其速度接近于

高層存儲器的速度。最準(zhǔn)確的應(yīng)用執(zhí)行時間來衡量，間接

地用平均存儲訪問時間(averagememory_accesstime,AI\AT)來衡量。

更好地評價存儲器層次結(jié)構(gòu)的性能參數(shù)是平均存儲的訪問

時間，其定義如下：

平均存儲訪問時間=命中時間+失配率X失配時間

表示為：AMT=HT+MxMP

應(yīng)該注意的是盡管用AMT來評價存儲器層次結(jié)構(gòu)的性

能比簡單的用HT來評價要好，AMT仍然是性能的一種間接

測度，它無法完全替代執(zhí)行時間這個最準(zhǔn)確的性能參數(shù)。

2013年5月7日星期二12時54分30秒計算機體系結(jié)構(gòu)17

置存儲器存儲結(jié)構(gòu)的性能

由圖5-4(b)可見失配率與塊大

八失配率

小之間的關(guān)系呈現(xiàn)三種不同性質(zhì)：

■當(dāng)塊大小過小時，失配率很高。

隨著塊大小的增加，由于有效

地利用了程序的空間局部性，

失配率呈現(xiàn)下降趨勢。

?當(dāng)高層存儲器容量保持不變

?時，失配率有一最低限值，此

0

塊大小時塊大〃'的變化對失配率沒有

影響。

圖5?4(b)塊大小與失配率的關(guān)系?當(dāng)塊大小超過某定值(又稱

)后，失配率呈現(xiàn)隨塊大小

2013年5月7日星期二12時54分30秒計算機口加，］上升的趨勢。~

1.3存儲器存儲結(jié)構(gòu)的性能

t失配損失，平均存儲訪問時間

傳送時間

訪問時間

塊大小塊大小

——??

00

圖5?4(a)塊大小失配損失的關(guān)系圖5?5塊大小與平均存儲訪問時間的關(guān)系

由于失配損失中的訪問延遲部分與塊大小無關(guān)，傳送時間隨塊大小的

增加而線性增長，如圖5?4(a),當(dāng)訪問延遲很大時，增加塊大小對失配損失

的影響不大。綜合考慮塊大小對失配率及失配損失的影響后，塊大小與平均

存儲訪問時間的關(guān)系見圖5?5。

設(shè)計存儲器層次結(jié)構(gòu)的根本目標(biāo)是為了減少執(zhí)行時間,因此在確定塊大

小時，不能以失配率為標(biāo)準(zhǔn)，而應(yīng)選擇使平均存儲訪問時間最小的塊大小

2013年5月7日星期二12時54分30秒計算機體系結(jié)構(gòu)19

存儲器層次結(jié)構(gòu)對CPU設(shè)計的影響

處理器的性能是計算機設(shè)計的最終目標(biāo)，所

以在考慮降低平均存儲訪問時間的同時還應(yīng)考慮

對CPU性能的影響。保證設(shè)計方案不僅能降低平

均存儲訪問時間，還能有益于改進(jìn)CPU的性能，

同時提高CPI。

在不支持存儲器層次結(jié)構(gòu)的系統(tǒng)中，由于所

有的存儲訪問需要相同的時間，所以處理器的設(shè)

計相對簡單。而在存儲器層次結(jié)構(gòu)中對高層存儲

器的訪問存在失配問題，這意味著CPU必須能夠

處理可變的存儲訪問時間。

2013年5月7日星期二12時54分30秒計算機體系結(jié)構(gòu)20

存儲器層次結(jié)構(gòu)對CPU設(shè)計的影響

當(dāng)失配損失較小，只有幾十個時鐘周期時，CPU采

用等待塊傳輸結(jié)束的策略。

當(dāng)失配損失較大，達(dá)到CPU時鐘周期的幾千倍時,

一般采用中斷使CPU切換到其它進(jìn)程去執(zhí)行的辦法。

處理器還必須設(shè)有一些機制以確定所需信息是否在存儲

器層次結(jié)構(gòu)的最高層存儲器中。在每次存儲訪問時都要做這

種判定檢查，因而會影響命中時間。為了保證達(dá)到可接受的

性能，這種檢測機制通常用硬件實現(xiàn)。要實現(xiàn)存儲器層次結(jié)

構(gòu)，處理器還必須有在相鄰兩級存儲器之間傳送信息塊機制。

如果塊傳送只需幾十個時鐘周期，那么這種傳送機制一

般用硬件來控制；

如果需要幾千個時鐘周期，則可以用軟件方法實現(xiàn)。

2013年5月7日星期二12時54分30秒計算機體系結(jié)構(gòu)21

1.5存儲器層次結(jié)構(gòu)設(shè)計的基本問題

由于所有的存儲器層次結(jié)構(gòu)幾乎都有相同的設(shè)計目標(biāo)，遵循相同的設(shè)

計原則，所以在考慮設(shè)計某二級存儲器構(gòu)成的存儲器層次結(jié)構(gòu)時所需考慮

的基本問題是一致的。下面是存儲器層次結(jié)構(gòu)設(shè)計中的四大基本問題：

在低層存儲器中的塊以什么方式與高層存儲器中的塊相對應(yīng)（即每個

低層存儲器的塊按什么規(guī)則裝入高層存儲器）？

直接映象、全關(guān)聯(lián)映象、組關(guān)聯(lián)映象

如果某信息塊在高層存儲器中，如何識別與查找它？

查找算法―（的實現(xiàn)）

發(fā)生訪問失配而高層存儲器所有可能對應(yīng)塊中不存在無效的塊，此

時根據(jù)什么規(guī)則？

算法一選擇有效信息塊將之淘汰出高層存儲器，而換之以從

低層存儲器中傳送來的新塊。

寫操作時，采用何種策略？

算法―以保持相鄰兩級存儲器中數(shù)據(jù)的一致性，發(fā)生寫操作

失配時是否將被寫的塊從低層存儲器取入高層存儲器。

2013年5月7日星期二12時54分30秒計算機體系結(jié)構(gòu)22

2.Cache/主存存儲器層次結(jié)構(gòu)

在現(xiàn)代計算機設(shè)計中幾乎全部采用了Cache技術(shù)，這

是因為在CPU與主存之間引入Cache,有效地解決了CPU

與主存之間的速度匹配問題。由Cache與主存構(gòu)成的存儲

器層次結(jié)構(gòu)具有兩級存儲器層次結(jié)構(gòu)的一般特點。

?Cache/主存的映象方式

?Cache/主存的映象機構(gòu)

?Cache/主存的替換策略

?Cache/主存的寫策略

?Cache主存存儲器層次結(jié)構(gòu)實例

?Cache/主存的性能分析

2013年5月7日星期二12時54分30秒計算機體系結(jié)構(gòu)23

2.Cache/主存存儲器層次結(jié)構(gòu)

表5?1Cache基本結(jié)構(gòu)參數(shù)

塊（行）大小4~128字節(jié)

命中時間1~2時鐘周期（常規(guī)為1）

失配損失8~100時鐘周期

（訪問時間）（6~60時鐘周期）

（傳送時間）（2~40時鐘周期）

失配率0.5%~10%

Cache容量IKB^IMB

2.1Cache/主存的映象方式

最基本的Cache/主存映象方式有三種：

1.直接映象(directmapped)：這是最簡單的一種映象方

式。主存中的一信息塊只能對應(yīng)Cache的一個特定行，如

圖5?6。設(shè)Cache中共有m=2Cb行，主存共分為2Mb塊，

通常按下列規(guī)則)將主存中的第i塊映象到Cache中的第J

行：

j=imod2cb

M

(j=0,1,???，2.?1,i=l,2v..,2b-D

5是Cacheblock首字母的表示；

是Memoryblock首字母的表示。

2013年5月7日星期二12時54分30秒計算機體系結(jié)構(gòu)25

Cache/主存的映象方式

主存

塊a

塊1

Cache???

o行塊0

塊2cb

塊1

塊2cb+1

???

M“行塊2塊

???

塊（21」）2孰

塊（2口卜2。+1

對比：閱覽室位置——只有???

一個位置可以坐。

塊，Mb_1

特點：空間利用率最低，沖

突概率最高，實現(xiàn)最簡單。圖5?6直接映像（

2013年5月7日星期二12時54分30秒計算機體系結(jié)構(gòu)26

2.1Cache/主存的映象方式

2.全關(guān)聯(lián)映象(fullyassociative)：主存中的一信息塊可對

應(yīng)Cache中的任意一行，如圖5?7。

2013年5月7日星期二12時54分30秒計算機體系結(jié)構(gòu)27

2.1Cache/主存的映象方式

3.組關(guān)聯(lián)映象(setassociative)：將Cache的行分成

若干組，不妨設(shè)為G組，G=2S,則每組中有n=

2%G=2(c『s)=2,行。主存中的第，塊可以對應(yīng)

Cache中的某一特定組中的任意一行。若組中有n

行，則稱之為o組關(guān)聯(lián)映象方式示

意圖見圖

容易看出，直接映象與全關(guān)聯(lián)映象都是組關(guān)

聯(lián)映象方式的特例：直接映象即1路組關(guān)聯(lián)，而全

關(guān)聯(lián)映象為m路組關(guān)聯(lián)(m=2cb)o

2013年5月7日星期二12時54分30秒計算機體系結(jié)構(gòu)28

Cache/主存的映象方式

Cache

至

組。???

塊2比1

塊2。

組1???

塊"J

???

組相聯(lián)

???

塊心.1

的一種

折衷。圖5?8組關(guān)聯(lián)映象

2013年5月7日星期二12時54分30秒計算機體系結(jié)構(gòu)29

弓I自（美MohnL.Hennessy

2.1Cache/主存的映象方式DavidA.Patterson

Cache

7O

6的

5

直接映射：,n

塌

2a

c分

塊號；h

如12只能進(jìn)入塊4e配

際

的

塊

塊

金

地

主

全關(guān)聯(lián)址

存

在

三

內(nèi)

塊號種

存

軌12可進(jìn)入任何一個塊映

象

母

且

73

6

勢

組關(guān)聯(lián)：且2

勢

3且1

2

勢n0

1ir

塊號■■

塊12可選入組0中的任何一第

2013年5月7日星期二12時54分30秒計算機體系結(jié)構(gòu)

2.2Cache/主存的映象機構(gòu)

映象機構(gòu)的是根據(jù)CPU送來的有效主存地址

確定要訪問的信息是否在Cache中，并找到該信息

塊，也即它是映象方式的具體實現(xiàn)。

由于無論采用哪種映象方式，Cache中的某一行

總是對應(yīng)于主存的多個塊，即Cache中的某信息行其

來源可以是主存中的多個塊。因此，Cache中的每行

都帶有一個標(biāo)志(tag)以確定該行所對應(yīng)的主存塊。

Cache中存放標(biāo)志的那部分存儲器稱為

o每個Cache的標(biāo)志中可以包含一些特定的信息，

根據(jù)這些特定信息可以檢測它們是否和來自CPU的塊

幀地址相匹配。

2013年5月7日星期二12時54分30秒計算機體系結(jié)構(gòu)31

2.2Cache/主存的映象機構(gòu)

由于主存中的某一塊可映象到Cache中的多個塊

(直接映象除外)，且對Cache/主存存儲器層次來

說，速度性能是至關(guān)重要，因而來自CPU的主存地址是

和Cache中所有可能對應(yīng)行的標(biāo)志同時作相聯(lián)比較，以

快速找出相匹配的塊，如圖5?9示。

為確定Cache行中的所含信息是否有效，通常還在

行標(biāo)志中添加一個有效位(validbit),指明行中信息是否有效。

如果未置有效位，則該行的標(biāo)志不能與主存地址匹配。

每個Cache行都帶有一個標(biāo)志，所以增加塊大小有

益于減少標(biāo)志存儲器成本在eache總成本中所占的比例o

2013年5月7日星期二12時54分30秒計算機體系結(jié)構(gòu)32

2013年5月7日星期二12時54分30秒計算機體系結(jié)構(gòu)33

超Cache/主存的映象機構(gòu)

如何由CPU地址在Cache中判定CPU要訪問的信息

塊？

如圖5?10,來自CPU的主存地址由兩部分組成：居

地址高端的塊幀地址(block-frameaddress)和居地址低端部分

的塊內(nèi)偏移地址(block-offsetaddress)o其中：

?塊內(nèi)偏移地址：用于從塊內(nèi)選取所需字節(jié)(設(shè)塊大小為

2W字節(jié))；

?塊幀地址(Mb位)在組關(guān)聯(lián)方式下分成兩部分：

⑴索弓l(index)：用于選取組；

⑵標(biāo)志(tag)：用于和Cache中的行標(biāo)志進(jìn)行比較。

2013年5月7日星期二12時54分30秒計算機體系結(jié)構(gòu)34

Cache/主存的映象機構(gòu)

塊幀地址（MJ塊內(nèi)偏移（2亞）

X

索引

圖5?10CPU地址組成

2013年5月7日星期二12時54分30秒計算機體系結(jié)構(gòu)35

2.2Cache/主存的映象機構(gòu)

?判定過程:

當(dāng)CPU給出一地址后，首先由索引確定2s組

中的一個組，然后地址標(biāo)志和該組中的所有行標(biāo)

志（共2?個，每個Mb?S位）進(jìn)行相聯(lián)比較。若有

相同的且有效位被置位，則表示相應(yīng)信息塊在

Cache中，命中Cache后由塊內(nèi)偏移地址確定要

訪問的具體字節(jié)。

否貝U,Cache失酉丁

2013年5月7日星期二12時54分30秒計算機體系結(jié)構(gòu)36

2.2Cache/主存的映象機構(gòu)

Cache的容量、塊大小保持不變，不同關(guān)聯(lián)度的比較:

行標(biāo)志標(biāo)志寬度

映象方式索引位備注

（個）（位）

e折或方案，是較好的選擇

組關(guān)聯(lián)2Mb-Ss

直接1Mb-CbCb

全關(guān)聯(lián)2cbMb0

在Cache的容量、塊大小一定的情況下，關(guān)聯(lián)度越高，塊沖

突率、失配率越低，而映像機構(gòu)的實現(xiàn)越復(fù)雜、成本越高。從性

能折衷權(quán)衡考慮，組關(guān)聯(lián)映像方式是一種較好的選擇方案。,

2013年5月7日星期二12時54分30秒計算機體系結(jié)構(gòu)37

2.3Cache/主存的替換策略

當(dāng)訪問Cache失配時，如果相應(yīng)的組中存在無效數(shù)據(jù)行

（該行的有效位未置），此時不存在替換問題，否則必須采取

某種策略選擇一有效數(shù)據(jù)行招其淘汰出Cache,而換之經(jīng)從

主存送來的數(shù)據(jù)塊。Cache替換策略非常重要，它將直接影

響Cache的命中率。

對于直接映象方式而言，實現(xiàn)替換策略的硬件機制相對

較簡單。事實上，此時不存在選擇問題，因為參與地址匹配

的只有一個行標(biāo)志，所以發(fā)生失配時只能對這一個特定行進(jìn)

行替換。但是，對于全關(guān)聯(lián)和組關(guān)聯(lián)映象，發(fā)生Cache失配

時，如果組中不存在無效的數(shù)據(jù)行，就需要在多個有效的數(shù)

據(jù)行中進(jìn)行選擇。基本的替換策略有以下三種:

2013年5月7日星期二12時54分30秒計算機體系結(jié)構(gòu)38

2.3Cache/主存的替換策略

1.隨機替換策略(RAND)：隨機地在候選行中選擇

一行進(jìn)行替換。由于完全隨機的選擇將給硬件調(diào)試

帶來很大的困難，因此，為使替換行為可再現(xiàn)以利

調(diào)試，一些系統(tǒng)實際上采用的是偽隨機替換策略。

這種策略沒有利用數(shù)據(jù)行的“歷史”使用信息，不反

映程序行為的局部性。

2.先進(jìn)先出策略(RF。)：在候選塊中選擇最早送

入Cache的那一行進(jìn)行替換。它利用了數(shù)據(jù)行的“歷

史”使用信息，但不能正確反映程序局部性，因為最

早進(jìn)入Cache的塊很可能是經(jīng)常被引用的塊。

2013年5月7日星期二12時54分30秒計算機體系結(jié)構(gòu)39

2.3Cache/主存的替換策略

3.最近最少使用策略(LRU)：在候選塊中選擇最近最少

被訪問到的那一行進(jìn)行替換。這種策略是利用程序局部性

原理的必然結(jié)果，因為最近使用過的塊很可能不久再次被

引用。為減少可能再次被引用的塊替換出去的機會，最佳

候選塊只能是最近最少使用的塊，要實現(xiàn)LRU策略，就必

須記錄行被訪問的情況。圖5?11給出了在全關(guān)聯(lián)映象的存

儲器層次結(jié)構(gòu)中。對于某一塊幀地址序列，使用LRU策略

選擇的替換塊號。假設(shè)Cache分成4個塊，而且開始時最

近最少使用的塊是塊0。

塊幀地址0321__00231__

LRU塊號0000333%工

圖5?11LRU：

2013年5月7日星期二12時54分30秒計算機體系結(jié)構(gòu)40

Cache/主存的替換策略

盡管FIFO策略利用了數(shù)據(jù)塊使用的“歷史”信息，但實

驗數(shù)據(jù)表明RAND策略的性能一般比FIFO策略要好，而且

RAND最重要的特點是簡單，易于用硬件實現(xiàn)。一般說

來，LRU策略的性能要好于RAND,但隨著要記錄訪問的

塊數(shù)增多，實現(xiàn)LRU策略的成本迅速增加，此時性能改進(jìn)卻不

明顯。

表5?2列出了不同Cache容量、不同關(guān)聯(lián)度情況下，使

用LRU策略和RAND策略時Cache失配率的對比實驗數(shù)據(jù)。

由表中最后一行數(shù)據(jù)可知，當(dāng)Cache容量達(dá)256KB時，采

用何種替換策略對失配率幾乎沒有影響。因此可見，與大

神需黜盛艱勒替換策略雙Q簾寓戶Ch?的性能影響更東

Cache/主存的替換策略

表5?2替換策略對Cache失配率的影響

關(guān)聯(lián)度2路8路

容量LRURANDLRURANDLRURAND

16KB5.18%5.69%4.67%5.29%4.39%4.96%

64KB1.88%2.01%1.54%1.66%1.39%1.53%

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

2013年5月7日星期二12時54分30秒計算機體系結(jié)構(gòu)42

2.，Cache/主存的寫策略

所有的取指訪問都是讀操作，而大部分指令不

對存儲器進(jìn)行寫操作，所以，對于Cache的訪問主

要是讀操作。根據(jù)第二章指令使用頻度分析可知，

一般程序的數(shù)據(jù)傳送指令中，取數(shù)操作(3d)大約是

存數(shù)操作(皿⑹的2倍，而且在存儲器數(shù)據(jù)傳送(memory

tracer)中，寫操作所占比例不到10%。根據(jù)高頻事件

高速處理的設(shè)計原則，在Cache中應(yīng)盡量優(yōu)化讀操

作性能，同時由Amdahl定律可知，面向高性能的

設(shè)計不能忽視寫操作的速度。

2013年5月7日星期二12時54分30秒計算機體系結(jié)構(gòu)43

Cache/主存的寫策略

通常，Cache的讀操作較易快速實現(xiàn)。一般，在讀取

并比較標(biāo)志的同時就可以讀取相應(yīng)數(shù)據(jù)行，即一得到來自

CPU的塊幀地址就可以開始讀數(shù)據(jù)行操作。如果讀命中，

則讀出的數(shù)據(jù)行立即送往CPU,而如果讀失配，就作廢讀

出的數(shù)據(jù)，這樣作既沒好處，也沒損失。

寫操作的情況就不同了，處理器指定寫操作的數(shù)據(jù)寬度

在1?8字節(jié)之間，即一個寫操作僅改變一個數(shù)據(jù)塊某一部分

的內(nèi)容。通常寫操作又細(xì)分為三個步驟：

(1)讀取源數(shù)據(jù)塊。

⑵修改其中的一部分。

⑶寫回修改后的數(shù)據(jù)。因為修改步驟不能與標(biāo)志檢查

并行進(jìn)行，所以一定要等標(biāo)志檢查確定命中后才能進(jìn)行修

改步驟。這樣，寫操作所需的時間通常比讀操作長。

2013年5月7日星期二12時54分30秒計算機體系結(jié)構(gòu)44

2.，Cache/主存的寫策略

在Cache設(shè)計中有多種不同的寫策略，基本的

寫策略有如下兩種：

1.直寫(writethrough):信息被寫入Cache行的

同時，利用CPU和主存之間的直接數(shù)據(jù)通路寫入

主存的對應(yīng)塊中。

2.回寫(writeback):信息只寫入Cache的相應(yīng)

行，僅當(dāng)被修改過的行被替換出Cache時，才將

它寫入主存的相應(yīng)存儲塊中。

2013年5月7日星期二12時54分30秒計算機體系結(jié)構(gòu)45

2.，Cache/主存的寫策略

根據(jù)Cache行的信息與對應(yīng)主存塊的信息相同與

否，采用回寫技術(shù)的Cache行被分為“干凈的”或“臟的”

兩種。

即該數(shù)據(jù)行在Cache中未被修改過，數(shù)

據(jù)與其主存中對應(yīng)塊相同；

而即該數(shù)據(jù)塊在Cache中已被修改過。

因此當(dāng)“干凈”的行被替換出Cache時，不必漏該行

寫回主存。相反，當(dāng)“臟的”行被替換時，必須耨其寫回

主存。為區(qū)分行是“干凈的”還是“臟的:通常為每個

Cache行設(shè)置一個稱為“”（也稱“55）的標(biāo)志

位，指示該Cache行是否曾被修改過。采用這樣的技術(shù)

2013年對構(gòu)46

回寫技術(shù)和直寫技術(shù)各有利弊?；貙懠夹g(shù)的是：

Cache命中時，寫操作是以寫Cache的速度進(jìn)行，而且在一

個數(shù)據(jù)塊內(nèi)的多次寫操作只需要對低層存儲器寫一次。由于

每個寫操作都不必寫主存。因而回寫技術(shù)有利于降低Cache

/主存存儲器層次結(jié)構(gòu)對主存帶寬的要求。這一性質(zhì)使回寫

技術(shù)在多處理器計算機系統(tǒng)設(shè)計中頗具吸引力。對于直寫技

術(shù)，讀操作引起的Cache失配不會導(dǎo)致對低層存儲器的寫

操作。而且直寫技術(shù)的硬件實現(xiàn)更為簡單。直寫技術(shù)的另一

海端是j主存中總是保存著數(shù)據(jù)的最新拷貝.這一性質(zhì)對

I/O和多處理器系統(tǒng)都非常重要，我們將在534節(jié)以及第八

章加以討論。這樣，在多處理器計算機系統(tǒng)的設(shè)計中，既希

望利用回寫技術(shù)減少每個處理器與主存之間的數(shù)據(jù)傳輸量，

又希望用直寫技術(shù)保證Cache和主存的一致性。

2013年5月7日星期二12時54分30秒計算機體系結(jié)構(gòu)47

2.，Cache/主存的寫策略

如果采用直寫技術(shù)，那么在對低層存儲器

的寫操作期間，CPU必須停下來等待，CPU

的這段等待時間被稱為(writestall)o

通常所用的減少寫停頓延遲的辦法是寫

緩沖器。使CPU在存儲器更新期間能繼續(xù)工

作。但設(shè)置寫緩沖器也不能完全避免寫停

頓，這一點我們將在5331中再討論。

2013年5月7日星期二12時54分30秒計算機體系結(jié)構(gòu)48

Cache/主存的寫策略

當(dāng)出現(xiàn)寫失配時，無論直寫技術(shù)還是回寫技術(shù)都存在是否

要將修改的數(shù)據(jù)塊裝入Cache的問題，一般有兩種選擇方案：

1.寫分配(writeallocate):將要寫的數(shù)據(jù)裝入Cache,然后

進(jìn)行和寫命中時相同的操作，這種方法與讀失配時的處理方法

類似。

2■無寫分配(nowriteallocate):也稱為(writearound),

直接對低層存儲器中的數(shù)據(jù)塊做改寫操作，不再將此數(shù)據(jù)塊裝

入Cache。

雖然這兩種方案對直寫技術(shù)或回寫技術(shù)都適用，但通常的

做法是采用回寫技術(shù)時選擇寫分配，這樣對該數(shù)據(jù)塊的后續(xù)寫

操作可以在Cache中進(jìn)行(時間局部性原理的自然應(yīng)用)；采

用直寫技術(shù)時一般選擇無寫分配，因為按直寫技術(shù)，即使該數(shù)

據(jù)塊有后續(xù)寫操作仍需對主存作改寫操作。________________

2013年5月7日星期二12時54分30秒計算機體系結(jié)構(gòu)49

2.5Cache/主存存儲器層次結(jié)構(gòu)實例

本節(jié)將以VAX-11/780的Cache為例具

體介紹Cache/主存存儲器層次結(jié)構(gòu)，并介紹

其工作流程。

VAX-11/780fflCacheffl§W?38KB(8l92

字節(jié)），塊大小為8字節(jié)，映像方式是2路組關(guān)

聯(lián)，采用隨機替換策略及直寫技術(shù)，配有1個

字（4字節(jié)）的寫緩沖器，寫失配時采用無寫分

配方法。VAX/1/780的Cache結(jié)構(gòu)如圖5?12

所示。

2013年5月7日星期二12時54分30秒計算機體系結(jié)構(gòu)50

2.5Cache/主存存儲器層次結(jié)構(gòu)實例

塊幀地址塊內(nèi)偏移CPU

_■地址

素引

數(shù)據(jù)數(shù)據(jù)

入出

模塊。

512塊

⑤

512塊

A

Cache

SKBC8152).寫緩存

圖542VAX-11/780的微處理器中數(shù)據(jù)Cache結(jié)構(gòu)主存

2013年5月7日星期二12時54分30秒計算機體系結(jié)構(gòu)51

2.5Cache/主存存儲器層次結(jié)構(gòu)實例

如圖5?12,當(dāng)Cache讀命時,Cache的工作流程可分

為五大步驟，這五個步驟是在一個CPU時鐘周期內(nèi)完成的。

.來自CPU的地址被分為29位塊幀地址和3位塊內(nèi)偏移

地址，塊幀地址又分成20位標(biāo)志和9位索引。

,根據(jù)索引選擇Cache中的一個組，讀取組內(nèi)各行標(biāo)志

以判定要訪問的數(shù)據(jù)塊是否在Cache中。圖中512組中的0號

數(shù)據(jù)塊組成模塊o(banko),而1號數(shù)據(jù)塊組成模塊1(bankl。索

引被同時送往兩個模塊，讀取該組中兩個數(shù)據(jù)行的行標(biāo)志。

索引的位數(shù)是由Cache容量、塊大小及關(guān)聯(lián)度決定的，表達(dá)

式為_____________________________

組數(shù)=Cache容量_81929

塊大小X關(guān)聯(lián)度8x2=512=2

2013年5月7日星期二12時54分30秒計算機體系結(jié)構(gòu)52

2.5Cache/主存存儲器層次結(jié)構(gòu)實例

?塊幀地址的標(biāo)志域與步驟2中讀取的兩個行標(biāo)志作

相等比較。為保證相應(yīng)行的數(shù)據(jù)有效，對應(yīng)行的有效位必

須是被置位的，否則比較結(jié)果無效。

,假設(shè)有一行標(biāo)志與塊幀地址的標(biāo)志相匹配，則由2

選1多路轉(zhuǎn)換器選取相應(yīng)的數(shù)據(jù)行。兩個行標(biāo)志同時匹配

的情況是不可能發(fā)生的，因為替換算法保證了一個數(shù)據(jù)塊

只有一個行標(biāo)志。為減少命中時間，數(shù)據(jù)讀取是與讀取行

標(biāo)志同時進(jìn)行的，所以當(dāng)多路轉(zhuǎn)換器就緒時，數(shù)據(jù)也已準(zhǔn)

備好了。這一步驟在組關(guān)聯(lián)Cache中是不可少的，但在直

接映像Cache中，因為不必選擇數(shù)據(jù)行，所以本步驟可以

省去。由于多路轉(zhuǎn)換器可能處在關(guān)鍵的定時路徑(timingpath)

匕慶而可能影響CPU的時鐘圄即c

2013年5月7日星期二12時54分30秒計算機體系結(jié)構(gòu)53

2.5Cache/主存存儲器層次結(jié)構(gòu)實例

.讀出的字送往CPU。

讀Cach^^時，Cache向CPU發(fā)出一個停頓⑸叫信號

通知CPU等待，并從主存中讀入2個字(8字節(jié))。在VAX

?11/780上這需要6個時鐘周期(忽略總線干擾(businterference))o

從主存讀取的數(shù)據(jù)塊送達(dá)時，Cache要選擇一個數(shù)據(jù)行替

換出去，VAX?11/780的Cache采用隨機替換策略，即當(dāng)組

中兩個數(shù)據(jù)行均為有效行時隨機選取一行替換出去。替換

數(shù)據(jù)塊意味著更新該行的數(shù)據(jù)、地址標(biāo)志和有效位。完成

這些工作后Cache再經(jīng)過一個常規(guī)的讀命中周期，揩讀取

的數(shù)據(jù)送往CPU。

2013年5月7日星期二12時54分30秒計算機體系結(jié)構(gòu)54

2.5Cache/主存存儲器層次結(jié)構(gòu)實例

與其它任何Cache一樣，VAX-11/780的寫操作比讀操

作更為復(fù)雜。如果,那么前四步操作與讀命中時完全

一樣，第五步則是修改數(shù)據(jù)塊，并）捋數(shù)據(jù)更新部分寫入

Cache相應(yīng)行。由于VAX-11/780在寫失配時采用無寫分配

方法，因而一旦發(fā)生寫失配，CPU）捋繞過Cache直接將數(shù)

據(jù)寫入低層存儲器。

由于VAX-11/780采用直寫技術(shù)，并配有1個字長的寫

緩沖器，因而在把數(shù)據(jù)送往低層存儲器時實際是將數(shù)據(jù)送往

寫緩沖器。若寫緩沖器是空的，則數(shù)據(jù)與地址被寫入緩沖

器，整個寫操作就完成了。在寫緩沖器招數(shù)據(jù)送往主存的同

時，CPU可繼續(xù)其工作。但如果寫緩沖器是滿的，此時

Cache和CPU必須等待，直到緩沖器為空才能將數(shù)據(jù)寫

入，完成寫操作。

2013年5月7日星期二12時54分30秒計算機體系結(jié)構(gòu)55

2.Cache/主存的性能分析

與其它級別的存儲器結(jié)構(gòu)不同，Cache有時被分為獨立的指令

Cache和數(shù)據(jù)Cache。若Cache中既可以存放指令，又可以存放數(shù)

據(jù)，此時稱之為(unifiedCache)或(mixedCache)o

CPU知道送出的訪問地址是指令地址還是數(shù)據(jù)地址，因而可

以為指令Cache和數(shù)據(jù)Cache分別設(shè)置地址、數(shù)據(jù)端口，這樣

Cache和CPU之間的傳輸帶寬就增加了一倍，這招有利于指令流

水線的實現(xiàn)。指令、數(shù)據(jù)分開存放的Cache結(jié)構(gòu)的優(yōu)點是我們可

以根據(jù)程序讀取指令和訪問數(shù)據(jù)所具有的不同行為特征分別優(yōu)化

指令Cache和數(shù)據(jù)Cache,有針對性的選擇容量、塊大小、關(guān)聯(lián)

度等參數(shù)，使得整個Cache/主存存儲器層次結(jié)構(gòu)有較好的性能。

這里我們揩僅對j

S令失配率邕數(shù)據(jù)失配率的不同之處加以討論。

2013年5