5.2

Cache基本知識(shí)5.3降低Cache失效率的方法5.4

減少Cache失效開(kāi)銷(xiāo)5.1

存儲(chǔ)器的層次結(jié)構(gòu)5.5

減少命中時(shí)間5.6

主存5.7

虛擬存儲(chǔ)器5.8

進(jìn)程保護(hù)和虛存實(shí)例5.9

AlphaAXP21064存儲(chǔ)層次第五章存儲(chǔ)層次5.1.1從單級(jí)存儲(chǔ)器到多級(jí)存儲(chǔ)器1.從用戶的角度來(lái)看，存儲(chǔ)器的三個(gè)主要指標(biāo)是：

容量，速度，價(jià)格(每位價(jià)格)2.

人們對(duì)這三個(gè)指標(biāo)的期望3.

這三個(gè)指標(biāo)相互矛盾4.解決方法

采用多種存儲(chǔ)器技術(shù)，構(gòu)成存儲(chǔ)層次。

演示Ⅰ演示Ⅱ(局部性原理)5.1存儲(chǔ)器的層次結(jié)構(gòu)第五章存儲(chǔ)層次5.1.2

存儲(chǔ)層次的性能參數(shù)

C，H，TA假設(shè)：S

──容量

TA──訪問(wèn)時(shí)間

C

──每位價(jià)格下面僅考慮由M1和M2構(gòu)成的兩級(jí)存儲(chǔ)層次：

M1的參數(shù)：S1，TA1，C1

M2的參數(shù)：S2，TA2，C21.

每位價(jià)格C

C＝─────C1S1＋C2S2S1＋S25.1存儲(chǔ)器的層次結(jié)構(gòu)2.命中率H和失效率F

H＝N1/(N1＋N2)

N1

──訪問(wèn)M1的次數(shù)

N2

──訪問(wèn)M2的次數(shù)

失效率F＝1－H5.1存儲(chǔ)器的層次結(jié)構(gòu)3.平均訪問(wèn)時(shí)間TA

TA＝TA1＋(1－H)TM

或

TA＝TA1＋F

TM

TA1

──命中時(shí)間

TM

──失效開(kāi)銷(xiāo)5.1.3“Cache－主存”和“主存－輔存”層次1.從主存的角度來(lái)看

“Cache－主存”層次：彌補(bǔ)主存速度的不足

“主存－輔存”層次：彌補(bǔ)主存容量的不足2.“Cache－主存”層次

◆

主存與CPU的速度差距

5.1存儲(chǔ)器的層次結(jié)構(gòu)◆“Cache-主存”層次3.“主存－輔存”層次存儲(chǔ)層次CPU對(duì)第二級(jí)的

訪問(wèn)方式比較項(xiàng)目目的存儲(chǔ)管理實(shí)現(xiàn)

訪問(wèn)速度的比值

(第一級(jí)和第二級(jí))典型的塊(頁(yè))大小失效時(shí)CPU是否切換“Cache－主存”層次“主存－輔存”層次為了彌補(bǔ)主存速度的不足為了彌補(bǔ)主存容量的不足主要由專(zhuān)用硬件實(shí)現(xiàn)主要由軟件實(shí)現(xiàn)幾比一幾百比一幾十個(gè)字節(jié)幾百到幾千個(gè)字節(jié)可直接訪問(wèn)均通過(guò)第一級(jí)不切換切換到其他進(jìn)程“Cache－主存”與“主存－輔存”層次的區(qū)別5.1存儲(chǔ)器的層次結(jié)構(gòu)5.1.4存儲(chǔ)層次的四個(gè)問(wèn)題當(dāng)把一個(gè)塊調(diào)入高一層(靠近CPU)存儲(chǔ)器時(shí)，

可以放在哪些位置上?

(映象規(guī)則)當(dāng)所要訪問(wèn)的塊在高一層存儲(chǔ)器中時(shí)，如何

找到該塊?

(查找算法)3.

當(dāng)發(fā)生失效時(shí)，應(yīng)替換哪一塊？

(替換算法)4.

當(dāng)進(jìn)行寫(xiě)訪問(wèn)時(shí)，應(yīng)進(jìn)行哪些操作?

(寫(xiě)策略)1.

2.5.1存儲(chǔ)器的層次結(jié)構(gòu)5.2Cache基本知識(shí)1．存儲(chǔ)空間分割與地址計(jì)算5.2.1映象規(guī)則1.全相聯(lián)映象

全相聯(lián)：主存中的任一塊可以被放置到

Cache中的任意一個(gè)位置。舉例

對(duì)比：

閱覽室位置──隨便坐

特點(diǎn)：

空間利用率最高，沖突概率最低，

實(shí)現(xiàn)最復(fù)雜。2．Cache和主存分塊5.2Cache基本知識(shí)2.直接映象◆

直接映象：主存中的每一塊只能被放置到

Cache中唯一的一個(gè)位置。

舉例

(循環(huán)分配)◆

對(duì)比：閱覽室位置──只有一個(gè)位置可

以坐◆

特點(diǎn)：空間利用率最低，沖突概率最高， 實(shí)現(xiàn)最簡(jiǎn)單。◆

對(duì)于主存的第i

塊，若它映象到Cache的第

j

塊，則:

j＝imod(M)

（M為Cache的塊數(shù)）

5.2Cache基本知識(shí)◆

組相聯(lián)：主存中的每一塊可以被放置到Cache

中唯一的一個(gè)組中的任何一個(gè)位置。

舉例◆

組相聯(lián)是直接映象和全相聯(lián)的一種折衷◆

設(shè)M＝2m，則當(dāng)表示為二進(jìn)制數(shù)時(shí)，j實(shí)際

上就是i的低m位：3.組相聯(lián)映象m位ji：5.2Cache基本知識(shí)◆上述的j

和k

通常稱(chēng)為索引◆

組的選擇常采用位選擇算法

若主存第i塊映象到第k組，則:

k＝imod（G）

（G為Cache的組數(shù)）

設(shè)G＝2g，則當(dāng)表示為二進(jìn)制數(shù)時(shí)，k實(shí)

際上就是i的低g位：g

位ki：5.2Cache基本知識(shí)◆

絕大多數(shù)計(jì)算機(jī)的Cache:n≤4

想一想：相聯(lián)度一定是越大越好？◆

n路組相聯(lián)：每組中有n個(gè)塊(n＝M/G)

n稱(chēng)為相聯(lián)度。

相聯(lián)度越高，Cache空間的利用率就越高，

塊沖突概率就越低，失效率也就越低。全相聯(lián)直接映象組相聯(lián)n

(路數(shù))G

(組數(shù))MM111＜n＜M1＜G＜M5.2Cache基本知識(shí)5.2.2查找方法1.如何確定Cache中是否有所要訪問(wèn)的塊？

若有的話如何確定其位置？答案5.2Cache基本知識(shí)◆

目錄表的結(jié)構(gòu)◆

只需查找候選位置所對(duì)應(yīng)的目錄表項(xiàng)◆

并行查找與順序查找◆

提高性能的重要思想：主候選位置(MRU塊)

前瞻執(zhí)行◆

并行查找的實(shí)現(xiàn)方法：5.2Cache基本知識(shí)舉例：４路組相聯(lián)并行標(biāo)識(shí)比較（比較器的個(gè)數(shù)及位數(shù)）

相聯(lián)存儲(chǔ)器單體多字存儲(chǔ)器＋比較器

◆

４路組相聯(lián)Cache的查找過(guò)程◆

直接映象Cache的查找過(guò)程5.2.3替換算法

所要解決的問(wèn)題：當(dāng)新調(diào)入一塊，而Cache

又已被占滿時(shí)，替換哪一塊？2.FIFO3.LRU

