『パタヘネ』5章 演習問題 解答集

Disclaimer

あくまで自学のために作成したものです。ここに書かれた内容の正当性を一切保証しません。
内容に誤りがある場合は是非コメントで指摘してください！！！

Table of contents

解答募集: 5.4.3, 5.6.4〜6, 5.7.4〜6, 5.8〜10, 5.11.3〜6, 5.12.3, 5.12.5, 5.13〜19

• 5.1
• 5.2
• 5.3
• 5.4
• 5.5
• 5.6
• 5.7
• 5.11
• 5.12

Solutions

5.1

5.1.1 4個

16バイトは128ビットなので、128 / 32 = 4

5.1.2 I, J, B[I][0]

I, J は毎回ループ内で参照されている。加えて、B[I][0]はあるIに対して8000回連続で参照されている。

5.1.3 A[I][J]

「同じ行内の複数の要素は連続して格納されている」ことから、メモリ上で実際に連続して格納されているのは A[I][J], A[I][J+1], A[I][J+2]...なので、二重配列の二番目のインデックスが増えていくA[I][J]を選ぶ。

5.1.4 31986個

プログラム全体で登場する異なる行列要素の数をかぞえて、5.1.1 の結果より、それを4で割ればよい。

A: A[I][J], A[J][I]それぞれ 8 * 8000 = 64000 個あるが、A[1][1]〜A[8][8]の64個が重複するため、64000 * 2 - 64
B: B[I][0] が 8個

なので、(64000 * 2 - 64 + 8) / 4 = 31986

5.1.5 I, J, B[I][0]

5.1.2 と同じ（メモリの配置が空間的に変わっただけなので、時間的局所性が変わらないのは当然）

5.1.6 A[J][I]

5.1.3 の逆で、「同じ列内の行列要素を連続的に格納する」ことから、メモリ上で実際に連続して格納されているのは A[I][J], A[I+1][J], A[I+2][J]...なので、二重配列の一番目のインデックスが増えていくA[J][I]を選ぶ。

5.2

5.2.1

末尾2ビットは「バイトオフセット」であることに注意する。

ブロックが16個なので、インデックスは log 16 = 4 ビット
したがって、下位3〜6(1-indexed)ビットがインデックスとなる。その上の下位7〜ビット（長さは26ビット）がタグ。
わかりやすくするために赤字部分をインデックスとして示した。

※ 2進アドレスは下8桁以外は省略
※ タグは下4桁以外は省略

2進アドレス （下8桁）	タグ （下2桁）	インデックス	ヒット/ミス
0000 0011	00	0000	ミス
1011 0100	10	1101	ミス
0010 1011	00	1010	ミス
0000 0010	00	0000	ヒット
1011 1111	10	1111	ミス
0101 1000	01	0110	ミス
1011 1110	10	1111	ヒット
0000 1110	00	0011	ミス
1011 0101	10	1101	ヒット
0010 1100	00	1011	ミス
1011 1010	10	1110	ミス
1111 1101	11	1111	ミス

5.2.2

ブロックが8個なので、インデックスは log 8 = 3 ビット
また、ブロック内オフセットが log 2 = 1 ビット
今回は下位4〜6(1-indexed)ビットがインデックスとなる。

タグ | インデックス | ブロック内オフセット

と分割されることに注意する。

2進アドレス （下8桁）	タグ （下2桁）	インデックス	ヒット/ミス
0000 0011	00	000	ミス
1011 0100	10	110	ミス
0010 1011	00	101	ミス
0000 0010	00	000	ヒット
1011 1111	10	111	ミス
0101 1000	01	011	ミス
1011 1110	10	111	ヒット
0000 1110	00	001	ミス
1011 0101	10	110	ヒット
0010 1100	00	101	ヒット
1011 1010	10	111	ヒット
1111 1101	11	111	ミス

5.2.3 ミス率、合計アクセス時間の観点で、ともに C3 が最も性能が良い

