Problem 1
A high-performance microprocessor operates with a clock cycle time of $t_{clk} = 1.00\text{ ns}$ ($1.00\text{ GHz}$). The processor employs a two-level cache memory hierarchy with the following access parameters: - Level 1 (L1) Cache: Hit time = $1\text{ clock cycle}$, local miss rate $m_1 = 4.0\%$ - Level 2 (L2) Cache: Hit time = $8\text{ clock cycles}$, local miss rate $m_2 = 12.0\%$ - Main Memory: Access latency = $100\text{ clock cycles}$ What is the Average Memory Access Time (AMAT) of this system, in nanoseconds (ns)?
- A1.25 ns (1.25 clock cycles)
- B1.42 ns (1.42 clock cycles)
- C1.65 ns (1.65 clock cycles)
- D1.80 ns (1.80 clock cycles)correct
Show the solution
**Step 1: Formulate Average Memory Access Time (AMAT)** From the FE Reference Handbook (Computer Systems / Cache Memory Hierarchy): For a two-level cache system: $$AMAT = \text{Hit Time}_{L1} + \text{Miss Rate}_{L1} \times \text{Miss Penalty}_{L1}$$ where the L1 miss penalty is the time required to service the request through the L2 cache: $$\text{Miss Penalty}_{L1} = \text{Hit Time}_{L2} + \text{Miss Rate}_{L2} \times \text{Miss Penalty}_{L2}$$ $$\text{Miss Penalty}_{L2} = \text{Main Memory Access Time}$$ **Step 2: Calculate L1 Miss Penalty in Clock Cycles** Given: - $\text{Hit Time}_{L2} = 8\text{ cycles}$ - $\text{Miss Rate}_{L2} = 12.0\% = 0.12$ - $\text{Main Memory Time} = 100\text{ cycles}$ $$\text{Miss Penalty}_{L1} = 8 + (0.12 \times 100) = 8 + 12 = 20\text{ clock cycles}$$ **Step 3: Calculate Total AMAT in Clock Cycles** Given: - $\text{Hit Time}_{L1} = 1\text{ cycle}$ - $\text{Miss Rate}_{L1} = 4.0\% = 0.04$ $$AMAT = 1 + (0.04 \times 20) = 1 + 0.80 = 1.80\text{ clock cycles}$$ **Step 4: Convert AMAT to Nanoseconds** $$AMAT(\text{ns}) = AMAT(\text{cycles}) \times t_{clk} = 1.80\text{ cycles} \times 1.00\text{ ns/cycle} = 1.80\text{ ns}$$ Conclusion: The Average Memory Access Time is **1.80 ns** (1.80 clock cycles). Distractor Analysis: - Option A: 1.25 clock cycles - Option B: 1.42 clock cycles - Option C: 1.65 clock cycles - Option D: 1.80 clock cycles (Correct)
Problem 2
A 5-stage classic RISC processor pipeline (IF, ID, EX, MEM, WB) executes a representative benchmark program with the following instruction distribution: - Load instructions ($LW$): $25.0\%$ - Store instructions ($SW$): $10.0\%$ - ALU operations (R-type): $50.0\%$ - Conditional Branches ($BEQ$): $15.0\%$ Hardware characteristics: - Full data forwarding is implemented; however, an ALU instruction immediately following a dependent load incurs a mandatory 1-cycle Load-Use stall. Exactly $40.0\%$ of loads are followed by an immediate dependent instruction. - Branch decisions are resolved in the ID stage with a 1-cycle branch penalty. Exactly $60.0\%$ of branches are taken. What is the effective average Clock Cycles Per Instruction ($CPI$) of this processor?
- A1.05
- B1.10
- C1.14
- D1.19correct
Show the solution
**Step 1: Determine the Ideal Baseline CPI** From the FE Reference Handbook (Computer Systems / Pipelining Performance): In an ideal 5-stage pipeline without structural, data, or control hazards, one instruction completes every clock cycle: $$CPI_{ideal} = 1.00$$ **Step 2: Calculate Data Hazard Stalls (Load-Use Penalty)** A Load-Use data hazard occurs when an instruction in the decode stage requires the result of a preceding load currently in execution, requiring 1 bubble cycle despite forwarding: $$\text{Stalls}_{data} = (\text{Load Frequency}) \times (\text{Probability of Dependent Instruction}) \times (\text{Stall Cycles})$$ $$\text{Stalls}_{data} = 0.250 \times 0.400 \times 1 = 0.100\text{ stall cycles/instruction}$$ **Step 3: Calculate Control Hazard Stalls (Branch Penalty)** Branches are resolved in stage 2 (ID). When a branch is taken, the fetched sequential instruction is flushed, incurring a 1-cycle penalty: $$\text{Stalls}_{branch} = (\text{Branch Frequency}) \times (\text{Branch Taken Probability}) \times (\text{Penalty Cycles})$$ $$\text{Stalls}_{branch} = 0.150 \times 0.600 \times 1 = 0.090\text{ stall cycles/instruction}$$ **Step 4: Compute Total Effective CPI** $$CPI_{effective} = CPI_{ideal} + \text{Stalls}_{data} + \text{Stalls}_{branch} = 1.00 + 0.100 + 0.090 = 1.190 \approx 1.19$$ Conclusion: The effective CPI of the processor is **1.19**. Distractor Analysis: - Option A: Assumes complete hardware forwarding eliminating all load-use stalls. - Option B: Overestimates stall cycles for independent instructions. - Option C: Calculates CPI without memory branch instruction contributions. - Option D: Correct. Determines pipeline CPI = 1 + data hazard stall cycles = 1.19.
Problem 3
Which TWO of the following statements regarding hardware cache coherence and the MESI (Modified, Exclusive, Shared, Invalid) snooping protocol in symmetric multiprocessing (SMP) architectures are correct?
- AA cache line in the Exclusive (E) state contains clean data matching main memory and is guaranteed to reside in only one processor core's local cache, permitting that core to write to it immediately by transitioning to Modified (M) without generating a bus invalidation broadcast.
- BWhen a processor core initiates a write to a cache block currently in the Shared (S) state, it can perform the write locally without transmitting any invalidation request over the shared coherence bus.
- CA cache line in the Modified (M) state holds dirty data that differs from main memory; the owning cache is responsible for supplying the line directly upon snooping a read request or writing it back upon eviction.
- DThe MESI snooping protocol completely eliminates the need for hardware snooping logic on shared memory interconnects by relying entirely on compile-time static software hazard annotations.
Show the solution
**Step 1: Understand MESI Protocol States and Invariants** From the FE Reference Handbook (Computer Systems / Architecture / Multi-Core Cache Coherence): 1. **Exclusive (E) State**: The line is present only in the current cache and is clean (matches main memory). Because no other core holds a copy, a write hit on an Exclusive line can proceed instantaneously without generating bus invalidation traffic, silently transitioning the line to the Modified (M) state. $\implies$ **Statement A is correct.** 2. **Modified (M) State**: The line is present only in the current cache and is dirty (contains updated data not yet written to main memory). The owning core must intercept read requests (snarfing/supplying data) and write back the block upon eviction. $\implies$ **Statement C is correct.** **Step 2: Evaluate Distractors** - Statement B is false: In the Shared (S) state, other cores may hold copies. A core wishing to write must broadcast a Bus Upgrade (BusUpgr / Invalidation) request on the bus so all other caches transition their copies to Invalid (I). - Statement D is false: The MESI protocol is a pure hardware snooping (or directory-based) mechanism implemented directly in silicon within the L1/L2 cache controllers and memory bus; it does not rely on software annotations. Conclusion: Statements **A** and **C** are correct.