Go to Qiita Advent Calendar 2024 Top
LoginSignup
11
7

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 5 years have passed since last update.

@takata150802

演習問題解答案(第5章容量と速度の両立：記憶階層の利用) パタヘネ: コンピュータの構成と設計 5th

Last updated at Posted at 2018-07-08

パタヘネ5版1の演習問題を解いています．
本記事では，“第5章容量と速度の両立：記憶階層の利用”の解答をまとめていきたいと思います．
第五章の内容は，キャッシュ, 仮想記憶などです．

なかなか演習問題に取り組む時間がとれないのですが，随時解答を追加してきます．

前回の記事：演習問題解答案(第4章プロセッサ) パタヘネ: コンピュータの構成と設計 5th

5.1 A CPU cache

5.1.1

16 Byte / 32 bit = 4

5.1.2

i, j: 全てのイテレーション($8 \times 8000$回)で，I, Jは複数回参照される．

B[I][0]: 最外ループのある1イテレーションで，B[I][0]は$8000$回参照される．

5.1.3

A[I][J]: 最外ループのある1イテレーションで，A[I][J]は最内ループの各イテレーション毎にシーケンシャルに参照される．

5.1.4

必要なキャッシュラインの数は下記となる．
$ \frac{8 * 8000 * 2 - 8 * 8}{4
[\rm{Byte}]} + \frac{8000}{4
[\rm{Byte}]} = 33984$

※A(I,J)は少なくとも要素数$8000\times8000$以上の行列ですが，参照される要素数は$8 \times 8000 \times 2 - 8 \times 8$です．また，B(I)の参照される要素数は$8000$となります．

5.1.5

I, J ,B(I,0)

5.1.6

A(J,I)

5.2 Improving Cache Performance

5.2.1

設問文で示されたキャッシュの緒元：

  • 32 bit幅のアドレス
  • 1word(4Byte)ブロックx16
  • ダイレクトマップ方式

キャッシュの構成パラメータ：

  • Byte offset: 2bit
  • Block offset: 無し(log2(1[word])= 0bit)
  • Index: 4bit (log2(16[ブロック]) = 4)
  • Tag: 32 - (2 + 0 + 4) = 26bit
Adrs(Decimal) Adrs(binary) [31:8] Adrs(binary)[7:0] Tag Index Block offset Byte offset Hit?
3 24'b0 8'b0000_0011 26'h0 4'h0 N/A 2'b11 No
180 24'b0 8'b1011_0100 26'h2 4'hD N/A 2'b00 No
43 24'b0 8'b0010_1011 26'h0 4'hA N/A 2'b11 No
2 24'b0 8'b0000_0010 26'h0 4'h0 N/A 2'b10 Yes
191 24'b0 8'b1011_1111 26'h2 4'hF N/A 2'b11 No
88 24'b0 8'b0101_1000 26'h1 4'h6 N/A 2'b00 No
190 24'b0 8'b1011_1110 26'h2 4'hF N/A 2'b10 Yes
14 24'b0 8'b0000_1110 26'h0 4'h3 N/A 2'b10 No
181 24'b0 8'b1011_0101 26'h2 4'hD N/A 2'b01 Yes
44 24'b0 8'b0010_1100 26'h0 4'hB N/A 2'b00 No
186 24'b0 8'b1011_1010 26'h2 4'hE N/A 2'b10 No
253 24'b0 8'b1111_1101 26'h3 4'hF N/A 2'b01 No

5.2.2

設問文で示されたキャッシュの緒元：

  • 32 bit幅のアドレス
  • 2word(8Byte)ブロックx8
  • ダイレクトマップ方式

キャッシュの構成パラメータ：

  • Byte offset: 2bit
  • Block offset: 1bit (log2(2[word]) = 1bit)
  • Index: 3bit (log2(8[ブロック]) = 3)
  • Tag: 32 - (2 + 1 + 3) = 26bit