優(yōu)點(diǎn)：失效率低

LRU和隨機(jī)法的失效率的比較1.隨機(jī)法

優(yōu)點(diǎn)：實(shí)現(xiàn)簡(jiǎn)單5.2Cache基本知識(shí)5.2.4寫(xiě)策略1.“寫(xiě)”操作所占的比例

Load指令：26％

Store指令：9％

“寫(xiě)”在所有訪存操作中所占的比例：

9％/(100％＋26％＋9％)≈7％

“寫(xiě)”在訪問(wèn)Cache操作中所占的比例：

9％/(26％＋9％)≈25％3．“寫(xiě)”訪問(wèn)有可能導(dǎo)致Cache和主存內(nèi)容的不一致2.“寫(xiě)”操作必須在確認(rèn)是命中后才可進(jìn)行5.2Cache基本知識(shí)4．兩種寫(xiě)策略

◆

寫(xiě)直達(dá)法執(zhí)行“寫(xiě)”操作時(shí)，不僅寫(xiě)入Cache，而且

也寫(xiě)入下一級(jí)存儲(chǔ)器。

◆

寫(xiě)回法執(zhí)行“寫(xiě)”操作時(shí)，只寫(xiě)入Cache。僅當(dāng)

Cache中相應(yīng)的塊被替換時(shí)，才寫(xiě)回主存。

(設(shè)置“污染位”)5.2Cache基本知識(shí)5．兩種寫(xiě)策略的比較

◆寫(xiě)回法的優(yōu)點(diǎn)：速度快，所使用的存儲(chǔ)器頻

帶較低；

◆寫(xiě)直達(dá)法的優(yōu)點(diǎn)：易于實(shí)現(xiàn)，一致性好。6.寫(xiě)緩沖器8.寫(xiě)策略與調(diào)塊

寫(xiě)回法──按寫(xiě)分配寫(xiě)直達(dá)法──不按寫(xiě)分配7.“寫(xiě)”操作時(shí)的調(diào)塊

◆

按寫(xiě)分配(寫(xiě)時(shí)取)

寫(xiě)失效時(shí)，先把所寫(xiě)單元所在的塊調(diào)入

Cache，再行寫(xiě)入。

◆

不按寫(xiě)分配(繞寫(xiě)法)

寫(xiě)失效時(shí)，直接寫(xiě)入下一級(jí)存儲(chǔ)器而不調(diào)塊。5.2Cache基本知識(shí)5.2.5Cache的結(jié)構(gòu)例子：DEC的AlphaAXP21064中的內(nèi)部數(shù)據(jù)

Cache。1.簡(jiǎn)介

容量：8KB

塊大小：32B

塊數(shù)：256

采用不按寫(xiě)分配映象方法：直接映象

“寫(xiě)”策略：寫(xiě)直達(dá)寫(xiě)緩沖器大小：4個(gè)塊5.2Cache基本知識(shí)2.結(jié)構(gòu)圖3.工作過(guò)程

◆

“讀”訪問(wèn)命中◆

“寫(xiě)”訪問(wèn)命中5.混合Cache與分離Cache

(1)優(yōu)缺點(diǎn)

(2)失效率的比較

5.2Cache基本知識(shí)◆

失效情況下的操作16KB容量1KB2KB4KB8KB32KB指令Cache3.06%失效率的比較64KB128KB數(shù)據(jù)Cache混合Cache2.26%1.78%1.10%0.64%0.39%0.15%0.02%24.61%20.57%15.94%10.19%6.47%4.82%3.77%2.88%13.34%9.78%7.24%4.57%2.87%1.99%1.36%0.95%(3)分離Cache平均失效率的計(jì)算：訪問(wèn)指令Cache的百分比×指令Cache的失效率＋訪問(wèn)數(shù)據(jù)Cache的百分比×數(shù)據(jù)Cache的失效率5.2.6Cache性能分析2.平均訪問(wèn)時(shí)間

平均訪問(wèn)時(shí)間＝命中時(shí)間＋失效率×失效開(kāi)銷(xiāo)1.失效率例5.1

假設(shè)Cache的命中時(shí)間為1個(gè)時(shí)鐘周期，失效

開(kāi)銷(xiāo)為50個(gè)時(shí)鐘周期，在混合Cache中一次load

或store操作訪問(wèn)Cache的命中時(shí)間都要增加一個(gè)

時(shí)鐘周期(因?yàn)榛旌螩ache只有一個(gè)端口，無(wú)法同

時(shí)滿足兩個(gè)請(qǐng)求。按照前一章中有關(guān)流水線的術(shù)

語(yǔ)，混合Cache會(huì)導(dǎo)致結(jié)構(gòu)沖突)，根據(jù)表5－4所

列的失效率，試問(wèn)指令Cache和數(shù)據(jù)Cache容量均為16KB的分離Cache和容量為32KB的混合Cache相

5.2Cache基本知識(shí)解：

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

分離Cache的總體失效率為：

(75%×0.64%)＋(25%×6.47%)＝2.10%

根據(jù)表5－4，容量為32KB的混合Cache的失

效率略低一些，只有1.99%.比，哪種Cache的失效率更低？又假設(shè)采用寫(xiě)直達(dá)

策略，且有一個(gè)寫(xiě)緩沖器，并且忽略寫(xiě)緩沖器引

起的等待。請(qǐng)問(wèn)上述兩種情況下平均訪存時(shí)間各

是多少？5.2Cache基本知識(shí)平均訪存時(shí)間公式可以分為指令訪問(wèn)和數(shù)據(jù)

訪問(wèn)兩部分：平均訪存時(shí)間＝指令所占的百分比×

(指令命中時(shí)間＋指令失效率×失效開(kāi)銷(xiāo))＋

數(shù)據(jù)所占的百分比×

(數(shù)據(jù)命中時(shí)間＋數(shù)據(jù)失效率×失效開(kāi)銷(xiāo))所以，兩種結(jié)構(gòu)的平均訪存時(shí)間分別為：平均訪存時(shí)間分離＝75%×(1＋0.64%×50)＋

25%×(1＋6.47%×50)

＝(75%×1.32)＋(25%×4.325)

＝0.990＋1.059＝2.055.2Cache基本知識(shí)平均訪存時(shí)間混合＝75%×(1＋1.99%×50)＋

25%×(1＋1＋1.99%×50)

＝(75%×1.995)＋(25%×2.995)

＝1.496＋0.749＝2.243.程序執(zhí)行時(shí)間

CPU時(shí)間＝(CPU執(zhí)行周期數(shù)＋存儲(chǔ)器停頓周期數(shù))

×?xí)r鐘周期時(shí)間其中，

存儲(chǔ)器停頓周期數(shù)＝訪存次數(shù)×失效率×

失效開(kāi)銷(xiāo)5.2Cache基本知識(shí)CPU時(shí)間＝IC×[CPIexe＋每條指令的平均存儲(chǔ)

器停頓周期數(shù)]×?xí)r鐘周期時(shí)間CPU時(shí)間＝IC×[CPIexe＋訪存次數(shù)/指令數(shù)×

失效率×失效開(kāi)銷(xiāo)]×?xí)r鐘周期時(shí)間5.2Cache基本知識(shí)例5.2

我們用一個(gè)和AlphaAXP類(lèi)似的機(jī)器作為

第一個(gè)例子。假設(shè)Cache失效開(kāi)銷(xiāo)為50個(gè)時(shí)鐘

周期，當(dāng)不考慮存儲(chǔ)器停頓時(shí)，所有指令的

執(zhí)行時(shí)間都是2.0個(gè)時(shí)鐘周期，Cache的失效

率為2%，平均每條指令訪存1.33次。試分析

Cache對(duì)性能的影響。考慮Cache的失效后，性能為：CPU時(shí)間有cache＝IC×(2.0＋(1.33×2%×50))

