計算機系統結構-5-存儲層次課件

5.2

Cache基本知識5.3降低Cache失效率的方法5.4

減少Cache失效開銷5.1

存儲器的層次結構5.5

減少命中時間5.6

主存5.7

虛擬存儲器5.8

進程保護和虛存實例5.9

AlphaAXP21064存儲層次第五章存儲層次5.1.1從單級存儲器到多級存儲器1.從用戶的角度來看，存儲器的三個主要指標是：

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

人們對這三個指標的期望3.

這三個指標相互矛盾4.解決方法

采用多種存儲器技術，構成存儲層次。

演示Ⅰ演示Ⅱ(局部性原理)5.1存儲器的層次結構第五章存儲層次5.1.2

存儲層次的性能參數

C，H，TA假設：S

──容量

TA──訪問時間

C

──每位價格下面僅考慮由M1和M2構成的兩級存儲層次：

M1的參數：S1，TA1，C1

M2的參數：S2，TA2，C21.

每位價格C

C＝─────C1S1＋C2S2S1＋S25.1存儲器的層次結構2.命中率H和失效率F

H＝N1/(N1＋N2)

N1

──訪問M1的次數

N2

──訪問M2的次數

失效率F＝1－H5.1存儲器的層次結構3.平均訪問時間TA

TA＝TA1＋(1－H)TM

或

TA＝TA1＋F

TM

TA1

──命中時間

TM

──失效開銷5.1.3“Cache－主存”和“主存－輔存”層次1.從主存的角度來看

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

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

◆

主存與CPU的速度差距

5.1存儲器的層次結構◆“Cache-主存”層次3.“主存－輔存”層次存儲層次CPU對第二級的

訪問方式比較項目目的存儲管理實現

訪問速度的比值

(第一級和第二級)典型的塊(頁)大小失效時CPU是否切換“Cache－主存”層次“主存－輔存”層次為了彌補主存速度的不足為了彌補主存容量的不足主要由專用硬件實現主要由軟件實現幾比一幾百比一幾十個字節幾百到幾千個字節可直接訪問均通過第一級不切換切換到其他進程“Cache－主存”與“主存－輔存”層次的區別5.1存儲器的層次結構5.1.4存儲層次的四個問題當把一個塊調入高一層(靠近CPU)存儲器時，

可以放在哪些位置上?

(映象規則)當所要訪問的塊在高一層存儲器中時，如何

找到該塊?

(查找算法)3.

當發生失效時，應替換哪一塊？

(替換算法)4.

當進行寫訪問時，應進行哪些操作?

(寫策略)1.

2.5.1存儲器的層次結構5.2Cache基本知識1．存儲空間分割與地址計算5.2.1映象規則1.全相聯映象

全相聯：主存中的任一塊可以被放置到

Cache中的任意一個位置。舉例

對比：

閱覽室位置──隨便坐

特點：

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

實現最復雜。2．Cache和主存分塊5.2Cache基本知識2.直接映象◆

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

Cache中唯一的一個位置。

舉例

(循環分配)◆

對比：閱覽室位置──只有一個位置可

以坐◆

特點：空間利用率最低，沖突概率最高， 實現最簡單。◆

對于主存的第i

塊，若它映象到Cache的第

j

塊，則:

j＝imod(M)

（M為Cache的塊數）

5.2Cache基本知識◆

組相聯：主存中的每一塊可以被放置到Cache

中唯一的一個組中的任何一個位置。

舉例◆

組相聯是直接映象和全相聯的一種折衷◆

設M＝2m，則當表示為二進制數時，j實際

上就是i的低m位：3.組相聯映象m位ji：5.2Cache基本知識◆上述的j

和k

通常稱為索引◆

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

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

k＝imod（G）

（G為Cache的組數）

設G＝2g，則當表示為二進制數時，k實

際上就是i的低g位：g

位ki：5.2Cache基本知識◆

絕大多數計算機的Cache:n≤4

想一想：相聯度一定是越大越好？◆

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

n稱為相聯度。

相聯度越高，Cache空間的利用率就越高，

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

(路數)G

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

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

目錄表的結構◆

只需查找候選位置所對應的目錄表項◆

并行查找與順序查找◆

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

前瞻執行◆

并行查找的實現方法：5.2Cache基本知識舉例：４路組相聯并行標識比較（比較器的個數及位數）

相聯存儲器單體多字存儲器＋比較器

◆