Adrs(Decimal) Adrs(binary) [31:8] Adrs(binary)[7:0] Tag Index Block offset Byte offset Hit?
3 24'b0 8'b0000_0011 26'h0 3'h0 1'b0 2'b11 No
180 24'b0 8'b1011_0100 26'h2 3'h6 1'b1 2'b00 No
43 24'b0 8'b0010_1011 26'h0 3'h5 1'b0 2'b11 No
2 24'b0 8'b0000_0010 26'h0 3'h0 1'b0 2'b10 Yes
191 24'b0 8'b1011_1111 26'h2 3'h7 1'b1 2'b11 No
88 24'b0 8'b0101_1000 26'h1 3'h3 1'b0 2'b00 No
190 24'b0 8'b1011_1110 26'h2 3'h7 1'b1 2'b10 Yes
14 24'b0 8'b0000_1110 26'h0 3'h1 1'b1 2'b10 No
181 24'b0 8'b1011_0101 26'h2 3'h6 1'b1 2'b01 Yes
44 24'b0 8'b0010_1100 26'h0 3'h5 1'b1 2'b00 Yes★
186 24'b0 8'b1011_1010 26'h2 3'h7 1'b0 2'b10 Yes★
253 24'b0 8'b1111_1101 26'h3 3'h7 1'b1 2'b01 No

5.2.3

キャッシュの構成案C1, C2, C3それぞれに対して，設問文で示された１２回の参照に対するミス率・合計アクセス時間を整理すると下記のようになります．よって，ミス率・アクセス時間の両方の観点でC3が最も優れています．

miss rate access time miss penalty total cycle
C1 9/12=75% 2[cycle] 25[cycle] 249[cycle]
C2 7/12=58% 3[cycle] 25[cycle] 211[cycle]
C3 5/12=42% 5[cycle] 25[cycle] 185[cycle]

なお，ミス率の導出のため，5.2.2で書いたような図をC1,C2,C3について書きました．

  • C1
Adrs(Decimal) Adrs(binary) [31:8] Adrs(binary)[7:0] Tag Index Block offset Byte offset Hit?
3 24'b0 8'b0000_0011 27'h0 3'h0 N/A 2'b11 No
180 24'b0 8'b1011_0100 27'h5 3'h5 N/A 2'b00 No
43 24'b0 8'b0010_1011 27'h1 3'h2 N/A 2'b11 No
2 24'b0 8'b0000_0010 27'h0 3'h0 N/A 2'b10 Yes
191 24'b0 8'b1011_1111 27'h5 3'h7 N/A 2'b11 No
88 24'b0 8'b0101_1000 27'h2 3'h6 N/A 2'b00 No
190 24'b0 8'b1011_1110 27'h5 3'h7 N/A 2'b10 Yes
14 24'b0 8'b0000_1110 27'h0 3'h3 N/A 2'b10 No
181 24'b0 8'b1011_0101 27'h5 3'h5 N/A 2'b01 Yes
44 24'b0 8'b0010_1100 27'h1 3'h3 N/A 2'b00 No
186 24'b0 8'b1011_1010 27'h5 3'h6 N/A 2'b10 No
253 24'b0 8'b1111_1101 27'h7 3'h7 N/A 2'b01 No
  • C2
Adrs(Decimal) Adrs(binary) [31:8] Adrs(binary)[7:0] Tag Index Block offset Byte offset Hit?
3 24'b0 8'b0000_0011 27'h0 2'h0 1'b0 2'b11 No
180 24'b0 8'b1011_0100 27'h5 2'h2 1'b1 2'b00 No
43 24'b0 8'b0010_1011 27'h1 2'h1 1'b0 2'b11 No
2 24'b0 8'b0000_0010 27'h0 2'h0 1'b0 2'b10 Yes
191 24'b0 8'b1011_1111 27'h5 2'h3 1'b1 2'b11 No
88 24'b0 8'b0101_1000 27'h2 2'h3 1'b0 2'b00 No
190 24'b0 8'b1011_1110 27'h5 2'h3 1'b1 2'b10 Yes
14 24'b0 8'b0000_1110 27'h0 2'h1 1'b1 2'b10 No
181 24'b0 8'b1011_0101 27'h5 2'h2 1'b1 2'b01 Yes
44 24'b0 8'b0010_1100 27'h1 2'h1 1'b1 2'b00 Yes★
186 24'b0 8'b1011_1010 27'h5 2'h3 1'b0 2'b10 Yes★
253 24'b0 8'b1111_1101 27'h7 2'h3 1'b1 2'b01 No
  • C3