×?xí)r鐘周期時(shí)間

＝IC×3.33×?xí)r鐘周期時(shí)間CPU時(shí)間＝IC×(CPIexe＋────────)

×?xí)r鐘周期時(shí)間存儲(chǔ)器停頓周期數(shù)指令數(shù)解：5.2Cache基本知識(shí)實(shí)際CPI：3.333.33/2.0=1.67(倍)CPU時(shí)間也增加為原來(lái)的1.67倍。但若不采用Cache,則：

CPI＝2.0+50×1.33＝68.55.2Cache基本知識(shí)

考慮兩種不同組織結(jié)構(gòu)的Cache：直接映象

Cache和兩路組相聯(lián)Cache，試問(wèn)它們對(duì)CPU的性

能有何影響？先求平均訪存時(shí)間，然后再計(jì)算

CPU性能。分析時(shí)請(qǐng)用以下假設(shè)：⑴理想Cache(命中率為100％)情況下的CPI

為2.0，時(shí)鐘周期為2ns，平均每條指令

訪存1.3次。⑵兩種Cache容量均為64KB，塊大小都是32

字節(jié)。例5.35.2Cache基本知識(shí)

⑶圖5.10說(shuō)明，在組相聯(lián)Cache中，我們必須增

加一個(gè)多路選擇器，用于根據(jù)標(biāo)識(shí)匹配結(jié)果

從相應(yīng)組的塊中選擇所需的數(shù)據(jù)。因?yàn)镃PU

的速度直接與Cache命中的速度緊密相關(guān),所

以對(duì)于組相聯(lián)Cache，由于多路選擇器的存

在而使CPU的時(shí)鐘周期增加到原來(lái)的1.10倍。⑷這兩種結(jié)構(gòu)Cache的失效開(kāi)銷(xiāo)都是70ns。在

實(shí)際應(yīng)用中，應(yīng)取整為整數(shù)個(gè)時(shí)鐘周期。⑸命中時(shí)間為1個(gè)時(shí)鐘周期，64KB直接映象

Cache的失效率為1.4%，相同容量的兩路組

相聯(lián)Cache的失效率為1.0%。5.2Cache基本知識(shí)由:

平均訪存時(shí)間＝命中時(shí)間＋失效率×失效開(kāi)銷(xiāo)得:

平均訪存時(shí)間1路＝2.0＋(0.014×70)＝2.98ns

平均訪存時(shí)間2路＝2.0×1.10＋(0.010×70)＝2.90ns由:

CPU時(shí)間＝IC×(CPIexe＋每條指令的平均存儲(chǔ)器

停頓周期數(shù))×?xí)r鐘周期時(shí)間

＝IC×(CPIexe×?xí)r鐘周期時(shí)間＋

每條指令的平均存儲(chǔ)器停頓時(shí)間)解：5.2Cache基本知識(shí)CPU時(shí)間1路＝IC×(2.0×2＋(1.3×0.014×70))

＝5.27×ICCPU時(shí)間2路＝IC×(2.0×2×1.10

＋(1.3×0.010×70))

＝5.31×IC得：5.31×ICCPU時(shí)間1路─────＝─────＝1.015.27×ICCPU時(shí)間2路5.2Cache基本知識(shí)平均訪存時(shí)間＝命中時(shí)間＋失效率×失效開(kāi)銷(xiāo)可以從三個(gè)方面改進(jìn)Cache的性能：(1)降低失效率(2)減少失效開(kāi)銷(xiāo)

(3)減少Cache命中時(shí)間下面介紹15種Cache優(yōu)化技術(shù)5.2.7改進(jìn)Cache性能5.2Cache基本知識(shí)(1)強(qiáng)制性失效(Compulsorymiss)

當(dāng)?shù)谝淮卧L問(wèn)一個(gè)塊時(shí)，該塊不在

Cache中，需從下一級(jí)存儲(chǔ)器中調(diào)入Cache，

這就是強(qiáng)制性失效。

(冷啟動(dòng)失效，首次訪問(wèn)失效。)(2)容量失效(Capacitymiss)

如果程序執(zhí)行時(shí)所需的塊不能全部調(diào)

入Cache中，則當(dāng)某些塊被替換后，若又5.3降低Cache失效率的方法1.三種失效(3C)第五章存儲(chǔ)層次

重新被訪問(wèn)，就會(huì)發(fā)生失效。這種失效稱(chēng)

為容量失效。(3)沖突失效(Conflictmiss)

在組相聯(lián)或直接映象Cache中，若太多

的塊映象到同一組(塊)中，則會(huì)出現(xiàn)該組

中某個(gè)塊被別的塊替換(即使別的組或塊有

空閑位置)，然后又被重新訪問(wèn)的情況。這

就是發(fā)生了沖突失效。

(碰撞失效，干擾失效)5.3降低Cache失效率的方法2.三種失效所占的比例(SPEC92)

表5.5

5.3降低Cache失效率的方法圖示I(絕對(duì)值)圖示Ⅱ(相對(duì)值)可以看出：(1)相聯(lián)度越高，沖突失效就越少；(2)強(qiáng)制性失效和容量失效不受相聯(lián)度的影響；(3)強(qiáng)制性失效不受Cache容量的影響，但容

量失效卻隨著容量的增加而減少；(4)表中的數(shù)據(jù)符合2:1的Cache經(jīng)驗(yàn)規(guī)則，即

大小為N

的直接映象Cache的失效率約等于

大小為N/2

的兩路組相聯(lián)Cache的失效率。強(qiáng)制性失效：增加塊大小，預(yù)取

(本身很少)容量失效：增加容量

(抖動(dòng)現(xiàn)象)沖突失效：提高相聯(lián)度

(理想情況：全相聯(lián))3.減少三種失效的方法4.許多降低失效率的方法會(huì)增加命中時(shí)間或

失效開(kāi)銷(xiāo)5.3降低Cache失效率的方法5.3.1增加Cache塊大小1.失效率與塊大小的關(guān)系

(1)對(duì)于給定的Cache容量，當(dāng)塊大小增加

失效率開(kāi)始是下降，后來(lái)反而上升了；

(2)Cache容量越大，使失效率達(dá)到最低的

塊大小就越大。5.3降低Cache失效率的方法2.增加塊大小會(huì)增加失效開(kāi)銷(xiāo)3.例題例5.4

假定存儲(chǔ)系統(tǒng)在延遲40個(gè)時(shí)鐘周期后，每2個(gè)

時(shí)鐘周期能送出16個(gè)字節(jié)。即:經(jīng)過(guò)42個(gè)時(shí)鐘周期，

它可提供16個(gè)字節(jié)；經(jīng)過(guò)44個(gè)時(shí)鐘周期，可提供32

個(gè)字節(jié)；依此類(lèi)推。試問(wèn)對(duì)于表5-6中列出的各種

容量的Cache，在塊大小分別為多少時(shí)，平均訪存

時(shí)間最小？解：

解題過(guò)程

1KB、4KB、16KBCache:塊大小＝32字節(jié)

64KB、256KBCache:塊大小＝64字節(jié)5.3降低Cache失效率的方法塊大小（字節(jié)）失效開(kāi)銷(xiāo)（時(shí)鐘周期）Cache容量（字節(jié)）1K4K16K64K256K16427.3214.5992.6551.8571.45832446.8704.1862.2631.5941.30864487.6054.3602.2671.5091.2451285610.3185.3572.5511.5711.2742567216.8477.8473.3691.8281.3535.3.2提高相聯(lián)度1.采用相聯(lián)度超過(guò)8的方法實(shí)際意義不大2.2:1Cache經(jīng)驗(yàn)規(guī)則

容量為N

