計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)-5-存儲層次課件

5.2

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

減少Cache失效開銷5.1

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

減少命中時間5.6

主存5.7

虛擬存儲器5.8

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

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

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

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

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

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

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

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

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

──容量

TA──訪問時間

C

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

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

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

每位價格C

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

H＝N1/(N1＋N2)

N1

──訪問M1的次數(shù)

N2

──訪問M2的次數(shù)

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

TA＝TA1＋(1－H)TM

或

TA＝TA1＋F

TM

TA1

──命中時間

TM

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

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

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

◆

主存與CPU的速度差距

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

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

訪問速度的比值

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

可以放在哪些位置上?

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

找到該塊?

(查找算法)3.

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

(替換算法)4.

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

(寫策略)1.

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

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

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

對比：

閱覽室位置──隨便坐

特點(diǎn)：

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

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

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

Cache中唯一的一個位置。

舉例

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

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

以坐◆

特點(diǎn)：空間利用率最低，沖突概率最高， 實(shí)現(xiàn)最簡單?！?/p>

對于主存的第i

塊，若它映象到Cache的第

j

塊，則:

j＝imod(M)

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

5.2Cache基本知識◆

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

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

舉例◆

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

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

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

和k

通常稱為索引◆

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

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

k＝imod（G）

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

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

際上就是i的低g位：g

位ki：5.2Cache基本知識◆

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

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

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

n稱為相聯(lián)度。

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

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

(路數(shù))G

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

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

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

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

并行查找與順序查找◆

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

前瞻執(zhí)行◆

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

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

◆

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

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

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

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

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

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

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

Load指令：26％

Store指令：9％

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

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

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

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

◆

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

也寫入下一級存儲器。

◆

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

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

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

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

帶較低；

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

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

◆

按寫分配(寫時取)

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

Cache，再行寫入。

◆

不按寫分配(繞寫法)

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

Cache。1.簡介

容量：8KB

塊大?。?2B

塊數(shù)：256

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

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

◆

“讀”訪問命中◆

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

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

(2)失效率的比較

5.2Cache基本知識◆

失效情況下的操作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ì)算：訪問指令Cache的百分比×指令Cache的失效率＋訪問數(shù)據(jù)Cache的百分比×數(shù)據(jù)Cache的失效率5.2.6Cache性能分析2.平均訪問時間

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

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

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

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

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

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

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

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

5.2Cache基本知識解：

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

分離Cache的總體失效率為：

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

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

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

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

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

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

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

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

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

(數(shù)據(jù)命中時間＋數(shù)據(jù)失效率×失效開銷)所以，兩種結(jié)構(gòu)的平均訪存時間分別為：平均訪存時間分離＝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.程序執(zhí)行時間

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

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

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

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

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

失效率×失效開銷]×?xí)r鐘周期時間5.2Cache基本知識例5.2

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

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

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

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

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

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

×?xí)r鐘周期時間

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

相聯(lián)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＋每條指令的平均存儲器

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

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

每條指令的平均存儲器停頓時間)解：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基本知識平均訪存時間＝命中時間＋失效率×失效開銷可以從三個方面改進(jìn)Cache的性能：(1)降低失效率(2)減少失效開銷

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

表5.5

5.3降低Cache失效率的方法圖示I(絕對值)圖示Ⅱ(相對值)可以看出：(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ù)取

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

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

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

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

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

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

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

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

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

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

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

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

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

時間最?。拷猓?/p>

解題過程

1KB、4KB、16KBCache:塊大?。?2字節(jié)

64KB、256KBCache:塊大小＝64字節(jié)5.3降低Cache失效率的方法塊大?。ㄗ止?jié)）失效開銷（時鐘周期）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)度超過8的方法實(shí)際意義不大2.2:1Cache經(jīng)驗(yàn)規(guī)則

容量為N

的直接映象Cache

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

例如：

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

增加10％

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

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

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

時鐘周期：

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

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

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

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

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

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

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

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

<平均訪存時間1路解：

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

別為：平均訪存時間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個時鐘周期。把相應(yīng)的失效率代入上式，

即可得平均訪存時間。

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

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

＝1.00＋(0.133×50)

＝7.65

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

訪存時間為：平均訪存時間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和它從下一級存儲器調(diào)數(shù)據(jù)

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

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

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

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

于小容量的直接映象數(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)命中時間小命中時間大失效率高失效率低取直接映象及組相聯(lián)兩者的優(yōu)點(diǎn)：

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