Adrs(Decimal) Adrs(binary) [31:8] Adrs(binary)[7:0] Tag Index Block offset Byte offset Hit?
3 24'b0 8'b0000_0011 27'h0 1'b0 2'b00 2'b11 No
180 24'b0 8'b1011_0100 27'h5 1'b1 2'b01 2'b00 No
43 24'b0 8'b0010_1011 27'h1 1'b0 2'b10 2'b11 No
2 24'b0 8'b0000_0010 27'h0 1'b0 2'b00 2'b10 Yes
191 24'b0 8'b1011_1111 27'h5 1'b1 2'b11 2'b11 Yes★
88 24'b0 8'b0101_1000 27'h2 1'b1 2'b10 2'b00 No
190 24'b0 8'b1011_1110 27'h5 1'b1 2'b11 2'b10 Yes
14 24'b0 8'b0000_1110 27'h0 1'b0 2'b11 2'b10 Yes★
181 24'b0 8'b1011_0101 27'h5 1'b1 2'b01 2'b01 Yes
44 24'b0 8'b0010_1100 27'h1 1'b0 2'b11 2'b00 Yes
186 24'b0 8'b1011_1010 27'h5 1'b1 2'b10 2'b10 Yes
253 24'b0 8'b1111_1101 27'h7 1'b1 2'b11 2'b01 No

5.2.4

第一のキャッシュについて

キャッシュの緒元：

  • 32 bit幅のアドレス
  • 2word(8Byte)ブロック
  • キャッシュデータサイズは32KiByte
  • ダイレクトマップ方式

構成パラメータ：

  • Byte offset: 2bit
  • Block offset: 1bit (log2(2[word]) = 1bit)
  • ブロック数: 32KiByte/2words = 4Ki [Block]
  • Index: 12bit (log2(4Ki [Block]) = 12)
  • Tag: 32 - (2 + 1 + 12) = 17bit
  • 合計ビット数: (Tag + enable bit) * ブロック数 + キャッシュデータサイズ = (17 + 1) * 4Ki + 32KiByte = 41KiByte = 41984 bit

第二のキャッシュについて

第二のキャッシュの諸元：

  • 32 bit幅のアドレス
  • 16word以上のブロックサイズ
  • ダイレクトマップ方式
  • 合計ビット数が第一のキャッシュに最も近い

構成パラメータ:

ブロック数を2^n，ブロックサイズを2^b(b≧4)とする．

構成パラメータは下記のように表される．

  • Byte offset: 2bit
  • ブロックサイズ: 2^b [word]
  • Block offset: b bit
  • ブロック数: 2**n [Block]
  • Index: n bit
  • Tag: 32 - (2 + b + n) = 30 - (b + n) bit
  • 合計ビット数: 31*2^n - (n + b)*2^n + 32*2(n + b)

以上より，下記関数を最小化する自然数a,bが，合計ビット数が最も第一のキャッシュに近い第二のキャッシュの構成パラメータa,bである．

$f(a,b) = |31\times2^n - (n + b)\times2^n + 32\times2(n + b)- 41984| $$ $$b >= 4$

$\therefore a = 6 bit, b = 4 bit$

最終的な第二のキャッシュの構成パラメータは下記となる．

  • Byte offset: 2bit
  • ブロックサイズ: 16 [word]
  • Block offset: 4 bit
  • ブロック数: 64 [Block]
  • Index: 6 bit
  • Tag: 20 bit
  • 合計ビット数: 34112 bit

第二のキャッシュの方が第一のキャッシュよりもブロックサイズが大きいが，性能が低い可能性がある理由:

  1. ブロックサイズが大きくなると，アクセス時間が増大するから
  2. ブロックサイズが大きくなると，ミス・ペナルティが増大するから