C1: インデックスは3bit、ブロック内オフセットは無し
→ 下位3〜5(1-indexed)ビットがインデックス
C2: インデックスは2bit、ブロック内オフセットは1bit
→ 下位4〜5(1-indexed)ビットがインデックス
C3: インデックスは1bit、ブロック内オフセットは1bit
→ 下位5(1-indexed)ビットがインデックス

また、タグはいずれも下位6〜ビット（長さは27ビット）なので、5.2.2と異なり下3桁の相違を考慮する必要がある。

C1

2進アドレス （下8桁）	タグ （下3桁）	インデックス	ヒット/ミス
0000 0011	000	000	ミス
1011 0100	101	101	ミス
0010 1011	001	010	ミス
0000 0010	000	000	ヒット
1011 1111	101	111	ミス
0101 1000	010	110	ミス
1011 1110	101	111	ヒット
0000 1110	000	011	ミス
1011 0101	101	101	ヒット
0010 1100	001	011	ミス
1011 1010	101	110	ミス
1111 1101	111	111	ミス

ミス率: 9 / 12

C2

2進アドレス （下8桁）	タグ （下3桁）	インデックス	ヒット/ミス
0000 0011	000	00	ミス
1011 0100	101	10	ミス
0010 1011	001	01	ミス
0000 0010	000	00	ヒット
1011 1111	101	11	ミス
0101 1000	010	11	ミス
1011 1110	101	11	ヒット
0000 1110	000	01	ミス
1011 0101	101	10	ヒット
0010 1100	001	01	ヒット
1011 1010	101	11	ヒット
1111 1101	111	11	ミス

ミス率: 7 / 12

C3

2進アドレス （下8桁）	タグ （下3桁）	インデックス	ヒット/ミス
0000 0011	000	0	ミス
1011 0100	101	1	ミス
0010 1011	001	0	ミス
0000 0010	000	0	ヒット
1011 1111	101	1	ヒット
0101 1000	010	1	ミス
1011 1110	101	1	ヒット
0000 1110	000	0	ヒット
1011 0101	101	1	ヒット
0010 1100	001	0	ヒット
1011 1010	101	1	ヒット
1111 1101	111	1	ミス

ミス率: 5 / 12

このように、ミス率はC3が最も低い。
また、合計アクセス時間は

C1: 25 * 9 + 2 * 12 = 249（サイクル）
C2: 25 * 7 + 3 * 12 = 211（サイクル）
C3: 25 * 5 + 5 * 12 = 185（サイクル）

となり、やはりC3が最も性能が良い。

5.2.4 （合計サイズ）335872ビット、（第2のキャッシュ）ブロックサイズが16語, ブロックの個数は512、（理由）ブロックサイズが大きくなるとミスペナルティが増大するから。

第1のキャッシュについて:

まずブロック数（キャッシュライン数）を考える。
キャッシュデータサイズは 32 KiB = 2^15 バイト、ブロックサイズは2語 = 8 = 2^3 バイトなので、2^12 = 4096 個のブロックがある。ダイレクトマップ方式であることに留意して、インデックスは 12 bit 必要。
ここからタグの長さが求まる。全体の32bitから、使わない末尾2bit、ブロック内オフセット1bit、インデックス12bitを引いて、タグの長さは

32 - 2 - 1 - 12 = 17 bit

となる。

以上より、タグ及び有効ビットも含めたキャッシュの、1つのブロックのビット数は

1 + 17 + 32 * 2 = 82 bit

なので、キャッシュの合計サイズは

82 * 4096 = 335872 = 328Kibibit

第2のキャッシュについて:

アドレス32bitのうち、インデックスで $n$ ビット、ブロック内オフセットで $m (\geq 4)$ ビット使うとする。タグは $32 - (2 + n + m) = 30 - n - m$ ビットとなる。

このとき、タグ及び有効ビットも含めたキャッシュの、1つのブロックのビット数は

