1. [30%] Consider the following figure.

(1) What is the name of the TLB’s input (Symbol A in the figure)? (Hint: XXX address.)
(2) What is the name of the TLB’s output (Symbol B in the figure)?
(3) What is the name of this type of cache (with B as its input)? (Hint: XXX cache.)
(4) Does the cache aliasing occur in the cache design shown in the figure (Yes or No)? Explain your answer.
(5) “We could have a hit in the cache, and get a TLB miss and a page table miss.” Is the statement true (Yes or No)? Explain your answer.
(6) Consider the processor operating at 1GHz. The processor stalls during a cache miss and has the following properties: (i) a cache access time of 2 clock cycles for a hit, (ii) a miss penalty of 100 clock cycles, and (iii) a miss rate of 0.03 misses per instruction. Please compute the average memory access time.

(4) No. Since every logical address of different process will convert to different physical address and the design uses a physically addressed cache.
(5) No. Page table miss $\to$ data are not in memory $\to$ data are not in cache.
(6) $\text{AMAT = } (2 + 0.03 \times 100) \times 1 \text{ns} = 5 \text{ns}$

2. [10%] Assume the MIPS processor with 5 stages of the pipeline:

(i) IF for the instruction fetch stage,
(ii) ID for the instruction decode/register file read stage,
(iii) EX for the execution stage,
(iv) MEM for the memory access stage, and
(v) WB for the write-back stage.

.wp-block-code{border:0;padding:0}.wp-block-code>div{overflow:auto}.shcb-language{border:0;clip:rect(1px,1px,1px,1px);-webkit-clip-path:inset(50%);clip-path:inset(50%);height:1px;margin:-1px;overflow:hidden;padding:0;position:absolute;width:1px;word-wrap:normal;word-break:normal}.hljs{box-sizing:border-box}.hljs.shcb-code-table{display:table;width:100%}.hljs.shcb-code-table>.shcb-loc{color:inherit;display:table-row;width:100%}.hljs.shcb-code-table .shcb-loc>span{display:table-cell}.wp-block-code code.hljs:not(.shcb-wrap-lines){white-space:pre}.wp-block-code code.hljs.shcb-wrap-lines{white-space:pre-wrap}.hljs.shcb-line-numbers{border-spacing:0;counter-reset:line}.hljs.shcb-line-numbers>.shcb-loc{counter-increment:line}.hljs.shcb-line-numbers .shcb-loc>span{padding-left:.75em}.hljs.shcb-line-numbers .shcb-loc::before{border-right:1px solid #ddd;content:counter(line);display:table-cell;padding:0 .75em;text-align:right;-webkit-user-select:none;-moz-user-select:none;-ms-user-select:none;user-select:none;white-space:nowrap;width:1%}I1: ADD R1, R2, R0

I2: LW  R2, 16(R1)

I3: LW  R1, 4(R3)

I4: SUB R5, R3, R4Code language: plaintext (plaintext)

(1) Find all data dependencies in the instruction sequence.
(2) Find all hazards in the instruction sequence for the processor with and without forwarding.
(3) Sometimes, even with forwarding, we would have to stall one stage for a data hazard. Fortunately the software technique, Reordering Code, would be adopted to avoid the pipeline stalls. Please state if the instruction sequence suffers from a data hazard that cannot be resolved by the forwarding (Yes or No). If your answer is Yes, please list your reordered code.

3. [10%] Determine whether each of the following statements is True (T) or False (F), and explain your answer.

(1) Strong scaling is not limited by Amdahl’s law.
(2) Both SMPs and message-passing computers rely on locks for synchronization.
(3) Multithreading technology in CPUs help reduce the memory latency.

4. [10%] When multiple processes need to cooperate, there is a choice between shared memory the inter-process communication (IPC). Compare and contrast these two techniques. Make sure to clarify the role of the operating system in each.

5. [10%] What is the cause of thrashing? How does the system detect thrashing? Once it detects thrashing, what can the system do to eliminate this problem?

(1) Thrashing occurs when the virtual memory of the system is overused, causing a constant state of paging and page-fault.
(2) CPU utilization: low, I/O paging disk: high.
(3) Decrease the degree of multi-programming.

6. [20%] Consider the following snapshot of a system:

(1) What is the content of the matrix Need?
(2) Is the system in a safe state? Why?
(3) If a request from process P1 arrives for (1, 3, 5, 1), can the request be granted immediately? Why?

(1)

Need
ABCD
0642
0410
0002
0750

(2) Yes, we found a safe sequence $P2 \to P1 \to P3 \to P4.$
(3) No, the request is more than the Need.

7. [10%] Assume we have a demand-paged memory. The page table is held in registers. It takes 8 milliseconds to service a page fault if an empty page is available or the replaced page is not modified, and 20 milliseconds if the replaced page is modified. Memory access time is 100 nanoseconds. Assume that the page to be replaced is modified 70 percent of the time. What is the maximum acceptable page fault rate for an effective access time of no more than 200 nanoseconds?