5.2.5

読み出し要求：0x0000_0000, 0x0000_8000, 0x0000_0000, 0x0000_8000, ・・・ 0x0000_0000, 0x0000_8000

第一のキャッシュにおいて，32bitアドレスとTag, Indexの関係は下記のようになる．

adrs[31:0] Tag Index
0x0000_0000 0 0
0x0000_8000 1 0

よって，上記読み出し要求に対し，ダイレクトマップ方式である第一のキャッシュは毎回キャッシュミスするが，
2way set associativeなキャッシュは最初の２回の読み出し要求以降キャッシュミスしない．

5.2.6

Aug 15 2018:追記

解答の一部を修正しました．@kurさんありがとうございます．
特に下記２点です．

  • TagにXORハッシュ値を用いてもメリットは無い．(IndexにXORハッシュ値を用いることには有用である)
  • 修正前のTag,Index算出方法はバグである．例えば，下記第一のアドレスと第二のアドレスからTag, Indexを算出したとき，どちらのアドレスに対してもTag=10'hF800, Index=10'h3E0となってしまう．つまり，第一のアドレスがキャッシュされた後，第二のアドレスがロードされると誤ってキャッシュヒットし，第一アドレスのデータが第二のアドレスのデータとして返されてしまう．
    • 第一のアドレス: 32'h0000_0000
    • 第二のアドレス: 32'hF800_0000

また，Tagの算出方法には解答に示した方法の他にいくつか別解が存在します．例として下記に５つの別解を示します．

  1. Tag: 16bit, {adrs[26:22], adrs[21:11])
  2. Tag: 16bit, {adrs[31:27], adrs[21:11])
  3. Tag: 16bit, {adrs[26:24],adrs[28:27], adrs[21:11])
  4. Tag: 16bit, {adrs[31:30],adrs[24:22], adrs[21:11])
  5. Tag: 16bit, {adrs[31], adrs[25],adrs[29],adrs[23],adrs[27], adrs[21:11])

追記ここまで

可能である．
アドレスの上位5bitとその次の5bitのXORハッシュ値をIndex算出に使うなら，
同様にそのハッシュ値をTag算出に用いれば良い．
このようにすることで，下記のメリットが得られる．

  • キャッシュに使用するアドレスが仮想アドレスである場合，どうしても使用されるアドレスに偏りが生じる(page 583参照)．例えば，アドレスの上位10bitが偏った値となる．その場合，キャッシュを有効に活用できない． そこで，設問のようにXORハッシュ値を用いると，アドレスに偏りがあっても~~Tag,~~Indexの値は偏らずキャッシュを有効に活用できる．

具体的には，32 bitのアドレス(adrs[31:0])を下記のように割り振れば良い．
※ブロック数が1024であるので，Indexは10bit幅である．
※ブロックサイズは16wordを仮定する．

  • Tag: 16bit, {adrs[31:27] xor adrs[26:22], adrs[21:11])
  • Tag: 16bit, {adrs[26:22], adrs[21:11])
  • Index: 10bit, {adrs[31:27] xor adrs[26:22], adrs[10:6])
  • Block offset: 4bit, adrs[5:2]
  • Byte offset: 2bit, adrs[1:0]

5.3

5.3.1

offsetフィールドが5bitであるので，
2**5 Byte = 8 word

5.3.2

indexフィールドが5bitであるので，
2**5 = 32 entry

5.3.3

$1+\frac{\rm{1エントリに格納するデータ以外のbit数}}{\rm{1エントリに格納するデータのbit数}} $
$= 1 + \frac{\rm{1(valid)+22(tag)}}{\rm{2^5 \times 8bit}} $
$= 1.09$

5.3.4

4回

  • 各参照に対する，ヒット・置き換えは下記のようになる．
Adrs(Decimal) tag[31:10](hex) index[9:5](hex) offset[4:0](hex) Hit? Replace?
0 0 0 0 No No
4 0 0 4 Yes No
16 0 0 10 Yes No
132 0 4 4 No No
232 0 7 8 No No
160 0 5 0 No No
1024 1 0 0 No Yes
30 0 0 1E No Yes
140 0 4 C Yes No
3100 3 0 1C No Yes
180 0 5 14 Yes No
2180 2 4 4 No Yes