$$ 1 + (30 - n - m) + 32 * 2^m = 31 - n - m + 2^{m+5} $$

で、これが $2^n$ 個あることから、キャッシュの合計サイズは

$$ (31 - n - m + 2^{m+5}) \cdot 2^n $$

適当に実験してみる。（2のオーダーで $n + m = 13, 14$ あたりが第1のキャッシュと近そうだというのは分かる）

def f(m, n):
    ans = 31 - n - m + pow(2, m+5)
    ans *= pow(2, n)
    return ans

>>> f(1, 12)
335872 # 1つ目のキャッシュ
>>> f(4, 9)
271360
>>> f(4, 10)
541696
>>> f(5, 8)
266752
>>> f(5, 9)
532992
>>> f(6, 7)
264448
>>> f(6, 8)
528640

おそらく $m=4, n=9$ が第1のキャッシュとサイズが最も近い。これは、ブロックサイズが16語、ブロックの個数が512のキャッシュである。

5.2.5 （読み出し要求）インデックスが同じでタグのみが異なるメモリアクセスを交互に繰り返す（例えば0x00000000, 0x10000000, 0x00000000, 0x10000000...など）（方策）マルチレベルキャッシュを用いる

2ウェイ・セット・アソシアティブであれば、異なるタグでも同じインデックスであれば2種類まで格納される。そして、その2種類のアドレスにアクセスするだけであれば（初期参照ミスを除けば）ミスが起こらない。
一方、ダイレクトマップ方式のキャッシュでも、それを二段構成のマルチレベルキャッシュにすることで、複数のタグのキャッシュを用意し得る（かも？）。（ちょっとここは自信ないです）

マルチレベルキャッシュの利点は、ミス率を減らすことができる点。欠点は、ミス率の減少に重点が置かれておりアクセス時間はやや遅い可能性がある点。（ここも自信ないです）

5.2.6 可能

キャッシュブロックサイズが明示されていないので、ここでは仮に2語であるとして、例えば

アドレス内の区画	計算方法
インデックス	{addr[31:27] XOR addr[26:22]} + addr[7:3]
タグ	addr[26:8]
ブロック内 オフセット	addr[2]
バイトオフセット	addr[1:0]

このようにすると、アドレスと「タグとインデックスの組み合わせ」が一対一対応する。

5.3

5.3.1 8語

オフセット 5bit のうち末尾 2bit を除いた 3bit がブロック内オフセットなので、語数は 2^3 = 8語。

5.3.2 32個

インデックスが 5bit なので、2^5 = 32

5.3.3 約1.09

一つのキャッシュラインについて比を考えればよい。
データを格納する bit 数は、32 bit * 8語 = 256 bit。
一方、それ以外にも、タグの 22 bit と有効ビットの 1bit がある。したがって、

(256 + 22 + 1) / 256 = 約1.09

5.3.4, 5.3.5, 5.3.6

各参照に対する、タグ・インデックス・ブロック内オフセットを示す。

2進アドレス （下12桁）	タグ （下2桁）	インデックス	ブロック内 オフセット	ヒット/ミス
0000 0000 0000	00	00000	000	ミス
0000 0000 0100	00	00000	001	ヒット
0000 0001 0000	00	00000	100	ヒット
0000 1000 0100	00	00100	001	ミス
0000 1110 1000	00	00111	010	ミス
0000 1010 0000	00	00101	000	ミス
0100 0000 0000	01	00000	000	ミス
0000 0001 1110	00	00000	111	ミス
0000 1000 1100	00	00100	011	ヒット
1100 0001 1100	11	00000	111	ミス
0000 1011 0100	00	00101	101	ヒット
1000 1000 0100	10	00100	001	ミス

なお、アドレス1024の後の30は、1024によって別のタグのキャッシュラインがインデックス00000に格納されるため、ミスとなることに注意する。