＝命中時間偽相聯(lián)＋失效率偽相聯(lián)×失效開銷偽相聯(lián)由于：

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

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

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

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

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

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

＝4.844

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

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

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

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

都是速度最快的。缺點(diǎn)：多種命中時間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,

塊大?。?6字節(jié))5.3降低Cache失效率的方法1個塊的指令流緩沖器：

捕獲15％～25％

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

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

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

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

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

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

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

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

存時間不變？解：

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

時鐘周期。

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

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

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

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

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

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

＝1＋0.00275＋0.4125

＝1.415

由公式：

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

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

帶預(yù)取的

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

◆

寄存器預(yù)?。喊褦?shù)據(jù)取到寄存器中

◆

Cache預(yù)?。?/p>

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

◆

故障性預(yù)?。侯A(yù)取時，若出現(xiàn)虛地址故障

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

◆

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

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

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

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

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

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

失效開銷小時：循環(huán)體展開1～2次

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

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

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

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

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

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

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

且按寫分配。

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

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

字節(jié)。當(dāng)程序開始執(zhí)行時，這些數(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ì)算過程(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é)約的時間：

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

無沖突失效和容量失效。

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

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

數(shù)據(jù)。

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

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

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

修改前：

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

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

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

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

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

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

修改后：

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

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

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

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

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

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

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

更便于優(yōu)化。

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

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

利用其中的數(shù)據(jù)(訪問次數(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)分塊

把對數(shù)組的整行或整列訪問改為按塊進(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ì)算過程

失效次數(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ì)算過程

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

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

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

◆

推遲對讀失效的處理

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

◆

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

方法，但這會增加失效開銷，故應(yīng)采用子

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

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

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

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

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

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

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

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

◆

盡早重啟動：調(diào)塊時，從塊的起始位置開

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

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

◆

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

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

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

◆

Cache塊較小

◆

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

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

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

“失效下失效”

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

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

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

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

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

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

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

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

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

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

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

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

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

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

對于整數(shù)程序：

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

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

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

◆

第一級Cache(L1)小而快

◆

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

平均訪問時間

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

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

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

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

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

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

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

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

評價第二級Cache時，應(yīng)使用全局失效率

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

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

解

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

5.4減少Cache失效開銷4.當(dāng)?shù)诙塁ache比第一級Cache大得多時，兩

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

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

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

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

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

兩個問題：

◆

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

◆

成本是多少？

(1)容量

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

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

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

相聯(lián)方法例5.13

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

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

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

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

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

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

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

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

則：5.4減少Cache失效開銷

失效開銷兩路組相聯(lián)，L1

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

失效開銷兩路組相聯(lián)，L1

＝11＋20%×50＝21.0個時鐘周期故對于第二級Cache來說，兩路組相聯(lián)優(yōu)于

直接映象。(3)塊大小

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

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

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

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

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

在同一塊芯片上。

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

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

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

訪問Cache的索引以及Cache中的標(biāo)識都

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

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

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

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

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

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

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

局限性：Cache容量受到限制

(頁內(nèi)位移)

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

頁大?。?KB

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

(圖5.22)

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

頁地址

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

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

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

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

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

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

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

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

+

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

+

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

+

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

+

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

+

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

+

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

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

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

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

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

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

來的好處

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

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

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

為了減少失效開銷TM，應(yīng)該：

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

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

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

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

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

◆

性能舉例

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

當(dāng)寬度為4個字時：

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

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

◆

缺點(diǎn)：

5.6主存

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

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

舉例：

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

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

潛在的并行性。◆

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

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

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

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

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

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

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

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

·

塊大小為1個字

·

存儲器總線寬度為1個字

·Cache失效率為3%

·

平均每條指令訪存1.2次

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

·

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

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

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

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

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

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

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

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

字，其CPI為

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

當(dāng)將塊大小增加為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個字節(jié)，則：32位總線和存儲器，不采用多體交叉：

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

存儲體的數(shù)目

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

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

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

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

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

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

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

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

(動畫演示)◆

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

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

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

◆

體沖突：

兩個請求要訪問同一個體

◆

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

這種方法存在問題。

5.6主存

假如我們有128個存儲體，按字交叉方式工作，并執(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ù)倍，同一列中的所有元素都在同一個體內(nèi)，無論CPU或存儲系統(tǒng)多么高級，該程序都會在數(shù)據(jù)Cache失效時暫停。5.6主存◆

解決體沖突的方法◆

舉例

(表5-10)

軟件方法(編譯器)

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

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

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