5.3.5

5.3.4に示した図より，

4/12 = 33.3%

5.3.6

各エントリのうち，有効なエントリに格納されているタグ・データは下記となる．

index (hex) tag (hex) data
0 3 Mem[3072:3013]
4 2 Mem[2176:2207]
5 0 Mem[160:191]
7 0 Mem[224:255]

5.4

5.4.1

Aug 15 2018:追記

解答の一部を修正しました．
(本設問の解答についてはあまり自信がありません・・・
そもそも”キャッシュのWrite Buffer”という用語に明確に定義ってあるんですかね？？？)

パタへネ５版５章では，”ライト・バッファ”に関する記述はpage382-383にあります．
ただ，よく読むとライト・バッファと言っても３種類のライト・バッファについて説明しているようです．
下記の表は，その3種類のライト・バッファをtype-A,B,Cとしてまとめたものです．

Write Bufferの種類 方式 目的
type-A Write-through方式 下位キャッシュへの書き込みレイテンシの隠蔽
type-B Write-back方式 "書き込みミス(ストア時のキャッシュミス)"を判定するサイクルの間，ストアするデータを保持すること
type-C Write-back方式 "書き込みミス"が発生した際のミスペナルティ削減

なお，type-A,B,Cそれぞれの本文中の記述箇所は下記です．

  • type-A: page382, 17行目, "この問題に対する解決策の１つはライト・バッファ(write buffer)を用いることで〜〜"
  • tpye-B: page383, 20行目, "もう１つは，対象のデータを保持するライト・バッファ(write buffer)を設けて〜〜"
  • type-C: page383, 31行目, "ライト・バック方式の多くのキャッシュは，ライト・バッファを備えている．"

※特に，page382, 41行目 "キャッシュへの書き込みに関しては，読み出しに見られない，難しい問題がいくつか出てくる．そのうち２つを取り上げる．具体的には，書き込みミスに対する方策とライトバック方式のキャッシュにおける効率的な書き込みの実現である．"の記述について，
"書き込みミスに対する方策"とは，ライト・スルー方式にはwrite allocate方式 もしくはno write allocate方式, ライト・
バック方式に対してはWrite Buffer(type-B)のことを指しており，
"効率的な書き込みの実現"とは，Write Buffer(type-C)でミスペナルティを削減することであると読み取りました．

下記に示した解答は，上述のtype-A, type-B, type-Cを説明の設定に沿って，説明しなおしただけのものです．

追記ここまで

下記３つのバッファが必要となり得る．

  1. L1,L2キャッシュ間Write Buffer(type-A):
  • L1キャッシュはWrite-through方式であるため，L1キャッシュに対する書き込みは必ずL2キャッシュに対しても行われる．このL2キャッシュへの書き込みレイテンシを隠蔽するQueueとして， L1,L2キャッシュ間Write Buffer(type-A)を用意する．
  1. L2キャッシュ,主記憶間Write Buffer(type-B):
  • L2キャッシュはWrite-back方式であるため，一貫性(consistency)が失われている可能性がある．具体的には，主記憶よりもL2キャシュに書き込まれているデータとのほうが新しい場合がある．したがって，あるブロックを主記憶に追い出す場合はそのブロックに書き込まれているデータが更新されたものかチェック(Dirty bitのチェック)を行い適切に処理した後でなければならない．その間データを保持するためにL2キャッシュ,主記憶間Write Buffer(type-B)を用意する．
  1. L2キャッシュ,主記憶間Write back BufferWrite Buffer(type-C):
  • L2キャッシュはWrite-back方式であるため，L2キャッシュミスが発生し，要求ブロックの代わりにあるブロックを主記憶に追い出す場合はそのブロックに書き込まれているデータが更新されたものかチェック(Dirty bitのチェック)を行う．更新されていれば，そのブロックを主記憶に書きだした後，要求ブロックをL2キャッシュに読み込む．更新されていなけば，そのブロックを要求ブロックで上書きする．更新されているブロックを主記憶に読み出してから要求ブロックをL2キャッシュに読み込むことは大きくなペナルティとなる．このペナルティを軽減するために，L2キャッシュ,主記憶間Write back BufferWrite Buffer(type-C)を用意する．具体的には，更新されているブロックを一旦L2キャッシュ,主記憶間Write back BufferWrite Buffer(type-C)に保持しておき，要求ブロックをL2キャッシュに読み込んだ後，L2キャッシュ,主記憶間Write back BufferWrite Buffer(type-C)から主記憶に更新されているブロックを書き出す．

