# 107 台大計系

# Computer Architecture

## 1

### a. please explain what architecture support is needed for this.

- programs 可以並行執行
- program之間通常不能互相讀取
  想到Virtual Memory
  - page table - 每個process有自己的page table，OS分配記憶體和更新page table，process之間便不會衝突，即可實現這兩點
  - MMU - 需要一個額外硬體轉換VA→PA

Operating System 9th pg.376 - We first need to make sure…
Computer Architecture 5th pg.44 - what is architecture?
Computer Orgnization 5th pg.432 - why page table?

### b. please explain out-of-order execution(OOOE) is indispensable performance feature on modern processors.

- 考慮以下instruction

    lw	$t0, 20($s2)
    addu	$t1, $t0, $t2  #load-use ，用forwarding仍需花費one cycle stall
    sub	$s4, $s4, $t3

> 在 in-order execution 情況下，即使 sub 與 lw、addu 沒有資料相依， sub 仍必須等待，如果 lw 發生 cahce miss 的話，要存取 memory 拿資料，可能會花費相當多 clock cycle，OOOE 可以避免這種情況。

張凡課本下冊，動態多重分發處理器

### c. 解釋 speculatively 的優缺點

- 好處
  - 猜對可以提早執行，盡量使得pipeline是滿的
- 壞處
  - 猜錯要有回復機制
  - 需要額外硬體架構

張凡課本下冊，speculation

### d. 造成例外的原因，現代處理器如何處理 out-of-order 造成的例外及正確性

- 造成原因
  - interrupt
  - TLB miss
  - cache miss…etc
- 如何處理?
  - in-order execution
    找出那個 instruction 發生 exception，並以此為交界線，在這之前的要執行完，在這之後的全都 flush
  - OOOE
    1.仍然保持對 instruction 的順序標記，以方便控制哪個要執行哪個要flush
    2.全部flush

https://www.cs.virginia.edu/~cr4bd/3330/S2017/notes/20170316-part2-slides-1up.pdf

### e. 解釋 cache 的重要性，及為何 cache data 會有不同

- cache重要在於，memory為Von Neumann model的瓶頸，搬資料的速度相對CPU來說太慢了。
- 為何不同？

http://www.cc.ntu.edu.tw/chinese/epaper/0045/201806204508.html

## 2

### (f)

每台電腦需處理 10 15 N B y t e s 10 15 N B y t e s
，每個 disk 裝 10 15 N D B y t e s 10 15 N D B y t e s
，transfer rate 250MB/sec

- min : seek 一次
  - 5(ms)+10 15 N D 250 M 10 15 N D 250 M
    (sec)=4∗10 6 N D 4∗10 6 N D
    (sec)
- max : 每個 block 都 seek 一次
  - 需 10 12 N D 10 12 N D
    個 block
  - 5∗10 12 N D 5∗10 12 N D
    (ms) + 10 15 N D 250 M 10 15 N D 250 M
    (sec)=5.004∗10 9 N D 5.004∗10 9 N D
    (sec)

### (g)

- 10 15 N 8∗(16∗2 30)10 15 N 8∗(16∗2 30)
  = 2 13 N 2 13 N
  (sec)

### (h)

- 兩兩合併 類似 full binary tree 結構
- 100∗l g N 100∗l g N

### (i)

- 所需時間 : (f)>(g)>(h) → 可透過換成 SSD 來改善

## 3 Which processor below isn’t affected by Meltdown?

- 找沒有支援OOOE的CPU

( C ) - intel Itanium

張凡課本下冊，VLIW

## 4

## 5 Which statement below is FALSE…?

(b) - 是8-bit 不是32-bit

https://cloud.google.com/blog/products/gcp/an-in-depth-look-at-googles-first-tensor-processing-unit-tpu

## 6 Which … does’t exploit parallelism?

(b)

### a. ILP

### b. none

### c. ILP (superscalar)

### d. TLP、DLP

張凡課本，定義ILP
Computer Orgnization 5th pg.525
Computer Architecture 5th pg.38

## 7 Branch prediction is more important…

(T)

- 隨著pipeline stage增加，從IF到branch決定的stage越長的話，表示要flush的instruction
  越多

張凡課本，control hazard

## 8 Two instructions … may not cause data hazard…

(T)

- forwarding

張凡課本，data hazard

## 9 If VIPT is used, one RAM data…

(F)
張凡課本，virtual index virtual tag(VIVT)

# Operating System

## 10

### a

- TLB為page table的cache
  - 目的是為了節省每次都要去存取在memory的page table的時間

1. CPU產生VA
2. 餵給TLB
3. hit的話，將PA餵給Cache
   miss的話 ，將原來的VA餵給page table找到PA
   ┌───┐ ┌───┐hit┌────┐
   │CPU │→│TLB │-→│Cache│
   └───┘ └───┘ – └────┘
   TLB miss↓
   ┌───────┐
   │page table│
   └───────┘

張凡課本，TLB

### b 1.F12C 2.2A9D 3.Page fault

### c inverted page table && multilevel page table

### d Please discribe possible method… and discuss the performance

- 不能更換CPU
  - possible method
    每一次mode switch的時候，都把TLB清空以確保user mode不會使用到kernel mode的PPN
  - The performance impacts
    每一次mode switch都要重新填滿TLB，如果mode switch極度頻繁時，等同於沒有TLB這個元件，都要去放在momory的page table拿PPN。
    →單一instruction/data的latency會提高，AMAT加一個memory access

Operating System 9th pg.374
https://stackoverflow.com/questions/21887797/what-is-the-overhead-of-a-context-switch

## 11 In Linux scheduler, what performance is improved using red-black-tree …

CFQ, deadline(恐龍書上只提到 CFQ )
理論上紅黑樹為一棵 balanced tree，在上面 search、delete 只要花費 O(lg n) 的時間

補充：

- CFQ(completely fair scheduler)
  I/O scheduler，用 rtree 紀錄 I/O request 與 priority。
- deadline
  用來保證 I/O request 在一定時間內被服務，以避免 starvation。
- noop
  採用 FIFO 法則，早期(2.4版)以前只有這個 scheduler

https://lwn.net/Articles/184495/
https://www.infradead.org/~mchehab/kernel_docs/unsorted/rbtree.html

## 12

## 13

### 實際舉硬碟排班例子 (1)FCFS會比SSTF優的 (2)FCFS比SSTF差

- #### <這個要湊的話技巧就是讓SSTF要一直折返來折返去的，而FCFS順順的跑就好>

- (1)現在硬碟總共有0~99(track) 目前在50
  TRACK要求順序:48.51.55
  FCFS:50->48->51->55 所以距離是:2+7=9
  SSTF:50->51->48->55 距離是1+3+7=11

- #### <基本上SSJF都會比FCFS好，所以這很好湊>

- (2)現在硬碟總共有0~99(track) 目前在50
  TRACK要求順序:60.52
  FCFS:50->62->52 所以距離是:22
  SSJF:50->52->60 距離是:10

## 14 Binary Semaphore to Counting Semaphor

    Semaphore S1,S2
    int c
    wait(S)
    {
        wait(s1);
        c = c-1;
        if (c < 0)
        {
            signal(s1);
            wait(s2);
        }
        else signal(s1);
    }
    signal(s)
    {
        wait(s1);
        c = c+1;
        if(c <= 0)
        {
            signal(s2);
        }
        signal(s1);
    }