４路組相聯Cache的查找過程◆

直接映象Cache的查找過程5.2.3替換算法

所要解決的問題：當新調入一塊，而Cache

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

優點：失效率低

LRU和隨機法的失效率的比較1.隨機法

優點：實現簡單5.2Cache基本知識5.2.4寫策略1.“寫”操作所占的比例

Load指令：26％

Store指令：9％

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

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

“寫”在訪問Cache操作中所占的比例：

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

◆

寫直達法執行“寫”操作時，不僅寫入Cache，而且

也寫入下一級存儲器。

◆

寫回法執行“寫”操作時，只寫入Cache。僅當

Cache中相應的塊被替換時，才寫回主存。

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

◆寫回法的優點：速度快，所使用的存儲器頻

帶較低；

◆寫直達法的優點：易于實現，一致性好。6.寫緩沖器8.寫策略與調塊

寫回法──按寫分配寫直達法──不按寫分配7.“寫”操作時的調塊

◆

按寫分配(寫時取)

寫失效時，先把所寫單元所在的塊調入

Cache，再行寫入。

◆

不按寫分配(繞寫法)

寫失效時，直接寫入下一級存儲器而不調塊。5.2Cache基本知識5.2.5Cache的結構例子：DEC的AlphaAXP21064中的內部數據

Cache。1.簡介

容量：8KB

塊大小：32B

塊數：256

采用不按寫分配映象方法：直接映象

“寫”策略：寫直達寫緩沖器大小：4個塊5.2Cache基本知識2.結構圖3.工作過程

◆

“讀”訪問命中◆

“寫”訪問命中5.混合Cache與分離Cache

(1)優缺點

(2)失效率的比較

5.2Cache基本知識◆

失效情況下的操作16KB容量1KB2KB4KB8KB32KB指令Cache3.06%失效率的比較64KB128KB數據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平均失效率的計算：訪問指令Cache的百分比×指令Cache的失效率＋訪問數據Cache的百分比×數據Cache的失效率5.2.6Cache性能分析2.平均訪問時間

平均訪問時間＝命中時間＋失效率×失效開銷1.失效率例5.1

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

開銷為50個時鐘周期，在混合Cache中一次load

或store操作訪問Cache的命中時間都要增加一個

時鐘周期(因為混合Cache只有一個端口，無法同

時滿足兩個請求。按照前一章中有關流水線的術

語，混合Cache會導致結構沖突)，根據表5－4所

列的失效率，試問指令Cache和數據Cache容量均為16KB的分離Cache和容量為32KB的混合Cache相

5.2Cache基本知識解：

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

分離Cache的總體失效率為：

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

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

效率略低一些，只有1.99%.比，哪種Cache的失效率更低？又假設采用寫直達

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

起的等待。請問上述兩種情況下平均訪存時間各

是多少？5.2Cache基本知識平均訪存時間公式可以分為指令訪問和數據

訪問兩部分：平均訪存時間＝指令所占的百分比×

(指令命中時間＋指令失效率×失效開銷)＋

數據所占的百分比×

(數據命中時間＋數據失效率×失效開銷)所以，兩種結構的平均訪存時間分別為：平均訪存時間分離＝75%×(1＋0.64%×50)＋

25%×(1＋6.47%×50)

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

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

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

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

＝1.496＋0.749＝2.243.程序執行時間

CPU時間＝(CPU執行周期數＋存儲器停頓周期數)

×時鐘周期時間其中，

存儲器停頓周期數＝訪存次數×失效率×

失效開銷5.2Cache基本知識CPU時間＝IC×[CPIexe＋每條指令的平均存儲

器停頓周期數]×時鐘周期時間CPU時間＝IC×[CPIexe＋訪存次數/指令數×

失效率×失效開銷]×時鐘周期時間5.2Cache基本知識例5.2

我們用一個和AlphaAXP類似的機器作為

第一個例子。假設Cache失效開銷為50個時鐘

周期，當不考慮存儲器停頓時，所有指令的

執行時間都是2.0個時鐘周期，Cache的失效

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

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

×時鐘周期時間

＝IC×3.33×時鐘周期時間CPU時間＝IC×(CPIexe＋────────)

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

CPI＝2.0+50×1.33＝68.55.2Cache基本知識

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

Cache和兩路組相聯Cache，試問它們對CPU的性

能有何影響？先求平均訪存時間，然后再計算

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

為2.0，時鐘周期為2ns，平均每條指令

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

