###### tags: `co` `thu`
# 計算機組織107
## 1. (10%) 請說明在 DRAM 內部定址設計上，是如何做到位址線接腳數可以用到較少的數目。請以 16Mbit DRAM 晶片為例

- A $16Mbits$ chip can be organised as a $2048\times 2048\times 4bits$ array
- Multiplex row address and column address
- $16Mbits=16M$ cell$\times bit=4M$ cell $\times 4bit$
- $4M=2^{22}$(22 addrress lines, $A_0~A_{21}$)
- $2^{22}=2^{11}(Row)\times 2^{11}(Column)$
- $11$ pins to address($2^{11}=2048$)
- Adding one more pin double range of values so $\times 4$ capacity($2^{12}\times 4$ Capacity with $2^{11}$)
## 2. (10%) How about the different between cache memory (SRAM) and RAM? (HINT: from organization, cost, speed, size, and applications)

| | organization | cost |speed|size|application|
| -------- | -------- | -------- |-------- |-------- |-------- |
| SRAM | 一個flip-flop和兩個電晶體，不須更新電路(6個transistors和2個NOT gate） | 貴 |快 |小 |Cache |
| DRAM | 1bit有一個電容和一個電晶體，須更新電路| 便宜 |慢 |大 |Main memory |

## 3.(20%) Please draw these two cache diagrams for MIPS, this cache specification of processor is listed as bellows:
- The size of maximum memory (RAM) space is 4G Bytes
- The size of cache memory is 4M Bytes
- Cache line size is 4 Bytes (32bits)
You can refer the following cache diagram of MIPS (4-way) for drawing MIPS processor cache diagram

(a) Please draw the diagram for 2-way set-associate cache (tag ?bit : set ?bit : word ?bit)please calculate the total SRAM space needed for this 4MB cache memory.

$4GB=2^{32}bytes$，address line 總共有32條
$4Bytes = 2^{2}$，word共2bits
$\frac{4MB}{4B}=2^{10}$，在direct mapping的情況下line有10bits，2-way set-associate的情況下，set則為$10-1=9bits$
$tag = 32-9-2=21bits$
$\frac{32+(32-9-2)+1}{32}=\frac{54}{32}\times 4KB=6.75KB$

(b) Please draw the diagram for 8-way set-associate cache (tag ?bit : set ?bit : word ?bit),please calculate the total SRAM space needed for this 4MB cache memory.

$4GB=2^{32}bits$，address line 總共有32條
$4Bytes=2^{2}$，word共2bits
$\frac{4MB}{4B} = 2^{10}$，$10-3=7$，set則為7bits
$tag=32-2-7=23$
$\frac{32+23+1}{32}=\frac{56}{32}\times 4MB=7MB$

## 4.(15%) Please calculate the average access time of this hard disk for transferring a 16GB video data file. As we known, the seek time of this HD is 0.8ms, spindle speed is 15000rpm, sectors per track is 1024, and byes per sector is 4096 bytes (advanced format).
公式為
$$T_a=T_s+\frac{1}{2r}+\frac{b}{rN}$$
so：
$$T_a=0.8+\frac{1}{2\cdot \frac{15000}{60}}+\frac{16\cdot 2^{30}}{\frac{15000}{60}\cdot 4096\cdot 1024}$$
$$T_a=0.8+\frac{1+2^{13}}{500}$$

## 5.(20%) Please draw diagrams and describe the functions in detail for RAID 1, RAID 3, RAID 5 and RAID 6
RAID 1：
1、兩組以上硬碟相互做鏡像
2、Data is striped across disks
3、兩份複製的資料分別放在不同的disk
4、Read from either
5、Write to both
6、回復容易(更換disk後重新做鏡像)
7、昂貴

| DISK1 | DISK2 |
| -------- | -------- |
| $A1$ | $A1'$ |
| $A2$ | $A2'$ |
| $A3$ | $A3'$ |
| $A4$ | $A4'$ |

RAID 3：
1、只有一個磁碟是多餘的
2、使用同位元錯誤檢測碼，資料遺失時可用此技術重建資料
3、轉移速率高

| DISK1 | DISK2 |DISK3 |
| -------- | -------- |-------- |
| $A1$ | $A2$ |$P_{A1、A2}$ |
| $A3$ | $A4$ |$P_{A3、A4}$ |
| $A5$ | $A6$ |$P_{A5、A6}$ |
| $A7$ | $A8$ |$P_{A7、A8}$ |

RAID 5：
1、同位元錯誤檢測循環分配在每個磁碟
2、N個disk用戶需要N+1個disk
3、常用於網路服務器

| DISK1 | DISK2 |DISK3 |
| -------- | -------- |-------- |
| $A1$ | $A2$ |$P_{A1、A2}$ |
| $A3$ | $P_{A3、A4}$ | $A4$ |
| $P_{A5、A6}$ | $A6$ |$A5$ |

RAID 6：
1、兩個同位元檢測碼
2、儲存在不同disk的單獨block中
3、N個disk用戶需要N+2個disk
4、需要3個disk同時壞掉才會資料遺失
5、有write penalty

| DISK1 | DISK2 |DISK3 |Disk4|
| -------- | -------- |-------- |-------- |
| $A1$ | $A2$ |$P_{A1、A2}$ |$Q_{A1、A2}$ |
| $A3$ | $P_{A3、A4}$ | $Q_{A3、A4}$ | $A4$ |
| $P_{A5、A6}$ | $Q_{A5、A6}$ |$A5$ |$A6$ |

## 6.(15%) Please describe the functions of DMA in detail

1、DMA controller 從CPU接管I/O
2、會偷取CPU閒置時間
3、允許一個設備直接讀寫系統記憶體而不需CPU參與

## 7.(15%) 請問 Pipeline 處理器是如何結合分支預測(Branch Prediction)與延遲分支(Delay Branch)來處理控制危障？(請用有條件跳躍（分支）當控制危障)

分支預測為當遇到有條件跳躍指令時，在 Fetch 階段時就會執行分支預測。如果預測結果是 taken，就會將下一個要執行的指令地址更新為跳躍目標地址；如果預測結果是 not taken，就會繼續往下執行原本的指令流程。

延遲分支為在pipeline中的某個階段才做出決策，如果預測結果是taken，就會暫停pipeline的流程，直到控制危障的指令已經Execute階段，再決定是否真的執行跳躍指令。如果預測結果是 not taken，則會繼續往下執行原本的指令流程。

所以當遇到有條件跳躍指令時，處理器會先進行分支預測，若發生控制危障再使用延遲分支。
### 不確定