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

# Disclaimer

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

# Table of contents

<font color="Red">解答募集: 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</font>


- [5.1](#51)
- [5.2](#52)
- [5.3](#53)
- [5.4](#54)
- [5.5](#55)
- [5.6](#56)
- [5.7](#57)
- [5.11](#511)
- [5.12](#512)

# 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進アドレス <br>（下8桁）     |      タグ<br>（下2桁） |    インデックス    | ヒット/ミス |
|:----------:|:------------------:|:-----------:|:------------:|
| 00<font color="Red">00 00</font>11 | 00 | 0000 | ミス |
| 10<font color="Red">11 01</font>00 | 10 | 1101 | ミス |
| 00<font color="Red">10 10</font>11 | 00 | 1010 | ミス |
| 00<font color="Red">00 00</font>10 | 00 | 0000 | ヒット |
| 10<font color="Red">11 11</font>11 | 10 | 1111 | ミス |
| 01<font color="Red">01 10</font>00 | 01 | 0110 | ミス |
| 10<font color="Red">11 11</font>10 | 10 | 1111 | ヒット |
| 00<font color="Red">00 11</font>10 | 00 | 0011 | ミス |
| 10<font color="Red">11 01</font>01 | 10 | 1101 | ヒット |
| 00<font color="Red">10 11</font>00 | 00 | 1011 | ミス |
| 10<font color="Red">11 10</font>10 | 10 | 1110 | ミス |
| 11<font color="Red">11 11</font>01 | 11 | 1111 | ミス |

#### 5.2.2

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

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

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

| 2進アドレス <br>（下8桁）     |      タグ<br>（下2桁） |    インデックス    | ヒット/ミス |
|:----------:|:------------------:|:-----------:|:------------:|
| 00<font color="Red">00 0</font>011 | 00 | 000 | ミス |
| 10<font color="Red">11 0</font>100 | 10 | 110 | ミス |
| 00<font color="Red">10 1</font>011 | 00 | 101 | ミス |
| 00<font color="Red">00 0</font>010 | 00 | 000 | ヒット |
| 10<font color="Red">11 1</font>111 | 10 | 111 | ミス |
| 01<font color="Red">01 1</font>000 | 01 | 011 | ミス |
| 10<font color="Red">11 1</font>110 | 10 | 111 | ヒット |
| 00<font color="Red">00 1</font>110 | 00 | 001 | ミス |
| 10<font color="Red">11 0</font>101 | 10 | 110 | ヒット |
| 00<font color="Red">10 1</font>100 | 00 | 101 | **ヒット** |
| 10<font color="Red">11 1</font>010 | 10 | 111 | **ヒット** |
| 11<font color="Red">11 1</font>101 | 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進アドレス <br>（下8桁）     |      タグ<br>（下3桁） |    インデックス    | ヒット/ミス |
|:----------:|:------------------:|:-----------:|:------------:|
| 000<font color="Red">0 00</font>11 | 000 | 000 | ミス |
| 101<font color="Red">1 01</font>00 | 101 | 101 | ミス |
| 001<font color="Red">0 10</font>11 | 001 | 010 | ミス |
| 000<font color="Red">0 00</font>10 | 000 | 000 | ヒット |
| 101<font color="Red">1 11</font>11 | 101 | 111 | ミス |
| 010<font color="Red">1 10</font>00 | 010 | 110 | ミス |
| 101<font color="Red">1 11</font>10 | 101 | 111 | ヒット |
| 000<font color="Red">0 11</font>10 | 000 | 011 | ミス |
| 101<font color="Red">1 01</font>01 | 101 | 101 | ヒット |
| 001<font color="Red">0 11</font>00 | 001 | 011 | ミス |
| 101<font color="Red">1 10</font>10 | 101 | 110 | ミス |
| 111<font color="Red">1 11</font>01 | 111 | 111 | ミス |

ミス率: 9 / 12

C2

| 2進アドレス <br>（下8桁）     |      タグ<br>（下3桁） |    インデックス    | ヒット/ミス |
|:----------:|:------------------:|:-----------:|:------------:|
| 000<font color="Red">0 0</font>011 | 000 | 00 | ミス |
| 101<font color="Red">1 0</font>100 | 101 | 10 | ミス |
| 001<font color="Red">0 1</font>011 | 001 | 01 | ミス |
| 000<font color="Red">0 0</font>010 | 000 | 00 | ヒット |
| 101<font color="Red">1 1</font>111 | 101 | 11 | ミス |
| 010<font color="Red">1 1</font>000 | 010 | 11 | ミス |
| 101<font color="Red">1 1</font>110 | 101 | 11 | ヒット |
| 000<font color="Red">0 1</font>110 | 000 | 01 | ミス |
| 101<font color="Red">1 0</font>101 | 101 | 10 | ヒット |
| 001<font color="Red">0 1</font>100 | 001 | 01 | **ヒット** |
| 101<font color="Red">1 1</font>010 | 101 | 11 | **ヒット** |
| 111<font color="Red">1 1</font>101 | 111 | 11 | ミス |

ミス率: 7 / 12

C3

| 2進アドレス <br>（下8桁）     |      タグ<br>（下3桁） |    インデックス    | ヒット/ミス |
|:----------:|:------------------:|:-----------:|:------------:|
| 000<font color="Red">0</font> 0011 | 000 | 0 | ミス |
| 101<font color="Red">1</font> 0100 | 101 | 1 | ミス |
| 001<font color="Red">0</font> 1011 | 001 | 0 | ミス |
| 000<font color="Red">0</font> 0010 | 000 | 0 | ヒット |
| 101<font color="Red">1</font> 1111 | 101 | 1 | **ヒット** |
| 010<font color="Red">1</font> 1000 | 010 | 1 | ミス |
| 101<font color="Red">1</font> 1110 | 101 | 1 | ヒット |
| 000<font color="Red">0</font> 1110 | 000 | 0 | **ヒット** |
| 101<font color="Red">1</font> 0101 | 101 | 1 | ヒット |
| 001<font color="Red">0</font> 1100 | 001 | 0 | ヒット |
| 101<font color="Red">1</font> 1010 | 101 | 1 | ヒット |
| 111<font color="Red">1</font> 1101 | 111 | 1 | ミス |

ミス率: 5 / 12

<br>

このように、ミス率は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のキャッシュと近そうだというのは分かる）

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

```python
>>> 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] |
| ブロック内 <br>オフセット | 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進アドレス <br>（下12桁）     |      タグ<br>（下2桁） |    インデックス  | ブロック内<br>オフセット  | ヒット/ミス |
|:----------:|:------------------:|:-----------:|:------------:|:------------:|
| 00<font color="Red">00 000</font>0 0000 | 00 | 00000 | 000 | ミス |
| 00<font color="Red">00 000</font>0 0100 | 00 | 00000 | 001 |ヒット |
| 00<font color="Red">00 000</font>1 0000 | 00 | 00000 | 100 |ヒット |
| 00<font color="Red">00 100</font>0 0100 | 00 | 00100 | 001 |ミス |
| 00<font color="Red">00 111</font>0 1000 | 00 | 00111 | 010 |ミス |
| 00<font color="Red">00 101</font>0 0000 | 00 | 00101 | 000 |ミス |
| 01<font color="Red">00 000</font>0 0000 | 01 | 00000 | 000 |ミス |
| 00<font color="Red">00 000</font>1 1110 | 00 | 00000 | 111 |**ミス** |
| 00<font color="Red">00 100</font>0 1100 | 00 | 00100 | 011 |ヒット |
| 11<font color="Red">00 000</font>1 1100 | 11 | 00000 | 111 |ミス |
| 00<font color="Red">00 101</font>1 0100 | 00 | 00101 | 101 |ヒット |
| 10<font color="Red">00 100</font>0 0100 | 10 | 00100 | 001 |ミス |

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

<br>


また、各参照のあとのキャッシュの状態を示す。（それぞれのインデックスにおいて、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]`が格納。<font color="Red">（置き換え）</font>
`30`: インデックス`00000`のラインに、タグ`..00`で、データ`メモリ[0:31]`が格納。<font color="Red">（置き換え）</font>
`140`: （ヒット）
`3100`: インデックス`00000`のラインに、タグ`..11`で、データ`メモリ[3072:3103]`が格納。<font color="Red">（置き換え）</font>
`180`: （ヒット）
`132`: インデックス`00100`のラインに、タグ`..10`で、データ`メモリ[2176:2207]`が格納。<font color="Red">（置き換え）</font>

<br>

**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

<font color="Red">（解答募集）</font>

#### 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

<font color="Red">（解答募集）</font>

#### 5.6.5

<font color="Red">（解答募集）</font>

#### 5.6.6

<font color="Red">（解答募集）</font>

## 5.7

#### 5.7.1

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

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

| 2進アドレス <br>（下8桁）     |      タグ<br>（下3桁） |    インデックス    |
|:----------:|:------------------:|:-----------:|
| 000<font color="Red">0 0</font>011 | 000 | 00 | ミス |
| 101<font color="Red">1 0</font>100 | 101 | 10 | ミス |
| 001<font color="Red">0 1</font>011 | 001 | 01 | ミス |
| 000<font color="Red">0 0</font>010 | 000 | 00 | ヒット |
| 101<font color="Red">1 1</font>111 | 101 | 11 | ミス |
| 010<font color="Red">1 1</font>000 | 010 | 11 | ミス |
| 101<font color="Red">1 1</font>110 | 101 | 11 | ヒット |
| 000<font color="Red">0 1</font>110 | 000 | 01 | ミス |
| 101<font color="Red">1 0</font>101 | 101 | 10 | ヒット |
| 001<font color="Red">0 1</font>100 | 001 | 01 | ミス |
| 101<font color="Red">1 1</font>010 | 101 | 11 | ミス |
| 111<font color="Red">1 1</font>101 | 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進アドレス <br>（下8桁）     |      タグ<br>（下6桁） |  
|:----------:|:------------------:|
| <font color="Red">0000 00</font>11 | 000000 | 000 | ミス |
| <font color="Red">1011 01</font>00 | 101101 | 101 | ミス |
| <font color="Red">0010 10</font>11 | 001010 | 010 | ミス |
| <font color="Red">0000 00</font>10 | 000000 | 000 | ヒット |
| <font color="Red">1011 11</font>11 | 101111 | 111 | ミス |
| <font color="Red">0101 10</font>00 | 010110 | 110 | ミス |
| <font color="Red">1011 11</font>10 | 101111 | 111 | ヒット |
| <font color="Red">0000 11</font>10 | 000011 | 011 | ミス |
| <font color="Red">1011 01</font>01 | 101101 | 101 | ヒット |
| <font color="Red">0010 11</font>00 | 001011 | 011 | ミス |
| <font color="Red">1011 10</font>10 | 101110 | 110 | ミス |
| <font color="Red">1111 11</font>01 | 111111 | 111 | ミス |

連想数は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進アドレス <br>（下8桁）     |      タグ<br>（下5桁） |  
|:----------:|:------------------:|
| <font color="Red">0000 0</font>011 | 00000 | 000 | ミス |
| <font color="Red">1011 0</font>100 | 10110 | 101 | ミス |
| <font color="Red">0010 1</font>011 | 00101 | 010 | ミス |
| <font color="Red">0000 0</font>010 | 00000 | 000 | ヒット |
| <font color="Red">1011 1</font>111 | 10111 | 111 | ミス |
| <font color="Red">0101 1</font>000 | 01011 | 110 | ミス |
| <font color="Red">1011 1</font>110 | 10111 | 111 | ヒット |
| <font color="Red">0000 1</font>110 | 00001 | 011 | ミス |
| <font color="Red">1011 1</font>101 | 10110 | 101 | ヒット |
| <font color="Red">0010 1</font>100 | 00101 | 011 | ミス |
| <font color="Red">1011 1</font>010 | 10111 | 110 | ミス |
| <font color="Red">1111 1</font>101 | 11111 | 111 | ミス |

連想度は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

<font color="Red">（解答募集）</font>

#### 5.7.5

<font color="Red">（解答募集）</font>

#### 5.7.6

<font color="Red">（解答募集）</font>

## 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番目は有効ビットが立っていないので、<font color="Red">ページフォールト</font>が発生する。ディスクから対応する物理ページを引っ張ってくる。「ディスクからページを取り込まなければならない場合、すでに使用されている最大のページ番号の次のページ番号を使用する」とあるので、物理ページ番号は**`13`**とする。また、TLBも更新する。この場合、有効ビットが立っていないキャッシュをまず最初に交換すると考えておく。

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

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

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

- `13916`: TLBにタグ3があるので<font color="Red">TLB中でのヒット</font>となる。

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


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

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

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

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

- `12608`: TLBにタグ3があるので<font color="Red">TLB中でのヒット</font>となる。

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

- `49225`: TLBにタグ12はないのでページテーブルを見る。上から12番目は（そもそも存在せず）有効ビットが立っていないので、<font color="Red">ページフォールト</font>が発生する。ディスクから対応する物理ページを引っ張ってくる。物理ページ番号は**`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番目は有効ビットが立っており、<font color="Red">ページテーブル中でのヒット</font>となる。TLBを更新する。

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

- `2227`: TLBにタグ0があるので<font color="Red">TLB中でのヒット</font>となる。

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

- `13916`: TLBにタグ0があるので<font color="Red">TLB中でのヒット</font>となる。

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

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

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

- `48870`: TLBにタグ2があるので<font color="Red">TLB中でのヒット</font>となる。

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

- `12608`: TLBにタグ0があるので<font color="Red">TLB中でのヒット</font>となる。

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

- `49225`: TLBにタグ3があるので<font color="Red">TLB中でのヒット</font>となる。

|有効|タグ|物理ページ番号|
|:--:|:--:|:--|
|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

<font color="Red">（（前半の）解答募集）</font>

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

<br>

（後半）

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

#### 5.11.4

<font color="Red">（解答募集）</font>

#### 5.11.5

<font color="Red">（解答募集）</font>

#### 5.11.6

<font color="Red">（解答募集）</font>

## 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

<font color="Red">（（後半の）解答募集）</font>

#### 5.12.4

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

#### 5.12.5

TLBミス

<font color="Red">（（後半の）解答募集）</font>

#### 5.12.6

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