Advanced Microarchitecture
Chapter: 5.3 Advanced Microarchitecture Level: 1 — Recognition (MCQ + Matching + True/False with justification) Time limit: 20 minutes Total marks: 40
Section A — Multiple Choice (1 mark each; 10 marks)
Choose the single best answer.
Q1. A processor that issues and executes more than one instruction per clock cycle using multiple execution units is called:
- (a) Pipelined
- (b) Superscalar
- (c) VLIW
- (d) SISD
Q2. In Tomasulo's algorithm, the hardware structures that hold instructions waiting for operands are the:
- (a) Reorder buffer entries
- (b) Reservation stations
- (c) Physical register file
- (d) Branch target buffer
Q3. The primary purpose of the Reorder Buffer (ROB) is to:
- (a) Predict branch outcomes
- (b) Provide in-order commit/retirement of out-of-order results
- (c) Store the return address
- (d) Rename registers dynamically
Q4. A 2-bit saturating counter predictor requires how many consecutive mispredictions to switch from "strongly taken" to "predict not taken"?
- (a) 1
- (b) 2
- (c) 3
- (d) 4
Q5. Register renaming primarily eliminates which type(s) of hazards?
- (a) True data (RAW) dependencies
- (b) WAR and WAW (false) dependencies
- (c) Structural hazards only
- (d) Control hazards only
Q6. A Branch Target Buffer (BTB) stores:
- (a) The 2-bit counter history only
- (b) The predicted target address of a taken branch
- (c) The reorder buffer index
- (d) The renamed register mapping
Q7. A tournament predictor works by:
- (a) Always using global history
- (b) Using a selector to choose between two component predictors
- (c) Removing all mispredictions
- (d) Storing return addresses in a stack
Q8. The Return Address Stack (RAS) is used to predict targets of:
- (a) Conditional branches
- (b) Indirect jumps in general
- (c) Function returns
- (d) Loop back-edges
Q9. VLIW architectures differ from superscalar processors mainly because:
- (a) They dynamically schedule at run time
- (b) The compiler statically packs independent operations into one long instruction word
- (c) They cannot execute floating point
- (d) They forbid out-of-order execution in hardware and software
Q10. Spectre and Meltdown are examples of:
- (a) Compiler optimization bugs
- (b) Speculative-execution side-channel vulnerabilities
- (c) Cache coherence protocols
- (d) VLIW scheduling techniques
Section B — Matching (1 mark each; 8 marks)
Q11. Match each term (1–8) to its best description (A–H).
| # | Term |
|---|---|
| 1 | Common Data Bus (CDB) |
| 2 | Simultaneous Multithreading (SMT) |
| 3 | Speculative execution |
| 4 | Static branch prediction |
| 5 | TAGE predictor |
| 6 | Out-of-order execution |
| 7 | Reservation station |
| 8 | Meltdown |
| Letter | Description |
|---|---|
| A | Executes instructions as operands become ready, not in program order |
| B | Broadcasts results to waiting units in Tomasulo's algorithm |
| C | Executing instructions past an unresolved branch, before commit |
| D | Multiple hardware threads share execution resources in the same cycle |
| E | Fixed prediction rule decided at compile time (e.g. backward-taken) |
| F | Uses multiple tagged tables indexed by increasingly long history lengths |
| G | Buffers an instruction and its source operands/tags until it can issue |
| H | Reads privileged kernel memory via a transient out-of-order load |
Section C — True/False with Justification (2 marks each; 22 marks)
1 mark for correct T/F, 1 mark for a correct one-line justification.
Q12. In Tomasulo's algorithm, register renaming is achieved implicitly via reservation station tags. (T/F + why)
Q13. A 1-bit branch predictor mispredicts exactly twice for each loop that iterates many times before exiting. (T/F + why)
Q14. Out-of-order execution allows instructions to commit (retire) out of program order. (T/F + why)
Q15. The Branch Target Buffer is only needed for not-taken branches. (T/F + why)
Q16. In VLIW, hazards between operations in the same bundle are resolved by hardware interlocks at run time. (T/F + why)
Q17. SMT improves throughput mainly by keeping execution units busy when one thread stalls. (T/F + why)
Q18. A WAR hazard represents a true data dependency that cannot be removed by renaming. (T/F + why)
Q19. The reorder buffer enables precise exceptions by ensuring architectural state is updated in program order. (T/F + why)
Q20. Spectre requires the attacker to run privileged (kernel-mode) code. (T/F + why)
Q21. A Return Address Stack is a LIFO structure whose predictions can become wrong if call/return nesting is very deep and overflows it. (T/F + why)
Q22. In a 2-bit saturating counter, being in a "weakly taken" state means one correct prediction will move it to "strongly taken." (T/F + why)
Answer keyMark scheme & solutions
Section A — MCQ (1 mark each)
Q1 — (b) Superscalar. Superscalar = multiple instructions issued/executed per cycle via replicated functional units. VLIW does this too but relies on the compiler, so (b) is the general answer.
Q2 — (b) Reservation stations. RS hold instructions plus operands/tags until all sources are ready, then dispatch to a functional unit.
Q3 — (b) In-order commit/retirement. The ROB tracks program order so results retire in order, giving precise state.
Q4 — (b) 2. From strongly-taken (11), two consecutive mispredicts go 11→10→01, and 01 is the first "predict not taken" state. So 2 mispredictions.
Q5 — (b) WAR and WAW. Renaming removes name (false) dependencies; RAW (true) dependencies remain.
Q6 — (b) Predicted target address. BTB caches the target PC of taken branches so the target is known at fetch.
Q7 — (b) Selector chooses between two predictors. A meta/selector predictor picks the better of (typically) a local and a global predictor.
Q8 — (c) Function returns. RAS pushes return address on call, pops on return.
Q9 — (b) Compiler statically packs independent ops. VLIW moves scheduling to the compiler; superscalar schedules in hardware.
Q10 — (b) Speculative-execution side channels. Both leak data via microarchitectural (cache) side channels from transient execution.
Section B — Matching (1 mark each)
Q11: 1→B, 2→D, 3→C, 4→E, 5→F, 6→A, 7→G, 8→H.
Section C — True/False with Justification (1 + 1 marks)
Q12 — TRUE. The tag written into a register's status and carried by RS entries serves as a rename tag, mapping a logical register to a producing station, so WAR/WAW hazards are removed. (1 T + 1 justification)
Q13 — TRUE. A 1-bit predictor mispredicts once at loop exit (predicts taken but it's not) and once on the first iteration of the next entry (still predicts not-taken from the exit). Hence 2 mispredicts per full loop execution. (Accept explanation of the two boundary mispredicts.)
Q14 — FALSE. OoO allows out-of-order execution, but commit/retirement is kept in order by the ROB to preserve precise architectural state.
Q15 — FALSE. The BTB is used for taken branches; it supplies the target so fetch can redirect. Not-taken branches simply fetch the fall-through path.
Q16 — FALSE. In VLIW the compiler guarantees operations in a bundle are independent (or inserts NOPs); there are no run-time interlocks in the classic model.
Q17 — TRUE. SMT fills idle issue slots/functional units with instructions from another thread while one thread stalls (e.g. on a cache miss), raising utilization/throughput.
Q18 — FALSE. A WAR is a false (name) dependency; it can be removed by register renaming. True dependency is RAW.
Q19 — TRUE. The ROB updates architectural registers/memory in program order, so an exception is taken at the correct instruction boundary (precise exceptions).
Q20 — FALSE. Spectre tricks a victim's own code (e.g. via mistrained branch prediction) to speculatively access data; it does not require attacker kernel code. (Meltdown crosses the privilege boundary directly.)
Q21 — TRUE. RAS is a fixed-depth LIFO; deeper nesting than its capacity overflows/wraps, corrupting entries and causing return mispredictions.
Q22 — TRUE. States: 00 SN, 01 WN, 10 WT, 11 ST. From weakly-taken (10), a correct (taken) prediction increments to 11 = strongly-taken.
Mark distribution
- Section A: 10 × 1 = 10
- Section B: 8 × 1 = 8
- Section C: 11 × 2 = 22
- Total = 40
[
{"claim":"2-bit counter needs 2 mispredicts to leave strongly-taken (11) into predict-not-taken (<=1)","code":"state=3\nmis=0\nwhile state>=2:\n state-=1\n mis+=1\nresult=(mis==2)"},
{"claim":"From weakly-taken (2) one correct(taken) prediction reaches strongly-taken (3)","code":"state=2\nstate=min(state+1,3)\nresult=(state==3)"},
{"claim":"2-bit state encoding: SN=0,WN=1,WT=2,ST=3 ordering is monotone","code":"states=[0,1,2,3]\nresult=(states==sorted(states) and states[3]==3)"},
{"claim":"Matching mapping counts to 8 unique letters","code":"m={1:'B',2:'D',3:'C',4:'E',5:'F',6:'A',7:'G',8:'H'}\nresult=(len(set(m.values()))==8 and len(m)==8)"}
]