字節。例5.35.2Cache基本知識

⑶圖5.10說明，在組相聯Cache中，我們必須增

加一個多路選擇器，用于根據標識匹配結果

從相應組的塊中選擇所需的數據。因為CPU

的速度直接與Cache命中的速度緊密相關,所

以對于組相聯Cache，由于多路選擇器的存

在而使CPU的時鐘周期增加到原來的1.10倍。⑷這兩種結構Cache的失效開銷都是70ns。在

實際應用中，應取整為整數個時鐘周期。⑸命中時間為1個時鐘周期，64KB直接映象

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

相聯Cache的失效率為1.0%。5.2Cache基本知識由:

平均訪存時間＝命中時間＋失效率×失效開銷得:

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

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

CPU時間＝IC×(CPIexe＋每條指令的平均存儲器

停頓周期數)×時鐘周期時間

＝IC×(CPIexe×時鐘周期時間＋

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

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

＋(1.3×0.010×70))

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

(3)減少Cache命中時間下面介紹15種Cache優化技術5.2.7改進Cache性能5.2Cache基本知識(1)強制性失效(Compulsorymiss)

當第一次訪問一個塊時，該塊不在

Cache中，需從下一級存儲器中調入Cache，

這就是強制性失效。

(冷啟動失效，首次訪問失效。)(2)容量失效(Capacitymiss)

如果程序執行時所需的塊不能全部調

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

重新被訪問，就會發生失效。這種失效稱

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

在組相聯或直接映象Cache中，若太多

的塊映象到同一組(塊)中，則會出現該組

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

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

就是發生了沖突失效。

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

表5.5

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

量失效卻隨著容量的增加而減少；(4)表中的數據符合2:1的Cache經驗規則，即

大小為N

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

大小為N/2

的兩路組相聯Cache的失效率。強制性失效：增加塊大小，預取

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

(抖動現象)沖突失效：提高相聯度

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

失效開銷5.3降低Cache失效率的方法5.3.1增加Cache塊大小1.失效率與塊大小的關系

(1)對于給定的Cache容量，當塊大小增加

失效率開始是下降，后來反而上升了；

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

塊大小就越大。5.3降低Cache失效率的方法2.增加塊大小會增加失效開銷3.例題例5.4

假定存儲系統在延遲40個時鐘周期后，每2個

時鐘周期能送出16個字節。即:經過42個時鐘周期，

它可提供16個字節；經過44個時鐘周期，可提供32

個字節；依此類推。試問對于表5-6中列出的各種

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

時間最小？解：

解題過程

1KB、4KB、16KBCache:塊大小＝32字節

64KB、256KBCache:塊大小＝64字節5.3降低Cache失效率的方法塊大小（字節）失效開銷（時鐘周期）Cache容量（字節）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提高相聯度1.采用相聯度超過8的方法實際意義不大2.2:1Cache經驗規則

容量為N

的直接映象Cache

≈容量為N/2的兩路組相聯Cache3.提高相聯度是以增加命中時間為代價

例如：

TTL或ECL板級Cache，兩路組相聯：

增加10％

定制的CMOSCache,兩路組相聯：

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

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

時鐘周期：

時鐘周期2路＝1.10×時鐘周期1路

時鐘周期4路＝1.12×時鐘周期1路時鐘周期8路＝1.14×時鐘周期1路

假定命中時間為1個時鐘，直接映象情況

下失效開銷為50個時鐘周期，而且假設不必將

失效開銷取整。使用表5－5中的失效率，試問

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

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

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

<平均訪存時間1路解：

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

別為：平均訪存時間8路

=

命中時間8路

+失效率8路

×失效開銷8路

=1.14＋失效率8路×50

平均訪存時間4路

=1.12＋失效率4路×50

平均訪存時間2路

=1.10＋失效率2路×50

平均訪存時間1路

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

在每種情況下的失效開銷相同，都是

50個時鐘周期。把相應的失效率代入上式，

即可得平均訪存時間。

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

訪存時間為：平均訪存時間1路

＝1.00＋(0.133×50)

＝7.65

容量為128KB的8路組相聯Cache的平均

訪存時間為：平均訪存時間8路

＝1.14＋(0.006×50)

＝1.44表5-85.3降低Cache失效率的方法Cache容量（K字節）相聯度（路）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和它從下一級存儲器調數據

的通路之間設置一個全相聯的小Cache，

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

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