また、各参照のあとのキャッシュの状態を示す。（それぞれのインデックスにおいて、8語=32bit格納できることに注意する）

0: インデックス00000のラインに、タグ..00で、データメモリ[0:31]が格納。
4: （ヒット）
16: （ヒット）
132: インデックス00100のラインに、タグ..00で、データメモリ[128:159]が格納。
232: インデックス00111のラインに、タグ..00で、データメモリ[224:255]が格納。
160: インデックス00101のラインに、タグ..00で、データメモリ[160:191]が格納。
1024: インデックス00000のラインに、タグ..01で、データメモリ[1024:1055]が格納。（置き換え）
30: インデックス00000のラインに、タグ..00で、データメモリ[0:31]が格納。（置き換え）
140: （ヒット）
3100: インデックス00000のラインに、タグ..11で、データメモリ[3072:3103]が格納。（置き換え）
180: （ヒット）
132: インデックス00100のラインに、タグ..10で、データメモリ[2176:2207]が格納。（置き換え）

5.3.4

置き換えの発生回数は4回

5.3.5

4 / 12 = 33%

5.3.6

インデックス	タグ（下2桁）	データ
00000	..11	メモリ[3072:3103]
00100	..10	メモリ[2176:2207]
00101	..00	メモリ[160:191]
00111	..00	メモリ[224:255]

5.4

5.4.1

L1はライトスルー方式なので、ストア命令の度に主記憶にも書き込む仕様である。主記憶への書き込みは遅いので、書き込み待ちのデータを保持するためにL1・L2間では必ずバッファを設けるべきである。

L2はライトバック方式なので、キャッシュが追い出される時に主記憶に書き込まれる仕様である。この方式では、キャッシュと主記憶の一貫性が失われている可能性があり、ダーティビットによるチェックが必要なので、データを保持するキャッシュがあったほうがよい。

5.4.2

L1はノー・ライト・アロケートなので、書き込みミスが発生した場合、直接L2を変更することになる（L1に変更はない）。
このL2でさらに書き込みミスが発生する場合、L2はライトアロケートなので、まず主記憶に書き込みを行ってからそれをL2に戻してくる。その際、書き込みを行おうとしているページがダーティ・ブロックであった場合は、まずそれを先に主記憶に書き込まねばならない。

5.4.3

（解答募集）

5.4.4 読み出し: 0.32, 書き込み: 0.4

CPI (cycle per instruction) = 2 とは、1命令あたり2サイクルのことなので、これを達成するのは、1サイクルあたり0.5命令を達成することと等価である。

読み出しのバンド幅は、1サイクルあたり発生するミスの確率に、読み出しで1回に読み出すブロックサイズ 64 をかける。

命令キャッシュについて、1命令あたり、ミスは0.30%で発生する。バンド幅は

0.5 * 0.003 * 64 = 0.096

データキャッシュからの読み出しについて、1命令あたり0.25の割合で発生し、ミスは2%で発生する。バンド幅は

0.5 * 0.25 * 0.02 * 64 = 0.16

データキャッシュへの書き込みについて、1命令あたり0.1の割合で発生し、ミスは2%で発生する。バンド幅は

0.5 * 0.1 * 0.02 * 64 = 0.064

これらを足し合わせて 0.096 + 0.16 + 0.064 = 0.32

書き込みは（ライトスルー方式であることから）毎回起こるが、1回につき 8 バイト（1ワード）である点に注意する。

0.5 * 0.1 * 8 = 0.4

5.4.5 読み出し: 0.32, 書き込み: 0.0672

読み出しは 5.4.4 と変わらない。

書き込みについて、今回は（ライトバック方式であることから）ミスが発生するときのみである。
1サイクルあたり0.5命令を達成したい下で、データの読み書きは合わせて 0.35 の割合で発生し、ミスは 2% で発生し、実際に書き込みが必要なのはダーティである 30 % で、毎回ブロックサイズ 64 バイトを書き込むので、