5.4.2

L1$での書き込みミスを処理する手順は下図のようになる．
flow.p542.PNG

5.4.3

英語版を確認したところ，設問文は誤訳と思われます．2
誤)"マルチレベルのプロセッサごとの固有キャッシュ(ブロックはL1とL2キャッシュのどちらか一方にのみ存在しうる)構成に関して，"
正)"マルチレベルの排他キャッシュ-いわゆるVictim Cache-(ブロックはL1とL2キャッシュのどちらか一方にのみ存在しうる)構成に関して，"

L1$での書き込みミスを処理は，5.4.2と同様となる．
L1$がNon-write-allocateであるため，L2 Cacheだけにデータを書き込めばよくL1$にはデータを書き込まない．
よって，Victim Cacheを仮定しても，"ブロックはL1とL2キャッシュのどちらか一方にのみ存在"させるために新たな処理は必要ない．

そこで，L1$が，Write-throughかつWrite-allocate方式でL1$とL2$はVictim Cache方式に則って制御されると仮定すると，
L1$での書き込みミスを処理する手順は下図のようになる．
flow.p543.PNG

5.4.4 - 5.4.6

  • 設問で仮定する命令mixとキャッシュ
1000命令当たりのld系命令数 1000命令当たりのst系命令数 I-Cacheミス率 D-Cacheミス率 Block size[Byte]
250 100 0.30% 2% 64

5.4.4

Write-throughかつWrite-allocate方式であるため，ld/st命令とメモリ(主記憶)への読み出し/書き込みの関係は下表のようになる．
CPI=2に必要な書き込みのバンド幅の計算は簡単である．st系命令の度にメモリアクセスが発生すると考えればよい．
一方で，CPI=2に必要な読み出しのバンド幅の計算には，キャッシュミスのタイミングでメモリアクセスが発生することになる．また，ld/st系命令によるD-$ミスだけでなく，i-fetchによるI-$ミスの両方を忘れずに考慮しなければならない．

ld命令 st命令 i-fetch
D-$ or I-$ Hit メモリアクセス無し メモリ書き込み メモリアクセス無し
D-$ or I-$ miss メモリ読み出し メモリ読み出し メモリ書き込み メモリ読み出し

※ ld命令でD-$ missしたとき，メモリに置換対象のデータを書き込んだりする必要はない．
なぜなら，Write-through方式であるため，D-$とメモリは一貫性が保たれているからである．

  • CPI=2に必要な読み出しのバンド幅
    下記２つを合計して，0.096[Byte/cycle] + 0.16[Byte/cycle] = 0.256[Byte/cycle]

    • i-fetchによるI-$ミス:
      {キャッシュミス回数/cycle}×{キャッシュミス時メモリから取得するデータサイズ}
      =({I-Cacheミス率}×{i-fetchの回数/cycle})×{Block size}
      =({I-Cacheミス率}×{1/CPI})×{Block size}
      = 0.3% × 1/2 × 64Byte = 0.096[Byte/cycle]
    • ld/st系命令によるD-$ミス：
      {キャッシュミス回数/cycle}×{キャッシュミス時メモリから取得するデータサイズ}
      =({D-Cacheミス率}×{ld/st系命令の回数/cycle})×{Block size}
      = 2% × ({350/1000}×1/CPI)×{Block size}
      = 2/100 × 350/1000 × 1/2 × 64Byte = 0.224[Byte/cycle]

  • CPI=2に必要な書き込みのバンド幅
    ※ 設問分の仮定は，"1000命令当たりのデータ書き込み数が100である"です．
    ここでは，"1000命令中100命令がst命令(1word=4Byte store)である"と解釈して解答を作成します．