的直接映象Cache

≈容量為N/2的兩路組相聯(lián)Cache3.提高相聯(lián)度是以增加命中時(shí)間為代價(jià)

例如：

TTL或ECL板級(jí)Cache，兩路組相聯(lián)：

增加10％

定制的CMOSCache,兩路組相聯(lián)：

增加2％5.3降低Cache失效率的方法4.例題

假定提高相聯(lián)度會(huì)按下列比例增大處理器

時(shí)鐘周期：

時(shí)鐘周期2路＝1.10×?xí)r鐘周期1路

時(shí)鐘周期4路＝1.12×?xí)r鐘周期1路時(shí)鐘周期8路＝1.14×?xí)r鐘周期1路

假定命中時(shí)間為1個(gè)時(shí)鐘，直接映象情況

下失效開(kāi)銷(xiāo)為50個(gè)時(shí)鐘周期，而且假設(shè)不必將

失效開(kāi)銷(xiāo)取整。使用表5－5中的失效率，試問(wèn)

當(dāng)Cache為多大時(shí)，以下不等式成立？例5.55.3降低Cache失效率的方法平均訪存時(shí)間8路

<平均訪存時(shí)間4路平均訪存時(shí)間4路

<平均訪存時(shí)間2路平均訪存時(shí)間2路

<平均訪存時(shí)間1路解：

在各種相聯(lián)度的情況下，平均訪存時(shí)間分

別為：平均訪存時(shí)間8路

=

命中時(shí)間8路

+失效率8路

×失效開(kāi)銷(xiāo)8路

=1.14＋失效率8路×50

平均訪存時(shí)間4路

=1.12＋失效率4路×50

平均訪存時(shí)間2路

=1.10＋失效率2路×50

平均訪存時(shí)間1路

=1.00＋失效率1路×505.3降低Cache失效率的方法

在每種情況下的失效開(kāi)銷(xiāo)相同，都是

50個(gè)時(shí)鐘周期。把相應(yīng)的失效率代入上式，

即可得平均訪存時(shí)間。

例如，1KB的直接映象Cache的平均

訪存時(shí)間為：平均訪存時(shí)間1路

＝1.00＋(0.133×50)

＝7.65

容量為128KB的8路組相聯(lián)Cache的平均

訪存時(shí)間為：平均訪存時(shí)間8路

＝1.14＋(0.006×50)

＝1.44表5-85.3降低Cache失效率的方法Cache容量（K字節(jié)）相聯(lián)度（路）124817.656.606.225.4425.904.904.624.0944.603.953.573.1983.303.002.872.59162.452.202.122.04322.001.801.771.79641.701.601.571.591281.501.451.421.441.基本思想

在Cache和它從下一級(jí)存儲(chǔ)器調(diào)數(shù)據(jù)

的通路之間設(shè)置一個(gè)全相聯(lián)的小Cache，

用于存放被替換出去的塊(稱(chēng)為Victim)，

以備重用。工作過(guò)程5.3.3VictimCache5.3降低Cache失效率的方法

對(duì)于減小沖突失效很有效，特別是對(duì)

于小容量的直接映象數(shù)據(jù)Cache，作用尤其

明顯。

例如，項(xiàng)數(shù)為4的VictimCache:

使4KBCache的沖突失效減少20%～90%2.作用5.3降低Cache失效率的方法1.直接映象vs．組相聯(lián)5.3.4偽相聯(lián)Cache2.偽相聯(lián)Cache優(yōu)點(diǎn)缺點(diǎn)直接映象組相聯(lián)命中時(shí)間小命中時(shí)間大失效率高失效率低取直接映象及組相聯(lián)兩者的優(yōu)點(diǎn)：

命中時(shí)間小，失效率低5.3降低Cache失效率的方法(1)基本思想及工作原理(動(dòng)畫(huà)演示)

在邏輯上把直接映象Cache的空間上下

平分為兩個(gè)區(qū)。對(duì)于任何一次訪問(wèn)，偽相聯(lián)

Cache先按直接映象Cache的方式去處理。若

命中，則其訪問(wèn)過(guò)程與直接映象Cache的情

況一樣。若不命中，則再到另一區(qū)相應(yīng)的位

置去查找。若找到，則發(fā)生了偽命中，否則

就只好訪問(wèn)下一級(jí)存儲(chǔ)器。(2)快速命中與慢速命中要保證絕大多數(shù)命中都是快速命中。5.3降低Cache失效率的方法3.例題例5.6

假設(shè)當(dāng)在按直接映象找到的位置處沒(méi)有發(fā)

現(xiàn)匹配、而在另一個(gè)位置才找到數(shù)據(jù)(偽命中)

需要2個(gè)額外的周期。仍用上個(gè)例子中的數(shù)據(jù)，

問(wèn)：當(dāng)Cache容量分別為2KB和128KB時(shí)，直接

映象、兩路組相聯(lián)和偽相聯(lián)這三種組織結(jié)構(gòu)中，

哪一種速度最快？5.3降低Cache失效率的方法首先考慮標(biāo)準(zhǔn)的平均訪存時(shí)間公式：

平均訪存時(shí)間偽相聯(lián)

＝命中時(shí)間偽相聯(lián)＋失效率偽相聯(lián)×失效開(kāi)銷(xiāo)偽相聯(lián)由于：

失效率偽相聯(lián)＝失效率2路命中時(shí)間偽相聯(lián)＝命中時(shí)間1路＋偽命中率偽相聯(lián)×2；偽命中率偽相聯(lián)＝命中率2路－命中率1路＝(1－失效率2路)－(1－失效率1路)

＝失效率1路－失效率2路解：5.3降低Cache失效率的方法故：

平均訪存時(shí)間偽相聯(lián)

＝命中時(shí)間1路＋(失效率1路－失效率2路)×2

＋失效率2路×失效開(kāi)銷(xiāo)1路將表5－5中的數(shù)據(jù)代入上面的公式，得：平均訪存時(shí)間偽相聯(lián)，2KB

＝1＋(0.098－0.076)×2＋(0.076×50)

＝4.844

平均訪存時(shí)間偽相聯(lián)，128KB

＝1＋(0.010－0.007)×2＋(0.007×50)

＝1.3565.3降低Cache失效率的方法根據(jù)上一個(gè)例子中的表5－8，對(duì)于2KBCache，

可得：平均訪存時(shí)間1路＝5.90個(gè)時(shí)鐘平均訪存時(shí)間2路＝4.90個(gè)時(shí)鐘對(duì)于128KB的Cache有，可得：平均訪存時(shí)間1路＝1.50個(gè)時(shí)鐘平均訪存時(shí)間2路＝1.45個(gè)時(shí)鐘可見(jiàn)，對(duì)于這兩種Cache容量，偽相聯(lián)Cache

都是速度最快的。缺點(diǎn)：多種命中時(shí)間5.3降低Cache失效率的方法5.3.5硬件預(yù)取技術(shù)1.指令和數(shù)據(jù)都可以預(yù)取2.預(yù)取內(nèi)容既可放入Cache，也可放在

外緩沖器中

例如：指令流緩沖器3.預(yù)取效果

(1)Joppi的研究結(jié)果

◆

指令預(yù)取：(4KB，直接映象Cache,

塊大小＝16字節(jié))5.3降低Cache失效率的方法1個(gè)塊的指令流緩沖器：

捕獲15％～25％

的失效4個(gè)塊的指令流緩沖器：

捕獲50％16個(gè)塊的指令流緩沖器：捕獲72％◆

數(shù)據(jù)預(yù)取：(4KB,直接映象Cache)1個(gè)數(shù)據(jù)流緩沖器：捕獲25％的失效

