Computer Architecture Final Exam Answer Sheet

# Computer Architecture Final Exam Answer Sheet > 劉子雍．108502523 > 資訊工程學系三年級 A 班 <style> .markdown-body li + li { padding-top: 0 !important; } .markdown-body table th, .markdown-body table td { padding: 2px 6px; } </style> --- ## 1. | Time | CPU request | Bus activity | State transition and action of P1 | State transition and action of P2 | State transition and action of P3 | |:---------------------:|:-----------:|:----------------:|:----------------------------------------------------------------:|:-----------------------------------------------:|:---------------------------------------------------:| | T1 (P1 writes X) | CPU Write | Invalidate for X | Shared -> Exclusive (Place invalidate on bus) | Shared -> Invalid (No action) | Shared -> Invalid (No action) | | T2 (P2 reads X) | CPU Read | Read miss for X | Exclusive -> Shared (Write-back block; abort memory access) | Invalid -> Shared (Place read miss on bus) | Invalid (No action) | | T3 (P3 writes X) | CPU Write | Write miss for X | Shared -> Invalid (No action) | Shared -> Invalid (No action) | Invalid -> Exclusive (Place write miss on bus) | ## 2. $AMAT_{prefetch} = HitTime \\ \qquad\qquad\qquad\quad + MissRate \times (PrefetchHitRate \times 2 \\ \qquad\qquad\qquad\qquad\qquad\qquad\qquad + (1 - PrefetchHitRate) \times MissPenalty) \\ \qquad\qquad\qquad = 2 + 0.02 \times (0.2 \times 2 + (1 - 0.2) \times 100) = 3.608$ $AMAT = HitTime + EffectiveMissRate \times MissPenalty \\ \Rightarrow 3.608 = 2 + EffectiveMissRate \times 100 \\ \Rightarrow EffectiveMissRate = 0.01608 = 1.608\%$ ==**ANS**==: $0.01608 = 1.608\%$ ## 3. One possible recovery order: 1. Use Block "0" of the Diagonal Parity to recover Block "0" of the Row Parity. 2. Use Block "3" of the Diagonal Parity to recover Block "3" of the Data Disk 1. 3. Use Block "0" of the Row Parity to recover Block "2" of the Data Disk 1. 4. Use Block "2" of the Data Disk 0, Block "3" of the Data Disk 1, Block "4" of the Data Disk 2, Block "0" of the Data Disk 3 to recover Block "1" of the Row Parity. 5. Use Block "2" of the Diagonal Parity to recover Block "2" of the Row parity. 6. Use Block "2" of the Row parity to recover Block "4" of the Data Disk 1. 7. Use Block "1" of the Diagonal Parity to recover Block "1" of the Data Disk 1. 8. Use Block "0" of the Data Disk 0, Block "1" of the Data Disk 1, Block "2" of the Data Disk 2, Block "3" of the Data Disk 3 to recover Block "4" of the Row Parity. ## 4. ### (a) It uses fully associative scheme to reduce more miss rate due to the exorbitant miss penalty of virtual memory. ### (b) It uses write-back strategy to reduce more miss penalty (by reducing times of repeated writes to the same memory location) due to the exorbitant miss penalty of virtual memory. ## 5. PC relative address is an addressing mode that a displacement is added to the program counter, which is useful for conditional branch across several instrucitons, because the target is often near the current instruction. It also permits the code to run independently of where it is loaded (position independence) and make good use of space for MIPS J-type instructions. ## 6. $\text{Cache size} = \text{Associativity} \times 2^{\text{Index size}} \times 2^{\text{Offset size}} \\ \Rightarrow 2^{19} = 2 \times 2^{\text{Index size}} \times 2^{7} \\ \Rightarrow \text{Index size} = 11$ $\text{Address size} = \text{Tag size} + \text{Index size} + \text{Offset size} \\ \Rightarrow 32 = \text{Tag size} + 11 + 7 \\ \Rightarrow \text{Tag size} = 14$ ==**ANS**==: $\text{Index size} = 11,\ \text{Tag size} = 14$ ## 7. A Directory-Based Scheme is more suitable than a Snooping protocol for large scaled machines with large processor counts, because a Snooping protocol uses broadcasting. For a Snooping protocol, frequent snooping on a cache causes a race with an access from a processor, thus it can increase cache access time and power consumption. Each of the requests has to be broadcast to all nodes in a system. It means that the size of the (physical or logical) bus and the bandwidth it provides must grow, as the system (the number of processors) becomes larger. Therefore, a Snooping protocol's scalability is poorer than a Directory-Based Scheme's. ## 8. No, non-blocking cache cannot reduce miss rate. Non-blocking cache just allows data cache to continue to supply cache hits during one or multiple misses, making miss handling non-blocking, which reduces miss penalty, not miss rate.