{st命令の回数/cycle} × {メモリに書き込むデータサイズ}
= ({100/1000} × 1/CPI) × {メモリに書き込むデータサイズ}
= 100/1000 × 1/2 × 4Byte = 0.2[Byte/cycle]

5.4.5

Write-backかつWrite-allocate方式であるため，ld/st命令とメモリ(主記憶)への読み出し/書き込みの関係は下表のようになる．
CPI=2に必要な書き込みバンド幅の計算には，
D-Cacheミス率とダーティであるかどうかを考慮する必要がある．
一方で，CPI=2に必要な読み出しのバンド幅の計算は，5.4.4と全く同一である．

ld命令 st命令 i-fetch
D-$ or I-$ Hit メモリアクセス無し メモリアクセス無し メモリアクセス無し
D-$ or I-$ miss, no Dirty メモリ読み出し メモリ読み出し メモリ読み出し
D-$ or I-$ miss, Dirty メモリ読み出し メモリ書き込み メモリ読み出し メモリ書き込み N/A

※ Write-back方式であるため，メモリとD-$に一貫性が保証されていない．よって，ld/st命令でD-$ missしたとき，Dirtyであるならばメモリ(主記憶)に書き出してやる必要がある．
※ I-$にはDirty bitは無いものとする． よって, "I-$ miss"は全て"I-$ miss no Dirty"とし，"I-$ miss, Dirty"は"N/A"とした．

  • CPI=2に必要な読み出しのバンド幅
    0.256 [Byte/cycle] (5.4.4と全く同一)

  • CPI=2に必要な書き込みのバンド幅
    {ブロックを置換する回数/cycle} × {置換するブロックのデータサイズ}
    = {{ld/st命令の回数/cycle} × {D-Cahceミス率} × {ブロックの置換の発生率}} × {Block size}
    = 350/1000 × 1/2 × 2% × 30% × 64 Byte
    = 0.0672 [Byte/cycle]

5.4.6

Write-backかつWrite-allocate方式であると仮定して解答を作成する．
計算方法としては，5.4.4, 5.4.5を参考にCPI=1.5に読み替えるだけである．

  • CPI=1.5に必要な読み出しのバンド幅
    下記２つを合計して，0.442[Byte/cycle]

    • i-fetchによるI-$ミス:
      {キャッシュミス回数/cycle}×{キャッシュミス時メモリから取得するデータサイズ}
      =({I-Cacheミス率}×{i-fetchの回数/cycle})×{Block size}
      =({I-Cacheミス率}×{1/CPI})×{Block size}
      = 0.3% × 1/1.5 × 64Byte = 0.143808[Byte/cycle]
    • ld/st系命令によるD-$ミス：
      {キャッシュミス回数/cycle}×{キャッシュミス時メモリから取得するデータサイズ}
      =({D-Cacheミス率}×{ld/st系命令の回数/cycle})×{Block size}
      = 2% × ({350/1000}×1/CPI)×{Block size}
      = 2/100 × 350/1000 × 1/1.5 × 64Byte = 0.29866[Byte/cycle]

  • CPI=1.5に必要な書き込みのバンド幅
    {ブロックを置換する回数/cycle} × {置換するブロックのデータサイズ}
    = {{ld/st命令の回数/cycle} × {D-Cahceミス率} × {ブロックの置換の発生率}} × {Block size}
    = 350/1000 × 1/1.5 × 2% × 30% × 64 Byte
    = 0.0896 [Byte/cycle]

  1. Patterson & Hennessy: コンピュータの構成と設計 第5版 ↩

  2. 英語版を確認すると，当該設問には"For a multilevel exclusive cache (a block can only reside in one of the L1 and L2 caches), configuration, "と書かれており，"exclusive cache"は"Victim Cache"を指していると思われます． ↩

11
7
4

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
11
7

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?