還可以采用多個(gè)數(shù)據(jù)流緩沖器(2)Palacharla和Kessler的研究結(jié)果流緩沖器：既能預(yù)取指令又能預(yù)取數(shù)據(jù)對(duì)于兩個(gè)64KB四路組相聯(lián)Cache來(lái)說(shuō)：

8個(gè)流緩沖器能捕獲50％～70％的失效。5.3降低Cache失效率的方法4.例題例5.7

AlphaAXP21064采用指令預(yù)取技術(shù)，其實(shí)際

失效率是多少？若不采用指令預(yù)取技術(shù)，Alpha

APX21064的指令Cache必須為多大才能保持平均訪

存時(shí)間不變？解：

假設(shè)從預(yù)取緩沖器中找到所需指令需多花1個(gè)

時(shí)鐘周期。

平均訪存時(shí)間預(yù)取

＝命中時(shí)間＋失效率×預(yù)取命中率×1

＋失效率×(1－預(yù)取命中率)×失效開(kāi)銷(xiāo)5.3降低Cache失效率的方法假設(shè)：

預(yù)取命中率＝25％

命中時(shí)間＝1個(gè)時(shí)鐘周期失效開(kāi)銷(xiāo)＝50個(gè)時(shí)鐘周期由表5.4可知，8KB指令Cache的失效率＝1.10％故平均訪存時(shí)間預(yù)取＝1＋(1.10%×25%×1)＋

(1.10%×(1－25%)×50)

＝1＋0.00275＋0.4125

＝1.415

由公式：

平均訪問(wèn)時(shí)間＝命中時(shí)間＋失效率×失效開(kāi)銷(xiāo)5.3降低Cache失效率的方法可得相應(yīng)的失效率為：失效率＝(平均訪問(wèn)時(shí)間－命中時(shí)間)/失效開(kāi)銷(xiāo)

＝(1.451－1)/50＝0.83％8KBCache

帶預(yù)取的

8kBCache失效率1.10％0.83％16KBCache0.64％5.3降低Cache失效率的方法5.3.6由編譯器控制的預(yù)取1.預(yù)取的類(lèi)型

◆

寄存器預(yù)取：把數(shù)據(jù)取到寄存器中

◆

Cache預(yù)取：

只將數(shù)據(jù)取到Cache中

◆

故障性預(yù)取：預(yù)取時(shí)，若出現(xiàn)虛地址故障

或違反訪問(wèn)權(quán)限，就會(huì)發(fā)生異常。

◆

非故障性預(yù)取：預(yù)取時(shí)，若出現(xiàn)虛地址故

障或違反訪問(wèn)權(quán)限，并不會(huì)導(dǎo)致異常，只

是轉(zhuǎn)變?yōu)椤安活A(yù)取”。由編譯器加入預(yù)取指令，在數(shù)據(jù)被用到之前

發(fā)出預(yù)取請(qǐng)求。5.3降低Cache失效率的方法4.例題2.在預(yù)取數(shù)據(jù)的同時(shí)，處理器應(yīng)能繼續(xù)執(zhí)行

只有這樣，預(yù)取才有意義。非阻塞Cache(非鎖定Cache)3.

循環(huán)是預(yù)取優(yōu)化的主要對(duì)象

失效開(kāi)銷(xiāo)小時(shí)：循環(huán)體展開(kāi)1～2次

失效開(kāi)銷(xiāo)大時(shí)：循環(huán)體展開(kāi)許多次5.3降低Cache失效率的方法例5.8

對(duì)于下面的程序，判斷哪些訪問(wèn)可能會(huì)導(dǎo)致

數(shù)據(jù)Cache失效。然后，加入預(yù)取指令以減少失

效。最后，計(jì)算所執(zhí)行的預(yù)取指令的條數(shù)以及通

過(guò)預(yù)取避免的失效次數(shù)。假定：

(1)我們用的是一個(gè)容量為8KB、塊大小為

16B的直接映象Cache，它采用寫(xiě)回法并

且按寫(xiě)分配。

(2)a、b分別為3×100(3行100列)和101×3

的雙精度浮點(diǎn)數(shù)組，每個(gè)元素都是8個(gè)

字節(jié)。當(dāng)程序開(kāi)始執(zhí)行時(shí)，這些數(shù)據(jù)都

不在Cache內(nèi)。5.3降低Cache失效率的方法for(i＝0;i<3;i＝i＋1)for(j＝0;j<100;j＝j(luò)＋1)a[i][j]＝b[j][0]×b[j＋1][0];解：(1)計(jì)算過(guò)程(2)失效情況總的失效次數(shù)＝251次

(3)改進(jìn)后的程序5.3降低Cache失效率的方法for(j＝0，j＜100；j＝j(luò)＋1){prefetch(b[j＋7][0]);

/*

預(yù)取7次循環(huán)后所需的b(j,0)*/prefetch(a[0][j＋7]);

/*

預(yù)取7次循環(huán)后所需的a(0,j)*/a[0][j]＝b[j][0]*b[j＋1][0]

}for(i＝1;i<3;i＝i＋1){for(j＝0;j<100;j＝j(luò)＋1)prefetch(a[i][j＋7]);

/*

預(yù)取7次循環(huán)后所需的a(i,j)*/a[i][j]＝b[j][0]*b[j＋1][0];

}5.3降低Cache失效率的方法例5．9

在以下條件下，計(jì)算例5.8中所節(jié)約的時(shí)間：

(1)忽略指令Cache失效，并假設(shè)數(shù)據(jù)Cache

無(wú)沖突失效和容量失效。

(2)假設(shè)預(yù)取可以被重疊或與Cache失效重

疊執(zhí)行，從而能以最大的存儲(chǔ)帶寬傳送

數(shù)據(jù)。

(3)不考慮Cache失效時(shí)，修改前的循環(huán)每7

個(gè)時(shí)鐘周期循環(huán)一次。修改后的程序中，失效情況

總的失效次數(shù)＝19次5.3降低Cache失效率的方法解：

修改前：

循環(huán)時(shí)間＝300×7＝2100

失效開(kāi)銷(xiāo)＝251×50＝12550/146502100＋12550＝14650

第一個(gè)預(yù)取循環(huán)每9個(gè)時(shí)鐘周期循環(huán)一次，

而第二個(gè)預(yù)取循環(huán)每8個(gè)時(shí)鐘周期循環(huán)一

次(包括外層for循環(huán)的開(kāi)銷(xiāo))。

(4)一次失效需50個(gè)時(shí)鐘周期。5.3降低Cache失效率的方法

修改后：

循環(huán)時(shí)間＝100×9＋200×8＝2500

失效時(shí)間＝19×50＝9502500＋950＝3450

加速比＝14650/3450＝4.25.3降低Cache失效率的方法5.3.7編譯器優(yōu)化2KBCache:

降低50％8KBCache：降低75%1.基本思想

在編譯時(shí)，對(duì)程序中的指令和數(shù)據(jù)進(jìn)行

重新組織，以降低Cache失效率。2.McFaring發(fā)現(xiàn)：通過(guò)對(duì)指令進(jìn)行重新排序，

可有效地降低指令Cache的失效率。5.3降低Cache失效率的方法3.數(shù)據(jù)對(duì)存儲(chǔ)位置的限制比指令的少，因此

更便于優(yōu)化。

通過(guò)把數(shù)據(jù)重新組織，使得在一塊數(shù)

據(jù)被從Cache替換出去之前，能最大限度

利用其中的數(shù)據(jù)(訪問(wèn)次數(shù)最多)

(1)數(shù)組合并

舉例：

/*修改前*/

intval[SIZE];intkey[SIZE];5.3降低Cache失效率的方法(2)內(nèi)外循環(huán)交換

舉例：

/*

修改前*/

for(j＝0;j<100;j＝j(luò)＋1)for(i＝0;i<5000;i＝i＋1)x[i][j]＝2*x[i][j];