0.5 * 0.35 * 0.02 * 0.3 * 64 = 0.0672

5.4.6 （5.4.4の続きとして）読み出し: 0.4288, 書き込み: 0.536（5.4.5の続きとして）読み出し: 0.4288, 書き込み: 0.090048

1サイクルあたり約0.67命令を達成したい。すなわち、前の問題の 0.67 / 0.5 = 1.34 倍のバイト数が求められているので、5.4.4, 5.4.5 の結果に 1.34 を掛ければよい。

5.5

5.5.1 （ミス率）50%（影響）ブロックサイズが大きくなるとミス率は下がる。（種類）初期参照ミス

1ブロックが 32 バイトであることから、32 / 8 = 4 語格納できると考える。
入力が0, 2, 4, 6, 8, 10...のとき、0でミスが発生し、メモリ[0:3]がキャッシュに格納される。この格納された結果から2はヒットする。4でミスが発生し、メモリ[4:7]がキャッシュに格納される。この格納された結果から6はヒットする。
この繰り返しなので、ミス率は50%

5.5.2 16バイト: 100%, 64バイト: 25%, 128バイト: 12.5%、空間局所性

16バイト: 語数2
64バイト: 語数8
128バイト: 語数16

であることに注意して、5.5.1 と同様に考える。

5.5.3 0%

常に隣のメモリをストリームバッファに入れるようにしておけば、必ずヒットするようになる。

5.5.4 8

ミス・レイテンシとは、ミスが発生した際の遅延のことであるから、最適なブロックサイズは、（ミス率）×（ミス・レイテンシ）が最小になるものと言える。

今回は
8: 0.04 * 20 * 8
16: 0.03 * 20 * 16
32: 0.02 * 20 * 32
64: 0.015 * 20 * 64
128: 0.01 * 20 * 128

を計算して、最小となるのは 8

5.5.5 32

5.5.4 と同様。

8: 0.04 * (24 + 8)
16: 0.03 * (24 + 16)
32: 0.02 * (24 + 32)
64: 0.015 * (24 + 64)
128: 0.01 * (24 + 128)

を計算して、最小となるのは 32

5.5.4 128

ミス・レイテンシが一定であれば、ミス率が最も小さいものが最適。

5.6

5.6.1 P1: 1.52GHz, P2: 1.11GHz

クロック周波数 = 1 / サイクル時間 である。

今回は L1 のヒット時間をそのままサイクル時間とみなせるということなので、

P1: 1 / 0.66 ns = 1.52 GHz
P2: 1 / 0.90 ns = 1.11 GHz

5.6.2 P1: 6.26 ns, P2: 5.1 ns

AMAT（平均メモリアクセス時間）= ヒットした場合のアクセス時間 + ミス率 × ミスペナルティ

P1: 0.66 + 0.08 * 70 = 6.26 ns
P2: 0.90 + 0.06 * 70 = 5.1 ns

5.6.3 P1: 12.53, P2: 7.35、速いのはP2

CPIを求める問題なので、1命令あたりのサイクル数を考える。

P1について:

問題文より、基本的には1サイクルである。
これに加え、メモリのストールを考慮すると、まず毎回命令キャッシュから命令を読み出す際に起こりうるミスを含める必要がある。1サイクルが 0.66ns とみなせることから、これは 0.08 * (70 / 0.66) = 約8.48 サイクル。
さらに、主記憶へのアクセスにより発生するミスも含める必要がある。これは 0.36 * 0.08 * (70 / 0.66) = 約3.05。
以上より、1 + 8.48 + 3.05 = 12.53

P2について:

同様に考えて、

1 + 0.06 * (70 / 0.9) + 0.36 * 0.06 * (70 / 0.9) = 1 + 4.67 + 1.68 = 7.35

P2の方が1命令にかかるサイクル数が少ないので、処理が速い。

5.6.4

（解答募集）

5.6.5

（解答募集）

5.6.6