對于減小沖突失效很有效，特別是對

于小容量的直接映象數據Cache，作用尤其

明顯。

例如，項數為4的VictimCache:

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

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

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

平分為兩個區。對于任何一次訪問，偽相聯

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

命中，則其訪問過程與直接映象Cache的情

況一樣。若不命中，則再到另一區相應的位

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

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

假設當在按直接映象找到的位置處沒有發

現匹配、而在另一個位置才找到數據(偽命中)

需要2個額外的周期。仍用上個例子中的數據，

問：當Cache容量分別為2KB和128KB時，直接

映象、兩路組相聯和偽相聯這三種組織結構中，

哪一種速度最快？5.3降低Cache失效率的方法首先考慮標準的平均訪存時間公式：

平均訪存時間偽相聯

＝命中時間偽相聯＋失效率偽相聯×失效開銷偽相聯由于：

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

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

平均訪存時間偽相聯

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

＋失效率2路×失效開銷1路將表5－5中的數據代入上面的公式，得：平均訪存時間偽相聯，2KB

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

＝4.844

平均訪存時間偽相聯，128KB

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

＝1.3565.3降低Cache失效率的方法根據上一個例子中的表5－8，對于2KBCache，

可得：平均訪存時間1路＝5.90個時鐘平均訪存時間2路＝4.90個時鐘對于128KB的Cache有，可得：平均訪存時間1路＝1.50個時鐘平均訪存時間2路＝1.45個時鐘可見，對于這兩種Cache容量，偽相聯Cache

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

外緩沖器中

例如：指令流緩沖器3.預取效果

(1)Joppi的研究結果

◆

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

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

捕獲15％～25％

的失效4個塊的指令流緩沖器：

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

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

還可以采用多個數據流緩沖器(2)Palacharla和Kessler的研究結果流緩沖器：既能預取指令又能預取數據對于兩個64KB四路組相聯Cache來說：

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

AlphaAXP21064采用指令預取技術，其實際

失效率是多少？若不采用指令預取技術，Alpha

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

存時間不變？解：

假設從預取緩沖器中找到所需指令需多花1個

時鐘周期。

平均訪存時間預取

＝命中時間＋失效率×預取命中率×1

＋失效率×(1－預取命中率)×失效開銷5.3降低Cache失效率的方法假設：

預取命中率＝25％

命中時間＝1個時鐘周期失效開銷＝50個時鐘周期由表5.4可知，8KB指令Cache的失效率＝1.10％故平均訪存時間預取＝1＋(1.10%×25%×1)＋

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

＝1＋0.00275＋0.4125

＝1.415

由公式：

平均訪問時間＝命中時間＋失效率×失效開銷5.3降低Cache失效率的方法可得相應的失效率為：失效率＝(平均訪問時間－命中時間)/失效開銷

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

帶預取的

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

◆

寄存器預取：把數據取到寄存器中

◆

Cache預取：

只將數據取到Cache中

◆

故障性預取：預取時，若出現虛地址故障

或違反訪問權限，就會發生異常。

◆

非故障性預取：預取時，若出現虛地址故

障或違反訪問權限，并不會導致異常，只

是轉變為“不預取”。由編譯器加入預取指令，在數據被用到之前

發出預取請求。5.3降低Cache失效率的方法4.例題2.在預取數據的同時，處理器應能繼續執行

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

循環是預取優化的主要對象

失效開銷小時：循環體展開1～2次

失效開銷大時：循環體展開許多次5.3降低Cache失效率的方法例5.8

對于下面的程序，判斷哪些訪問可能會導致

數據Cache失效。然后，加入預取指令以減少失

效。最后，計算所執行的預取指令的條數以及通

過預取避免的失效次數。假定：

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

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

且按寫分配。

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

的雙精度浮點數組，每個元素都是8個

字節。當程序開始執行時，這些數據都

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

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