/*修改后*/

structmerge{intval;intkey;

};structmergemerged_array[size];5.3降低Cache失效率的方法(3)循環(huán)融合

舉例：

/*

修改前*/for(i＝0;i<N;i＝i＋1)for(j＝0;j<N;j＝j(luò)＋1)a[i][j]＝1/b[i][j]*c[i][j];/*

修改后*/

for(i＝0;i<100;i＝i＋1)for(j＝0;j<000;j＝j(luò)＋1)x[i][j]＝2*x[i][j];5.3降低Cache失效率的方法

/*

修改后*/for(i＝0;i<N;i＝i＋1)for(j＝0;j<N;j＝j(luò)＋1){

a[i][j]＝1/b[i][j]*c[i][j];d[i][j]＝a[i][j]＋c[i][j];}for(i＝0;i<N;i＝i＋1)for(j＝0;j<N;j＝j(luò)＋1)d[i][j]＝a[i][j]＋c[i][j];(4)分塊

把對(duì)數(shù)組的整行或整列訪問(wèn)改為按塊進(jìn)行。5.3降低Cache失效率的方法

舉例：

/*

修改前*/

for(i＝0;i<N;i＝i＋1)for(j＝0;j<N;j＝j(luò)＋1){r＝0;for(k＝0;k<N;k＝k＋1){r＝r＋y[i][k]*z[k][j];

}x[i][j]＝r;

}計(jì)算過(guò)程

失效次數(shù)：2N3＋N25.3降低Cache失效率的方法/*

修改后*/for(jj＝0;jj<N;jj＝j(luò)j＋1)for(kk＝0;kk<N;kk＝kk＋1)for(i＝0;i<N;i＝i＋1)for(j＝j(luò)j;j<min(jj＋B－1,N);j＝j(luò)＋1){r＝0;for(k＝kk;k<min(kk＋B－1,N);k＝k＋1){

r＝r＋y[i][k]*z[k][j];

}x[i][j]＝x[i][j]＋r;}計(jì)算過(guò)程

失效次數(shù)：2N3/B

＋N25.3降低Cache失效率的方法5.4.1讓讀失效優(yōu)先于寫(xiě)5.4減少Cache失效開(kāi)銷(xiāo)1.Cache中的寫(xiě)緩沖器導(dǎo)致對(duì)存儲(chǔ)器訪問(wèn)的

復(fù)雜化2.解決問(wèn)題的方法(讀失效的處理)

◆

推遲對(duì)讀失效的處理

(缺點(diǎn)：讀失效的開(kāi)銷(xiāo)增加，如50％)

◆

檢查寫(xiě)緩沖器中的內(nèi)容3.在寫(xiě)回法Cache中，也可采用寫(xiě)緩沖器第五章存儲(chǔ)層次5.4.2子塊放置技術(shù)1.為減少標(biāo)識(shí)的位數(shù)，可采用增加塊大小的

方法，但這會(huì)增加失效開(kāi)銷(xiāo)，故應(yīng)采用子

塊放置技術(shù)。2.子塊放置技術(shù)：把Cache塊進(jìn)一步劃分為更

小的塊(子塊)，并給每個(gè)子塊賦予一位有

效位，用于指明該子塊中的數(shù)據(jù)是否有效。

Cache與下一級(jí)存儲(chǔ)器之間以子塊為單位傳

送數(shù)據(jù)。但標(biāo)識(shí)仍以塊為單位。3.舉例(動(dòng)畫(huà)演示)5.4減少Cache失效開(kāi)銷(xiāo)5.4.3請(qǐng)求字處理技術(shù)1.請(qǐng)求字

從下一級(jí)存儲(chǔ)器調(diào)入Cache的塊中，只有

一個(gè)字是立即需要的。這個(gè)字稱(chēng)為請(qǐng)求字。

2.應(yīng)盡早把請(qǐng)求字發(fā)送給CPU

◆

盡早重啟動(dòng)：調(diào)塊時(shí)，從塊的起始位置開(kāi)

始讀起。一旦請(qǐng)求字到達(dá)，就立即發(fā)送給

CPU，讓CPU繼續(xù)執(zhí)行。

◆

請(qǐng)求字優(yōu)先：調(diào)塊時(shí)，從請(qǐng)求字所在的位

置讀起。這樣，第一個(gè)讀出的字便是請(qǐng)求

字。將之立即發(fā)送給CPU。5.4減少Cache失效開(kāi)銷(xiāo)3.這種技術(shù)在以下情況下效果不大：

◆

Cache塊較小

◆

下一條指令正好訪問(wèn)同一Cache塊的另

一部分5.4減少Cache失效開(kāi)銷(xiāo)5.4.4非阻塞Cache技術(shù)1.非阻塞Cache：Cache失效時(shí)仍允許CPU進(jìn)行

其它的命中訪問(wèn)。即允許“失效下命中”。2.進(jìn)一步提高性能：“多重失效下命中”

“失效下失效”

(存儲(chǔ)器必須能夠處理多個(gè)失效)3.重疊失效個(gè)數(shù)對(duì)平均訪問(wèn)時(shí)間的影響5.4減少Cache失效開(kāi)銷(xiāo)非阻塞Cache平均存儲(chǔ)器等待時(shí)間

與阻塞Cache的比值12浮點(diǎn)程序76％51％6439％整數(shù)程序81％78％78％重疊失效個(gè)數(shù)5.4減少Cache失效開(kāi)銷(xiāo)

對(duì)于圖5.18所描述的Cache，在兩路組相聯(lián)和

“一次失效下命中”這兩種措施中，哪一種對(duì)浮

點(diǎn)程序更重要？對(duì)整數(shù)程序的情況如何？

假設(shè)8KB數(shù)據(jù)Cache的平均失效率為：

對(duì)于浮點(diǎn)程序，直接映象Cache為11.4%，兩路

組相聯(lián)Cache為10.7%；

對(duì)于整數(shù)程序，直接映象Cache為7.4%，兩路

組相聯(lián)Cache為6.0%。并且假設(shè)平均存儲(chǔ)器等待時(shí)

間是失效率和失效開(kāi)銷(xiāo)的積，失效開(kāi)銷(xiāo)為16個(gè)時(shí)鐘

周期。例5.115.4減少Cache失效開(kāi)銷(xiāo)對(duì)于浮點(diǎn)程序，平均存儲(chǔ)器等待時(shí)間為：

失效率直接映象×失效開(kāi)銷(xiāo)＝11.4%×16＝1.82

失效率兩路組相聯(lián)×失效開(kāi)銷(xiāo)＝10.7%×16＝1.711.71/1.82＝0.94

對(duì)于整數(shù)程序：

失效率直接映象×失效開(kāi)銷(xiāo)＝7.4%×16＝1.18

失效率兩路組相聯(lián)×失效開(kāi)銷(xiāo)＝6.0%×16＝0.960.96/1.18=0.81解：5.4減少Cache失效開(kāi)銷(xiāo)5.4.5采用兩級(jí)Cache1.應(yīng)把Cache做得更快？還是更大？

答案：二者兼顧，再增加一級(jí)Cache

◆

第一級(jí)Cache(L1)小而快

◆

第二級(jí)Cache(L2)容量大2.性能分析

平均訪問(wèn)時(shí)間

＝命中時(shí)間L1＋失效率L1×失效開(kāi)銷(xiāo)L1

＝命中時(shí)間L1＋失效率L1×

(命中時(shí)間L2＋失效率L2×失效開(kāi)銷(xiāo)L2)5.4減少Cache失效開(kāi)銷(xiāo)3.局部失效率與全局失效率

局部失效率＝該級(jí)Cache的失效次數(shù)/到達(dá)