（解答募集）

5.7

5.7.1

末尾2ビットは「バイトオフセット」であることに注意する。

また、ブロック内オフセットは log 2 = 1 ビット
インデックスは log (24/(3*2)) = 2 ビット

2進アドレス （下8桁）	タグ （下3桁）	インデックス
0000 0011	000	00
1011 0100	101	10
0010 1011	001	01
0000 0010	000	00
1011 1111	101	11
0101 1000	010	11
1011 1110	101	11
0000 1110	000	01
1011 0101	101	10
0010 1100	001	01
1011 1010	101	11
1111 1101	111	11

3ウェイ・セット・アソシアティブであることに注意すると、キャッシュの遷移は以下の通り
（H/M は ヒット/ミス）

00	00	00	01	01	01	10	10	10	11	11	11	H/M
000												M
000						101						M
000			001			101						M
000			001			101						H
000			001			101			101			M
000			001			101			101	010		M
000			001			101			101	010		H
000			001	000		101			101	010		M
000			001	000		101			101	010		H
000			001	000		101			101	010		H
000			001	000		101			101	010		H
000			001	000		101			101	010	111	M

5.7.2

フル・アソシアティブにおいてはインデックスは存在しない。またブロック・サイズが1語なので、ブロック内オフセットも存在しない。

C1

2進アドレス （下8桁）	タグ （下6桁）
0000 0011	000000
1011 0100	101101
0010 1011	001010
0000 0010	000000
1011 1111	101111
0101 1000	010110
1011 1110	101111
0000 1110	000011
1011 0101	101101
0010 1100	001011
1011 1010	101110
1111 1101	111111

連想数は8。LRUに注意する。

								H/M
000000								M
000000	101101							M
000000	101101	001010						M
000000	101101	001010						H
000000	101101	001010	101111					M
000000	101101	001010	101111	010110				M
000000	101101	001010	101111	010110				H
000000	101101	001010	101111	010110	000011			M
000000	101101	001010	101111	010110	000011			H
000000	101101	001010	101111	010110	000011	001011		M
000000	101101	001010	101111	010110	000011	001011	101110	M
000000	101101	111111	101111	010110	000011	001011	101110	M

5.7.3 LRU: 75%, MRU: 75%, Best: 58.3%

今回は、ブロック内オフセットが 1bit になる。

2進アドレス （下8桁）	タグ （下5桁）
0000 0011	00000
1011 0100	10110
0010 1011	00101
0000 0010	00000
1011 1111	10111
0101 1000	01011
1011 1110	10111
0000 1110	00001
1011 1101	10110
0010 1100	00101
1011 1010	10111
1111 1101	11111

連想度は4。

LRUの場合:

				H/M
00000				M
00000	10110			M
00000	10110	00101		M
00000	10110	00101		H
00000	10110	00101	10111	M
00000	01011	00101	10111	M
00000	01011	00101	10111	H
00000	01011	00001	10111	M
10110	01011	00001	10111	M
10110	00101	00001	10111	M
10110	00101	00001	10111	H
10110	00101	11111	10111	M

ミス率 9 / 12 = 75%

MRUの場合:

				H/M
00000				M
00000	10110			M
00000	10110	00101		M
00000	10110	00101		H
00000	10110	00101	10111	M
00000	10110	00101	01011	M
00000	10110	00101	10111	M
00000	10110	00101	00001	M
00000	10110	00101	00001	H
00000	10110	00101	00001	H
00000	10110	10111	00001	M
00000	10110	11111	00001	M

ミス率 9 / 12 = 75%

最も良い低いミス率を達成するには、複数回出てくるタグを残しておくのがよい。

残すべきなのは 00000, 10111, 10110, 00101, 10111（先の方が、より早く消してもよいもの）

これに気をつけると、

				H/M
