# HW 7
###### tags: `計算機組織`, `109-2`

## Q1

### Ans

#### 5.12.1
Virtual Address 有 $43$ 位，也就是說總共會有 $2^{43}$ Byte

每個 Page 有 $4$ KiB，等於 $4 \times 2^{10} = 2^{12}$ Byte。所以總共會有 $2^{43} / 2^{12}$，一共 $2^{31}$ 個 page

每個 page 需要一個門牌 PTE，一個 PTE 4 Byte，所以我們需要 $2^{31} \times 4 = 2^{33}$ Byte 的空間來存這些門牌 PTE

#### 5.12.2
把每個 table 都切成 1-bit 大小，總共會需要 $31$ level

而每個 level 都需要一個 reference 來確定位置，因此 ref 數也是 $31$

#### 5.12.3
Inverted Page Table 是以實體記憶體為對象來製作，這裡安裝了 $16$ GiB，也就是 $16 \times 2^{10}$ KiB

除以每 page 的大小，總共會有 $16 \times 2^{10} / 4 = 2^{12}$ 個 page；所以我們需要 $2^{12}$ 個 PTE。

Hash 完，如果洗出來的值不會有重複的問題，那發生 TLB miss 時就只需要跑一次 reference；反之，存取次數會依重複程度提升。

## Q2

### Ans

#### 5.12.4
TLB 被重新 fetch

#### 5.12.5
因為 TLB 沒有 VA Page 30 的資訊，所以會被丟一個 TLB Miss，叫他去 Page Table 撈。

如果要讀的 TLB Entry 剛好在 cache 裡面的話，Software managed TLB 會比 hardware managed TLB 快。

#### 5.12.6
因為 VA Page 200 被標記為 Read-Only，所以會被丟一個 write protection exception

## Q3

### Ans

#### 5.13.1

| Access | Hit? | Evict | S0 I0 | S0 I1 | S1 I0 | S1 I1 |
|:------:|:----:|:-----:|:-------:|:-------:|:-----:|:-----:|
| 0 | miss | - | Mem[0] | | | |
| 2 | miss | - | Mem[0] | Mem[2] | | |
| 4 | miss | 0 | Mem[4] | Mem[2] | | |
| 8 | miss | 0 | Mem[4] | Mem[8] | | |
| 10 | miss | 0 | Mem[10] | Mem[8] | | |
| 12 | miss | 0 | Mem[10] | Mem[12] | | |
| 14 | miss | 0 | Mem[14] | Mem[12] | | |
| 16 | miss | 0 | Mem[14] | Mem[16] | | |
| 0 | miss | 0 | Mem[0] | Mem[16] | | |

0 Hits!

#### 5.13.2

| Access | Hit? | Evict | S0 I0 | S0 I1 | S1 I0 | S1 I1 |
|:------:|:----:|:-----:|:------:|:-------:|:-----:|:-----:|
| 0 | miss | - | Mem[0] | | | |
| 2 | miss | - | Mem[0] | Mem[2] | | |
| 4 | miss | 0 | Mem[0] | Mem[4] | | |
| 8 | miss | 0 | Mem[0] | Mem[8] | | |
| 10 | miss | 0 | Mem[0] | Mem[10] | | |
| 12 | miss | 0 | Mem[0] | Mem[12] | | |
| 14 | miss | 0 | Mem[0] | Mem[14] | | |
| 16 | miss | 0 | Mem[0] | Mem[16] | | |
| 0 | HIT! | - | Mem[0] | Mem[16] | | |

1 Hits!

#### 5.13.3
酷耶！丟硬幣，那我們就照題目說的，正面替換 Index=0；反面替換 Index=1
喔對，我手邊沒有硬幣，所以我拿祖傳的NTR骰子來丟：NTR=反 LDO=正，希望你不要介意

| Access | Hit? | Evict | S0 I0 | S0 I1 | S1 I0 | S1 I1 | 正反? |
|:------:|:----:|:-----:|:-------:|:-------:|:-----:|:-----:|:-----:|
| 0 | miss | - | Mem[0] | | | | |
| 2 | miss | - | Mem[0] | Mem[2] | | | |
| 4 | miss | 0 | Mem[4] | Mem[2] | | | O=正 |
| 8 | miss | 0 | Mem[4] | Mem[8] | | | T=反 |
| 10 | miss | 0 | Mem[10] | Mem[8] | | | L=正 |
| 12 | miss | 0 | Mem[10] | Mem[12] | | | N=反 |
| 14 | miss | 0 | Mem[10] | Mem[14] | | | R=反 |
| 16 | miss | 0 | Mem[10] | Mem[16] | | | R=反 |
| 0 | miss | 0 | Mem[0] | Mem[16] | | | L=正 |

0 Hit!

## Q4

### Ans

#### 5.13.4
從以上的實驗中，使用 MRU 替換最近使用的 bit 這個策略為最佳，因為沒有 evict 掉唯一重複的 Mem[0]，所以可達到最大的 1 Hit。

但是這只是因應這個極端的測資而言 (只有一個重複，而且重複的是第一個使用的)，真實的情況可能不會如此。

#### 5.13.5
上面提到真實的情況不會像這次實驗的測資。一般而言，存取的記憶體比較會偏向同一塊附近 (Local locality)，當然也可能會有鬆散的情形。但是，我們無法預測 CPU 要存取的順序會是如何，所以我們也很難依照順序來決定相應的演算法。

#### 5.13.6
剛剛提過，我們無法預測 CPU 要存取的順序，所以我們只能放馬後炮，在得知順序後才來惋惜為什麼沒有在當時做出正確的選擇。例如存取 <0, 2, 4, 6, 2, 0>，我們在得知結果後當然會選擇留下 0 和 2，但是在當下不知道的情形，若我們選擇 4, 6，那將會鎩羽而歸。生命無常，這題也是。

## Q5

5.(20%)
Suppose that we need to take 150 seconds to resolve one problem when the problem size is one. The running time of the problem is composed of an initialization phase which takes 20 seconds and cannot be parallelized, and a problem resolving phase which can be perfectly parallelized and grows quadratic with growing problem size.

[5.1]. Please show the speedup for the above application as a function of the number of processors ( p ) and the problem size ( n ).
[5.2]. Please show the execution time and the speedup of the application with problem size one 1, if the application is parallelized and run on 2 processors?
[5.3]. Please show the execution time and the speedup of the application when the problem size is increased to 5 and run on 4 processors? And on 8 processors?

### Ans

#### 5.1
我們可以看到這個問題有不能被平行化的 Init Phase $20$ 秒，和可以被平行化，且複雜度為平方的 Problem Resolving Phase，基礎時間 $130$ 秒

我們可以列出執行時間函式 $T = 20 + \frac{130 \times n^2}{p}$
Speed-up $S = \frac{20+(130\times n^2 / 1)}{20+(130\times n^2 / p)}$

#### 5.2
依照關係式直接熱血開算

$T = 20 + \frac{130 \times 1^2}{2} = 85$ 秒
$S = \frac{130}{85} \approx 152.94\%$

#### 5.3
熱血開算

$n=5,\ p=4$
- $T = 20 + \frac{130 \times 5^2}{4} = 832.5$ 秒
- $S = \frac{20+130 \times 5^2 / 1}{20+130 \times 5^2/4} \approx 392.79\%$

$n=5,\ p=8$
- $T = 20 + \frac{130 \times 5^2}{8} = 426.25$ 秒
- $S = \frac{20+130 \times 5^2 / 1}{20+130 \times 5^2/8} \approx 767.16\%$