該級(jí)Cache的訪問(wèn)次數(shù)例如：上述式子中的失效率L2

全局失效率＝該級(jí)Cache的失效次數(shù)/CPU

發(fā)出的訪存的總次數(shù)

全局失效率L2＝失效率L1×失效率L2

評(píng)價(jià)第二級(jí)Cache時(shí)，應(yīng)使用全局失效率

這個(gè)指標(biāo)。5.4減少Cache失效開(kāi)銷(xiāo)例5.12

假設(shè)在1000次訪存中，第一級(jí)Cache失效40次，第二級(jí)Cache失效20次。試問(wèn)：在這種情況下，該Cache系統(tǒng)的局部失效率和全局失效率各是多少？

解

第一級(jí)Cache的失效率（全局和局部）是40/1000，即4%；第二級(jí)Cache的局部失效率是20/40，即50%，第二級(jí)Cache的全局失效率是20/1000，即2%。

5.4減少Cache失效開(kāi)銷(xiāo)4.當(dāng)?shù)诙?jí)Cache比第一級(jí)Cache大得多時(shí)，兩

級(jí)Cache的全局失效率與容量和第二級(jí)Cache

相同的單級(jí)Cache的失效率非常接近。

5.第二級(jí)Cache的參數(shù)

第二級(jí)Cache不會(huì)影響CPU的時(shí)鐘頻率，

因此其設(shè)計(jì)有更大的考慮空間。

兩個(gè)問(wèn)題：

◆

能否降低CPI中的平均訪存時(shí)間部分？

◆

成本是多少？

(1)容量

第二級(jí)Cache的容量一般比第一級(jí)的

大許多，如512KB。5.4減少Cache失效開(kāi)銷(xiāo)(2)相聯(lián)度

第二級(jí)Cache可采用較高的相聯(lián)度或偽

相聯(lián)方法例5.13

給出有關(guān)第二級(jí)Cache的以下數(shù)據(jù)：⑴兩路組相聯(lián)使命中時(shí)間增加10%×CPU時(shí)鐘周期⑵對(duì)于直接映象，命中時(shí)間L2＝10個(gè)時(shí)鐘周期⑶對(duì)于直接映象，局部失效率L2＝25%⑷對(duì)于兩路組相聯(lián)，局部失效率L2＝20%⑸失效開(kāi)銷(xiāo)L2＝50個(gè)時(shí)鐘周期試問(wèn)第二級(jí)Cache的相聯(lián)度對(duì)失效開(kāi)銷(xiāo)的影響如何？5.4減少Cache失效開(kāi)銷(xiāo)解：

對(duì)于一個(gè)直接映象的第二級(jí)Cache來(lái)說(shuō)，

第一級(jí)Cache的失效開(kāi)銷(xiāo)為：失效開(kāi)銷(xiāo)直接映象，L1

＝10＋25%×50＝22.5個(gè)時(shí)鐘周期對(duì)于兩路組相聯(lián)第二級(jí)Cache來(lái)說(shuō)，命中

時(shí)間增加了10%(0.1)個(gè)時(shí)鐘周期，故第一級(jí)

Cache的失效開(kāi)銷(xiāo)為：失效開(kāi)銷(xiāo)兩路組相聯(lián)，L1

＝10.1＋20%×50＝20.1個(gè)時(shí)鐘周期

把第二級(jí)Cache的命中時(shí)間取整，得10或11，

則：5.4減少Cache失效開(kāi)銷(xiāo)

失效開(kāi)銷(xiāo)兩路組相聯(lián)，L1

＝10＋20%×50＝20.0個(gè)時(shí)鐘周期

失效開(kāi)銷(xiāo)兩路組相聯(lián)，L1

＝11＋20%×50＝21.0個(gè)時(shí)鐘周期故對(duì)于第二級(jí)Cache來(lái)說(shuō)，兩路組相聯(lián)優(yōu)于

直接映象。(3)塊大小

第二級(jí)Cache可采用較大的塊，

如64、128、256字節(jié)。圖5.19

為減少平均訪存時(shí)間，可以讓容量較小

的第一級(jí)Cache采用較小的塊，而讓容量較大

的第二級(jí)Cache采用較大的塊。5.4減少Cache失效開(kāi)銷(xiāo)5.5減少命中時(shí)間2.應(yīng)使Cache足夠小，以便可以與CPU一起放

在同一塊芯片上。

命中時(shí)間直接影響到處理器的時(shí)鐘頻率。在

當(dāng)今的許多計(jì)算機(jī)中，往往是Cache的訪問(wèn)時(shí)間

限制了處理器的時(shí)鐘頻率。1.硬件越簡(jiǎn)單，速度就越快；5.5.1容量小、結(jié)構(gòu)簡(jiǎn)單的Cache第五章存儲(chǔ)層次1.虛擬Cache

訪問(wèn)Cache的索引以及Cache中的標(biāo)識(shí)都

是虛擬地址(一部分)。2.并非都采用虛擬Cache(為什么?)3.虛擬Cache的清空問(wèn)題5.5.2虛擬Cache解決方法：在地址標(biāo)識(shí)中增加PID字段

(進(jìn)程標(biāo)識(shí)符)三種情況下失效率的比較

單進(jìn)程，PIDs，清空

PIDs與單進(jìn)程相比：＋0.3％～＋0.6％

PIDs與清空相比：－0.6％～－4.3%5.5減少命中時(shí)間4.同義和別名

解決方法：反別名法,頁(yè)著色5.虛擬索引＋物理標(biāo)識(shí)

優(yōu)點(diǎn)：兼得虛擬Cache和物理Cache的好處

局限性：Cache容量受到限制

(頁(yè)內(nèi)位移)

Cache容量≤頁(yè)大小×相聯(lián)度6.舉例：IBM3033的Cache

頁(yè)大小＝4KB

相聯(lián)度＝165.5減少命中時(shí)間5.5.3寫(xiě)操作流水化

(圖5.22)

Cache容量＝16×4KB＝64KB7.另一種方法：硬件散列變換

頁(yè)地址

地址標(biāo)識(shí)頁(yè)內(nèi)位移索引塊內(nèi)位移31121105.5.4Cache優(yōu)化技術(shù)總結(jié)

(表5-9)5.5減少命中時(shí)間優(yōu)化技術(shù)失效率失效開(kāi)銷(xiāo)命中時(shí)間硬件復(fù)雜度評(píng)價(jià)增加塊大小+-

0實(shí)現(xiàn)容易；RS/6000550采用了128字節(jié)提高相聯(lián)度+

-1MIPSR10000為4路組相聯(lián)VictimCache+

2HP7200中采用了類(lèi)似的技術(shù)偽相聯(lián)Cache+

2已應(yīng)用于MIPSR10000的第二級(jí)Cache硬件預(yù)取指令和數(shù)據(jù)+

2數(shù)據(jù)預(yù)取比較困難；僅被幾臺(tái)機(jī)器采用，如：Alpha21064編譯器控制的預(yù)取+

3需采用非阻塞cache；有幾種機(jī)器支持它用編譯技術(shù)減少Cache失效次數(shù)

+

0向軟件提出了新要求；有些機(jī)器提供了編譯器選項(xiàng)使讀失效優(yōu)先級(jí)高于寫(xiě)

+

1在單處理機(jī)上實(shí)現(xiàn)容易，被廣泛使用子塊調(diào)入

+

1主要用于減少標(biāo)識(shí)的數(shù)目盡早重啟動(dòng)和關(guān)鍵字優(yōu)先

+

2已應(yīng)用于MIPSR10000和IBM620非阻塞Cache

+

3已應(yīng)用于Alpha21064和R10000中第二級(jí)Cache

+