00000				M
00000	10110			M
00000	10110	00101		M
00000	10110	00101		H
00000	10110	00101	10111	M
01011	10110	00101	10111	M
01011	10110	00101	10111	H
00001	10110	00101	10111	M
00001	10110	00101	10111	H
00001	10110	00101	10111	H
00001	10110	00101	10111	H
11111	10110	00101	10111	M

ミス率

7 / 12 = 約58.3%

5.7.4

（解答募集）

5.7.5

（解答募集）

5.7.6

（解答募集）

5.11

5.11.1

ページサイズが 4KiB = 4096 バイトであることから、アドレスのうち下位 log 4096 = 12 ビットがページ内オフセットとして用いられ、その上のビットが仮想ページ番号となる。

まず、処理する仮想アドレスについて整理する。

仮想アドレス	2進数	仮想ページ番号
4669	0001 0010 0011 1101	1
2227	0000 1000 1011 0011	0
13916	0011 0110 0101 1100	3
34587	1000 0111 0001 1011	8
48870	1011 1110 1110 0110	11
12608	0011 0001 0100 0000	3
49225	1100 0000 0100 1001	12

各参照について

• 4669: TLBにタグ1はないのでページテーブルを見る。上から1番目は有効ビットが立っていないので、ページフォールトが発生する。ディスクから対応する物理ページを引っ張ってくる。「ディスクからページを取り込まなければならない場合、すでに使用されている最大のページ番号の次のページ番号を使用する」とあるので、物理ページ番号は**13**とする。また、TLBも更新する。この場合、有効ビットが立っていないキャッシュをまず最初に交換すると考えておく。

有効	タグ	物理ページ番号
1	11	12
1	7	4
1	3	6
1	1	13 (New!)

• 2227: TLBにタグ0はないのでページテーブルを見る。上から0番目は有効ビットが立っており、ページテーブル中でのヒットとなる。TLBを更新する。（特に理由はないが）一番上が最も昔に更新されたキャッシュとみなして、それを交換する。

有効	タグ	物理ページ番号
1	0	5 (New!)
1	7	4
1	3	6
1	1	13

• 13916: TLBにタグ3があるのでTLB中でのヒットとなる。

有効	タグ	物理ページ番号
1	0	5
1	7	4
1	3	6 (Hit!)
1	1	13

• 34587: TLBにタグ8はないのでページテーブルを見る。上から8番目は有効ビットが立っていないので、ページフォールトが発生する。ディスクから対応する物理ページを引っ張ってくる。物理ページ番号は**14**とする。また、TLBも更新する。

有効	タグ	物理ページ番号
1	0	5
1	8	14 (New!)
1	3	6
1	1	13

• 48870: TLBにタグ11はないのでページテーブルを見る。上から11番目は有効ビットが立っており、ページテーブル中でのヒットとなる。TLBを更新する。

有効	タグ	物理ページ番号
1	0	5
1	8	14
1	3	6
1	11	12 (New!)

• 12608: TLBにタグ3があるのでTLB中でのヒットとなる。

有効	タグ	物理ページ番号
1	0	5
1	8	14
1	3	6 (Hit!)
1	11	12

• 49225: TLBにタグ12はないのでページテーブルを見る。上から12番目は（そもそも存在せず）有効ビットが立っていないので、ページフォールトが発生する。ディスクから対応する物理ページを引っ張ってくる。物理ページ番号は**15**とする。また、TLBも更新する。

有効	タグ	物理ページ番号
1	12	15
1	8	14
1	3	6 (Hit!)
1	11	12

ページテーブルは最終的に以下の通り。

有効	物理ページまたはディスク上
1	5
1	13
0	Disk
1	6
1	9
1	11
0	Disk
1	4
1	14
0	Disk
1	3
1	12
1	15

5.11.2

ページサイズが 16KiB であることから、アドレスのうち下位 14 ビットがページ内オフセットとして用いられ、その上のビットが仮想ページ番号となる。