/*

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

/*

預取7次循環后所需的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＋1)prefetch(a[i][j＋7]);

/*

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

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

在以下條件下，計算例5.8中所節約的時間：

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

無沖突失效和容量失效。

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

疊執行，從而能以最大的存儲帶寬傳送

數據。

(3)不考慮Cache失效時，修改前的循環每7

個時鐘周期循環一次。修改后的程序中，失效情況

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

修改前：

循環時間＝300×7＝2100

失效開銷＝251×50＝12550/146502100＋12550＝14650

第一個預取循環每9個時鐘周期循環一次，

而第二個預取循環每8個時鐘周期循環一

次(包括外層for循環的開銷)。

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

修改后：

循環時間＝100×9＋200×8＝2500

失效時間＝19×50＝9502500＋950＝3450

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

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

在編譯時，對程序中的指令和數據進行

重新組織，以降低Cache失效率。2.McFaring發現：通過對指令進行重新排序，

可有效地降低指令Cache的失效率。5.3降低Cache失效率的方法3.數據對存儲位置的限制比指令的少，因此

更便于優化。

通過把數據重新組織，使得在一塊數

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

利用其中的數據(訪問次數最多)

(1)數組合并

舉例：

/*修改前*/

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

舉例：

/*

修改前*/

for(j＝0;j<100;j＝j＋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)循環融合

舉例：

/*

修改前*/for(i＝0;i<N;i＝i＋1)for(j＝0;j<N;j＝j＋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＋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＋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＋1)d[i][j]＝a[i][j]＋c[i][j];(4)分塊

把對數組的整行或整列訪問改為按塊進行。5.3降低Cache失效率的方法

舉例：

/*

修改前*/

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

}x[i][j]＝r;

}計算過程

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

修改后*/for(jj＝0;jj<N;jj＝jj＋1)for(kk＝0;kk<N;kk＝kk＋1)for(i＝0;i<N;i＝i＋1)for(j＝jj;j<min(jj＋B－1,N);j＝j＋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;}計算過程

失效次數：2N3/B

＋N25.3降低Cache失效率的方法5.4.1讓讀失效優先于寫5.4減少Cache失效開銷1.Cache中的寫緩沖器導致對存儲器訪問的

復雜化2.解決問題的方法(讀失效的處理)

◆

推遲對讀失效的處理

(缺點：讀失效的開銷增加，如50％)

◆

檢查寫緩沖器中的內容3.在寫回法Cache中，也可采用寫緩沖器第五章存儲層次5.4.2子塊放置技術1.為減少標識的位數，可采用增加塊大小的

方法，但這會增加失效開銷，故應采用子

塊放置技術。2.子塊放置技術：把Cache塊進一步劃分為更

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

效位，用于指明該子塊中的數據是否有效。

Cache與下一級存儲器之間以子塊為單位傳

送數據。但標識仍以塊為單位。3.舉例(動畫演示)5.4減少Cache失效開銷5.4.3請求字處理技術1.請求字

從下一級存儲器調入Cache的塊中，只有

一個字是立即需要的。這個字稱為請求字。

2.應盡早把請求字發送給CPU

◆

盡早重啟動：調塊時，從塊的起始位置開

始讀起。一旦請求字到達，就立即發送給

CPU，讓CPU繼續執行。

◆

請求字優先：調塊時，從請求字所在的位

置讀起。這樣，第一個讀出的字便是請求

字。將之立即發送給CPU。5.4減少Cache失效開銷3.這種技術在以下情況下效果不大：

◆

Cache塊較小

◆

下一條指令正好訪問同一Cache塊的另

一部分5.4減少Cache失效開銷5.4.4非阻塞Cache技術1.非阻塞Cache：Cache失效時仍允許CPU進行

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

“失效下失效”

(存儲器必須能夠處理多個失效)3.重疊失效個數對平均訪問時間的影響5.4減少Cache失效開銷非阻塞Cache平均存儲器等待時間

與阻塞Cache的比值12浮點程序76％51％6439％整數程序81％78％78％重疊失效個數5.4減少Cache失效開銷

對于圖5.18所描述的Cache，在兩路組相聯和

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

點程序更重要？對整數程序的情況如何？

假設8KB數據Cache的平均失效率為：

對于浮點程序，直接映象Cache為11.4%，兩路

組相聯Cache為10.7%；

對于整數程序，直接映象Cache為7.4%，兩路

組相聯Cache為6.0%。并且假設平均存儲器等待時

間是失效率和失效開銷的積，失效開銷為16個時鐘

周期。例5.115.4減少Cache失效開銷對于浮點程序，平均存儲器等待時間為：

失效率直接映象×失效開銷＝11.4%×16＝1.82

失效率兩路組相聯×失效開銷＝10.7%×16＝1.711.71/1.82＝0.94

對于整數程序：

失效率直接映象×失效開銷＝7.4%×16＝1.18