2硬件代價(jià)大；兩級(jí)Cache的塊大小不同時(shí)實(shí)現(xiàn)困難；被廣泛采用容量小且結(jié)構(gòu)簡(jiǎn)單的Cache-

+0實(shí)現(xiàn)容易，被廣泛使用避免在對(duì)Cache進(jìn)行索引時(shí)進(jìn)行地址轉(zhuǎn)換

+2對(duì)于小容量Cache來(lái)說(shuō)實(shí)現(xiàn)容易，已應(yīng)用于Alpha21064流水化寫(xiě)

+1已應(yīng)用于Alpha210641.主存的主要性能指標(biāo)：延遲和帶寬2.以往：

Cache主要關(guān)心延遲，I/O主要關(guān)心帶寬現(xiàn)在：Cache關(guān)心兩者下面討論幾種能提高主存性能的存儲(chǔ)器組織技術(shù)在下面的討論中，我們以處理Cache失效為例來(lái)說(shuō)明各種存儲(chǔ)器組織結(jié)構(gòu)的好處。5.6主存第五章存儲(chǔ)層次◆

增加Cache塊大小能利用主存帶寬增加所帶

來(lái)的好處

在以下的討論中，我們假設(shè)基本存儲(chǔ)

器結(jié)構(gòu)的性能為：5.6主存

送地址需4個(gè)時(shí)鐘周期每個(gè)字的訪問(wèn)時(shí)間為24個(gè)時(shí)鐘周期傳送一個(gè)字的數(shù)據(jù)需4個(gè)時(shí)鐘周期◆

為了減少失效開(kāi)銷(xiāo)TM，應(yīng)該：

減少主存延遲提高主存帶寬

如果Cache大小為4個(gè)字，則：

失效開(kāi)銷(xiāo)＝4×(4＋24＋4)

＝4×32＝128(時(shí)鐘周期)

帶寬＝16/128＝0.0125(字節(jié)/時(shí)鐘周期)1.增加存儲(chǔ)器的寬度

◆

性能舉例

(參照前面的假設(shè))

當(dāng)寬度為4個(gè)字時(shí)：

失效開(kāi)銷(xiāo)＝1×32(周期)

帶寬＝0.5(字節(jié)/周期)5.6主存

◆

缺點(diǎn)：

5.6主存

增加CPU和存儲(chǔ)器之間的連接通路的寬度

CUP和Cache之間有一個(gè)多路選擇器擴(kuò)充主存的最小增量增加了相應(yīng)的倍數(shù)寫(xiě)入有可能變得復(fù)雜◆

舉例：

DEC的AlphaAxp21064：256位寬2.采用簡(jiǎn)單的多體交叉存儲(chǔ)器

在存儲(chǔ)系統(tǒng)中采用多個(gè)DRAM，并利用它們

潛在的并行性。◆

存儲(chǔ)器的各個(gè)體一般是按字交叉的交叉存儲(chǔ)器（interleavedmemory）

通常是指存儲(chǔ)器的各個(gè)體是按字交叉的。字交叉存儲(chǔ)器非常適合于處理：

Cache讀失效，寫(xiě)回法Cache中的寫(xiě)回

性能舉例：(參照前面的假設(shè))

失效開(kāi)銷(xiāo)＝4＋24＋4×4＝44(周期)

帶寬＝0.4(字節(jié)/周期)5.6主存

假設(shè)四個(gè)存儲(chǔ)體的地址是在字一級(jí)交叉的，即存儲(chǔ)體0中每個(gè)字的地址對(duì)4取模都是0，體1中每個(gè)字的地址對(duì)4取模都是1，依此類(lèi)推。04812地址體015913地址體1261014地址體2371115地址體3

假設(shè)某臺(tái)機(jī)器的特性及其Cache的性能為：

·

塊大小為1個(gè)字

·

存儲(chǔ)器總線寬度為1個(gè)字

·Cache失效率為3%

·

平均每條指令訪存1.2次

·Cache失效開(kāi)銷(xiāo)為32個(gè)時(shí)鐘周期(和上面相同)

·

平均CPI(忽略Cache失效)為2

試問(wèn)多體交叉和增加存儲(chǔ)器寬度對(duì)提高性能各

有何作用？如果當(dāng)把Cache塊大小變?yōu)?個(gè)字時(shí)，失效率例5.145.6主存

降為2%；塊大小變?yōu)?個(gè)字時(shí)，失效率降為1%。

根據(jù)5.6.2小節(jié)中給出的訪問(wèn)時(shí)間，求在采用

2路、4路多體交叉存取以及將存儲(chǔ)器和總線寬

度增加一倍時(shí)，性能分別提高多少？解：

在改變前的機(jī)器中，Cache塊大小為一個(gè)

字，其CPI為

2＋(1.2×3%×32)＝3.15

當(dāng)將塊大小增加為2個(gè)字時(shí)，在下面三種

情況下的CPI分別為：5.6主存32位總線和存儲(chǔ)器，不采用多體交叉：

2＋(1.2×2%×2×32)＝3.5432位總線和存儲(chǔ)器，采用多體交叉：

2＋(1.2×2%×(4＋24＋8))＝2.86

性能提高了10%64位總線和存儲(chǔ)器，不采用多體交叉：

2＋(1.2×2%×1×32)＝2.77

性能提高了14%如果將塊大小增加到4個(gè)字節(jié)，則：32位總線和存儲(chǔ)器，不采用多體交叉：

2＋(1.2×1%×4×32)＝3.545.6主存◆

存儲(chǔ)體的數(shù)目

體的數(shù)目≥訪問(wèn)體中一個(gè)字所需的時(shí)鐘周期32位總線和存儲(chǔ)器，采用多體交叉：

2＋(1.2×1%×(4＋24＋16))＝2.53

性能提高了25%64位總線和存儲(chǔ)器，不采用多體交叉：

2＋(1.2×1%×2×32)＝2.77

性能提高了14%3.獨(dú)立存儲(chǔ)體

設(shè)置多個(gè)存儲(chǔ)控制器，使多個(gè)體能獨(dú)立操

作，以便能同時(shí)進(jìn)行多個(gè)獨(dú)立的訪存。5.6主存◆

每個(gè)體有獨(dú)立的地址線

(動(dòng)畫(huà)演示)◆

非阻塞Cache與多體結(jié)構(gòu)◆

體和超體將存儲(chǔ)器分為若干個(gè)獨(dú)立的存儲(chǔ)體，而每個(gè)獨(dú)立存儲(chǔ)體內(nèi)又劃分為若干個(gè)按字交叉方式工作的體。

5.6主存4.避免存儲(chǔ)體沖突

◆

體沖突：

兩個(gè)請(qǐng)求要訪問(wèn)同一個(gè)體

◆

減少?zèng)_突：采用許多體例如：NECSX/3最多128個(gè)體

這種方法存在問(wèn)題。

5.6主存

假如我們有128個(gè)存儲(chǔ)體，按字交叉方式工作，并執(zhí)行以下程序：

intx[256][512];for(j=0;j<512;j=j+1)for(i=0;i<256;i=i+1)x[i][j]=2*x[i][j];

因?yàn)?12是128的整數(shù)倍，同一列中的所有元素都在同一個(gè)體內(nèi)，無(wú)論CPU或存儲(chǔ)系統(tǒng)多么高級(jí)，該程序都會(huì)在數(shù)據(jù)Cache失效時(shí)暫停。5.6主存◆

解決體沖突的方法◆

舉例

(表5-10)

軟件方法(編譯器)

循環(huán)交換優(yōu)化 擴(kuò)展數(shù)組的大小，使之不是2的冪。硬件方法

使體數(shù)為素?cái)?shù)。

當(dāng)存儲(chǔ)體數(shù)為素?cái)?shù)，且為2的冪減1時(shí)，