仮想アドレス	2進数	仮想ページ番号
4669	0001 0010 0011 1101	0
2227	0000 1000 1011 0011	0
13916	0011 0110 0101 1100	0
34587	1000 0111 0001 1011	2
48870	1011 1110 1110 0110	2
12608	0011 0001 0100 0000	0
49225	1100 0000 0100 1001	3

• 4669: TLBにタグ0はないのでページテーブルを見る。上から0番目は有効ビットが立っており、ページテーブル中でのヒットとなる。TLBを更新する。

有効	タグ	物理ページ番号
1	11	12
1	7	4
1	3	6
1	0	5 (New!)

• 2227: TLBにタグ0があるのでTLB中でのヒットとなる。

有効	タグ	物理ページ番号
1	11	12
1	7	4
1	3	6
1	0	5 (Hit!)

• 13916: TLBにタグ0があるのでTLB中でのヒットとなる。

有効	タグ	物理ページ番号
1	11	12
1	7	4
1	3	6
1	0	5 (Hit!)

• 34587: TLBにタグ2はないのでページテーブルを見る。上から2番目は有効ビットが立っていないので、ページフォールトが発生する。ディスクから対応する物理ページを引っ張ってくる。物理ページ番号は**13**とする。また、TLBも更新する。

有効	タグ	物理ページ番号
1	2	13 (New!)
1	7	4
1	3	6
1	0	5

• 48870: TLBにタグ2があるのでTLB中でのヒットとなる。

有効	タグ	物理ページ番号
1	2	13 (Hit!)
1	7	4
1	3	6
1	0	5

• 12608: TLBにタグ0があるのでTLB中でのヒットとなる。

有効	タグ	物理ページ番号
1	2	13
1	7	4
1	3	6
1	0	5 (Hit!)

• 49225: TLBにタグ3があるのでTLB中でのヒットとなる。

有効	タグ	物理ページ番号
1	2	13
1	7	4
1	3	6 (Hit!)
1	0	5

ページテーブルは最終的に以下の通り。

有効	物理ページまたはディスク上
1	5
0	Disk
1	13
1	6
1	9
1	11
0	Disk
1	4
0	Disk
0	Disk
1	3
1	12

ページサイズを大きくすることの

メリット: ミスが減る。
デメリット: 小さい単位でのメモリ管理ができなくなるので無駄が大きい。ミスが発生した際のディスクアクセス量が増えてしまう。

5.11.3

（（前半の）解答募集）

※ 仮にTLBをダイレクトマップやセットアソシアティブと仮定した場合、アドレスのどの部分をインデックスとしてみなせばいいのか不明（おそらく13〜14bitあたり？）。

（後半）

ページテーブル自体は主記憶にあるため、仮にTLBを備えていない場合、アドレスを引くのに毎回主記憶にアクセスせねばならず、遅い。したがってTLBを備えることは重要。

5.11.4

（解答募集）

5.11.5

（解答募集）

5.11.6

（解答募集）

5.12

5.12.1 （PTE）2^31（メモリ）8GiB

ページサイズが 4KiB であることから、アドレスのうち下位 12 bitがページ内オフセットとして用いられ、その上の上位 31 ビットが仮想アドレス番号になる。
よって PTE は 2^31 必要。

さらに、PTEサイズは4バイトなので、ページテーブルを格納するのに必要なメモリは 4 * 2^31 = 8GiB

5.12.2 31レベル、31回

イメージとしては https://images.app.goo.gl/Hi2kDdjQLfyRmZfg8 のテーブルが31個ある感じ。

5.12.3 （PTE）2^32

物理アドレスから仮想アドレスを引くテーブルを考える。

PTE は、物理アドレスが 16GiB なので、16 GiB / 4 KiB = 2^32

（（後半の）解答募集）

5.12.4

有効ビットが立っていないのはキャッシュの内容が主記憶に入っていないとき。

5.12.5

TLBミス

（（後半の）解答募集）

5.12.6

割り込み（読み取り専用なので）