失效率兩路組相聯×失效開銷＝6.0%×16＝0.960.96/1.18=0.81解：5.4減少Cache失效開銷5.4.5采用兩級Cache1.應把Cache做得更快？還是更大？

答案：二者兼顧，再增加一級Cache

◆

第一級Cache(L1)小而快

◆

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

平均訪問時間

＝命中時間L1＋失效率L1×失效開銷L1

＝命中時間L1＋失效率L1×

(命中時間L2＋失效率L2×失效開銷L2)5.4減少Cache失效開銷3.局部失效率與全局失效率

局部失效率＝該級Cache的失效次數/到達

該級Cache的訪問次數例如：上述式子中的失效率L2

全局失效率＝該級Cache的失效次數/CPU

發出的訪存的總次數

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

評價第二級Cache時，應使用全局失效率

這個指標。5.4減少Cache失效開銷例5.12

假設在1000次訪存中，第一級Cache失效40次，第二級Cache失效20次。試問：在這種情況下，該Cache系統的局部失效率和全局失效率各是多少？

解

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

5.4減少Cache失效開銷4.當第二級Cache比第一級Cache大得多時，兩

級Cache的全局失效率與容量和第二級Cache

相同的單級Cache的失效率非常接近。

5.第二級Cache的參數

第二級Cache不會影響CPU的時鐘頻率，

因此其設計有更大的考慮空間。

兩個問題：

◆

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

◆

成本是多少？

(1)容量

第二級Cache的容量一般比第一級的

大許多，如512KB。5.4減少Cache失效開銷(2)相聯度

第二級Cache可采用較高的相聯度或偽

相聯方法例5.13

給出有關第二級Cache的以下數據：⑴兩路組相聯使命中時間增加10%×CPU時鐘周期⑵對于直接映象，命中時間L2＝10個時鐘周期⑶對于直接映象，局部失效率L2＝25%⑷對于兩路組相聯，局部失效率L2＝20%⑸失效開銷L2＝50個時鐘周期試問第二級Cache的相聯度對失效開銷的影響如何？5.4減少Cache失效開銷解：

對于一個直接映象的第二級Cache來說，

第一級Cache的失效開銷為：失效開銷直接映象，L1

＝10＋25%×50＝22.5個時鐘周期對于兩路組相聯第二級Cache來說，命中

時間增加了10%(0.1)個時鐘周期，故第一級

Cache的失效開銷為：失效開銷兩路組相聯，L1

＝10.1＋20%×50＝20.1個時鐘周期

把第二級Cache的命中時間取整，得10或11，

則：5.4減少Cache失效開銷

失效開銷兩路組相聯，L1

＝10＋20%×50＝20.0個時鐘周期

失效開銷兩路組相聯，L1

＝11＋20%×50＝21.0個時鐘周期故對于第二級Cache來說，兩路組相聯優于

直接映象。(3)塊大小

第二級Cache可采用較大的塊，

如64、128、256字節。圖5.19

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

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

的第二級Cache采用較大的塊。5.4減少Cache失效開銷5.5減少命中時間2.應使Cache足夠小，以便可以與CPU一起放

在同一塊芯片上。

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

當今的許多計算機中，往往是Cache的訪問時間

限制了處理器的時鐘頻率。1.硬件越簡單，速度就越快；5.5.1容量小、結構簡單的Cache第五章存儲層次1.虛擬Cache

訪問Cache的索引以及Cache中的標識都

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

(進程標識符)三種情況下失效率的比較

單進程，PIDs，清空

PIDs與單進程相比：＋0.3％～＋0.6％

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

解決方法：反別名法,頁著色5.虛擬索引＋物理標識

優點：兼得虛擬Cache和物理Cache的好處

局限性：Cache容量受到限制

(頁內位移)

Cache容量≤頁大小×相聯度6.舉例：IBM3033的Cache

頁大小＝4KB

相聯度＝165.5減少命中時間5.5.3寫操作流水化

(圖5.22)

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

頁地址

地址標識頁內位移索引塊內位移31121105.5.4Cache優化技術總結

(表5-9)5.5減少命中時間優化技術失效率失效開銷命中時間硬件復雜度評價增加塊大小+-

0實現容易；RS/6000550采用了128字節提高相聯度+

-1MIPSR10000為4路組相聯VictimCache+

2HP7200中采用了類似的技術偽相聯Cache+

2已應用于MIPSR10000的第二級Cache硬件預取指令和數據+

2數據預取比較困難；僅被幾臺機器采用，如：Alpha21064編譯器控制的預取+

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

+

0向軟件提出了新要求；有些機器提供了編譯器選項使讀失效優先級高于寫

+

1在單處理機上實現容易，被廣泛使用子塊調入

+

1主要用于減少標識的數目盡早重啟動和關鍵字優先

+

2已應用于MIPSR10000和IBM620非阻塞Cache

+

3已應用于Alpha21064和R10000中第二級Cache

+

2硬件代價大；兩級Cache的塊大小不同時實現困難；被廣泛采用容量小且結構簡單的Cache-

+0實現容易，被廣泛使用避免在對Cache進行索引時進行地址轉換

+2對于小容量Cache來說實現容易，已應用于Alpha21064流水化寫

+1已應用于Alpha210641.主存的主要性能指標：延遲和帶寬2.以往：

Cache主要關心延遲，I/O主要關心帶寬現在：Cache關心兩者下面討論幾種能提高主存性能的存儲器組織技術在下面的討論中，我們以處理Cache失效為例來說明各種存儲器組織結構的好處。5.6主存第五章存儲層次◆

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

來的好處

在以下的討論中，我們假設基本存儲

器結構的性能為：5.6主存

送地址需4個時鐘周期每個字的訪問時間為24個時鐘周期傳送一個字的數據需4個時鐘周期◆

為了減少失效開銷TM，應該：

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

如果Cache大小為4個字，則：

失效開銷＝4×(4＋24＋4)

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

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

◆

性能舉例

(參照前面的假設)

當寬度為4個字時：

失效開銷＝1×32(周期)

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

◆

缺點：

5.6主存

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

CUP和Cache之間有一個多路選擇器擴充主存的最小增量增加了相應的倍數寫入有可能變得復雜◆

舉例：

DEC的AlphaAxp21064：256位寬2.采用簡單的多體交叉存儲器

在存儲系統中采用多個DRAM，并利用它們

潛在的并行性。◆

存儲器的各個體一般是按字交叉的交叉存儲器（interleavedmemory）

通常是指存儲器的各個體是按字交叉的。字交叉存儲器非常適合于處理：

Cache讀失效，寫回法Cache中的寫回

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

失效開銷＝4＋24＋4×4＝44(周期)

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

假設四個存儲體的地址是在字一級交叉的，即存儲體0中每個字的地址對4取模都是0，體1中每個字的地址對4取模都是1，依此類推。04812地址體015913地址體1261014地址體2371115地址體3

假設某臺機器的特性及其Cache的性能為：

·

塊大小為1個字

·

存儲器總線寬度為1個字

·Cache失效率為3%

·

平均每條指令訪存1.2次

·Cache失效開銷為32個時鐘周期(和上面相同)

·

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

試問多體交叉和增加存儲器寬度對提高性能各

有何作用？如果當把Cache塊大小變為2個字時，失效率例5.145.6主存

降為2%；塊大小變為4個字時，失效率降為1%。

根據5.6.2小節中給出的訪問時間，求在采用

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

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

在改變前的機器中，Cache塊大小為一個

字，其CPI為

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

當將塊大小增加為2個字時，在下面三種

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

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

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

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

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

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

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

存儲體的數目

體的數目≥訪問體中一個字所需的時鐘周期32位總線和存儲器，采用多體交叉：

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

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

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

性能提高了14%3.獨立存儲體

設置多個存儲控制器，使多個體能獨立操

作，以便能同時進行多個獨立的訪存。5.6主存◆

每個體有獨立的地址線

(動畫演示)◆

非阻塞Cache與多體結構◆

體和超體將存儲器分為若干個獨立的存儲體，而每個獨立存儲體內又劃分為若干個按字交叉方式工作的體。

5.6主存4.避免存儲體沖突

◆

體沖突：

兩個請求要訪問同一個體

◆

減少沖突：采用許多體例如：NECSX/3最多128個體

這種方法存在問題。

5.6主存

假如我們有128個存儲體，按字交叉方式工作，并執行以下程序：

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];

因為512是128的整數倍，同一列中的所有元素都在同一個體內，無論CPU或存儲系統多么高級，該程序都會在數據Cache失效時暫停。5.6主存◆

解決體沖突的方法◆

舉例

(表5-10)

軟件方法(編譯器)

循環交換優化 擴展數組的大小，使之不是2的冪。硬件方法

使體數為素數。

當存儲體數為素數，且為2的冪減1時，