Lecture 31: Problem Solving VI

What this lecture covers

This is a live problem-solving session where teaching assistants work through the previous year's final exam for the ETH Zurich Digital Design and Computer Architecture course, question by question. Rather than presenting new material, it shows how to approach and reason through exam-style problems on topics spanning the whole course: Boolean algebra, finite state machines, the ISA/microarchitecture distinction, Verilog, memory technologies, performance metrics, out-of-order execution, GPU SIMD utilization, data prefetching, cache associativity, and pipelining.

Because it revisits topics from earlier in the course rather than introducing them, it works best as exam preparation after you've seen the corresponding lectures. Watching it, you can expect to pick up problem-solving techniques and common mistakes to avoid, such as how to simplify Boolean expressions efficiently, how to build a data-flow graph from a Tomasulo snapshot, and how to avoid mis-averaging weighted speedup fractions.

Key ideas

• Sum-of-products simplification: group truth-table terms that differ by one variable and cancel complementary pairs (B or B-not is always 1) instead of jumping straight to Karnaugh maps.
• NAND/NOR-only implementations: any expression can be rebuilt from only NOR (or only NAND) gates by double-negating it and applying De Morgan's law, then realizing each inverted single-input signal as a gate fed by two copies of the same signal.
• Moore vs. Mealy FSMs: in a Moore machine outputs are attached to states; in a Mealy machine outputs are attached to transitions, so the same underlying state logic can be reused with different output labeling.
• ISA vs. microarchitecture: the ISA is what software can see and control (register counts, addressable memory size, whether a cache policy is software-selectable); the microarchitecture is how the hardware implements that interface (pipeline width, number of ALUs, cache bank count).
• Weighted speedup: sum each application's shared IPC divided by its alone IPC; you must divide before summing, not sum the numerators and denominators separately.
• Tomasulo reconstruction: start from the reservation-station entry with no unresolved source tags, since that identifies the instruction that hasn't depended on anything else, then work outward using the register alias table's tags.
• SIMD utilization: it's the ratio of active-thread instructions actually executed to the instructions that would run if every thread in a warp took the same path.
• Prefetcher coverage and bandwidth overhead: coverage is prefetched-and-used requests over total memory requests without prefetching; overhead is total memory traffic with prefetching over traffic without it, counting duplicate prefetch requests only once.

Walkthrough

Boolean circuit minimization (0:00)

The first question gives a 4-bit input with two outputs, factorial and D4 (divisible by four), and asks for a truth table followed by simplified sum-of-products expressions. The presenter builds the truth table from the word description, then simplifies by grouping terms that differ in exactly one variable and canceling out the resulting B or B-not and A or A-not pairs. For a follow-up part that asks for the factorial output built only from NOR gates, the segment shows the standard trick: simplify the expression normally, then double-negate it, apply De Morgan's law to flip ANDs/ORs, and realize any leftover single-variable NOT by feeding two copies of that signal into a NOR (or NAND) gate.

Finite state machine design (13:49)

The FSM question models a cable-car-style vehicle with idle, unload, transit, and emergency states, controlled by inputs that report passengers entering or leaving. The TA works through reading the specification for implicit states, assigning door-output bits to each Moore-type state, and drawing transitions only where they carry meaning, treating unspecified input combinations as self-loops. He stresses that unhandled or nonsensical inputs still need an edge, and that most points are lost through small mistakes like a missing reset arrow or inverted output bits. The second part converts the same FSM to Mealy style, where the output bits move from the states onto the edges, requiring a bell output whenever a door opens or closes and a continuous output during the emergency self-loop.

ISA vs. microarchitecture, and Verilog tracing (25:39)

A short true/false-style question lists processor features (branch predictor design, register bit positions in an instruction encoding, ALU count, cache replacement policy, register file port count) and asks whether each belongs to the ISA or the microarchitecture. The rule applied throughout is that anything a programmer needs to know or can control is ISA, and anything about how the hardware is built underneath is microarchitecture. The Verilog question then asks what a small always-block module computes, tracing a register that increments and indexes into an 8-bit hex input to accumulate an output value across clock cycles, and a second sub-question tests reading Verilog syntax for wire versus reg, bit-width literals, and reduction operators.

Memory technology and performance evaluation (55:11)

A long true/false set covers memory fundamentals: register files consume less energy than main memory, longer word/bit lines increase access time, activating a DRAM cell temporarily destroys its stored charge until the sense amplifiers restore it, DRAM is cheaper per bit than SRAM due to density, row conflicts cost more time than row hits, PCM is non-volatile, and multi-level page tables mean the full page table isn't necessarily resident in physical memory. The performance evaluation question then has students compute IPC for single-threaded runs and for two-application "mixes" sharing a core, and combine them into a weighted speedup metric, with a recurring warning against incorrectly summing numerators and denominators separately instead of dividing each application's fraction first.

Tomasulo's algorithm and out-of-order execution (1:36:35)

Given a snapshot of reservation stations and a register alias table for an adder and a multiplier with separate reservation-station sizes, the task is to reconstruct five in-flight instructions as a data-flow graph and then order them consistently with program order. The method shown is to find the reservation-station entry whose operands are both already-valid register values (no dependency tag), since that must be the oldest instruction, then follow the tags forward through the register alias table to link each dependent instruction to its sources and destination register.

GPUs, SIMD utilization, and data prefetching (2:03:04)

For a GPU kernel with 1,024 loop iterations mapped to one thread each, the question first computes the number of warps (1,024 threads divided by a warp size of 32). It then derives SIMD utilization algebraically for a conditional branch taken by a fixed subset of threads per warp, solving for the number of instructions inside the branch that would produce a target utilization ratio, and repeats the calculation when the branch condition also depends on thread index bounds that make some warps fully diverge and others fully converge. The prefetching question analyzes a fixed stride-based access pattern and computes coverage and bandwidth overhead for a stride prefetcher (which issues nothing without a repeated stride) and for "prefetch next N lines" prefetchers with different values of N, tracking which prefetched lines are actually reused before being evicted.

Cache reverse engineering and pipelining (2:41:13)

The final two questions close out the exam review. The cache question asks which three follow-up addresses would reveal a cache's set associativity given a FIFO replacement policy, eight blocks, and a known access history; the approach is to simulate the cache state under 1-way, 2-way, 4-way, and 8-way associativity and find addresses that produce a distinct hit/miss pattern for each case. The pipelining question analyzes a five-stage in-order pipeline diagram to identify ALU latency for add versus multiply instructions, detect where data forwarding already exists, explain why the decode stage sometimes takes two cycles, and compute the speedup from adding an extra register-file read port or an earlier forwarding path from the memory stage.

Before you watch

• Watch this after finishing the course's regular lectures on Boolean logic, FSMs, ISA design, Verilog, memory systems, out-of-order execution, GPUs, prefetching, caches, and pipelining, since this session assumes that material rather than teaching it from scratch.
• Have a copy of, or be ready to pause on, each exam question shown on screen, since the walkthroughs skip reading the full problem text aloud.
• Review Tomasulo's algorithm and register renaming beforehand, since the out-of-order question is one of the densest parts of the session.

Check your understanding

1. Why must B or B-not and A or A-not pairs equal 1 when simplifying a sum-of-products expression, and how does that justify merging terms that differ in one variable?
2. In the Tomasulo reconstruction, how do you identify which of the five instructions was executed before the reservation-station snapshot was taken?
3. Why is it mathematically wrong to compute weighted speedup by summing all the shared IPCs and dividing by the sum of all the alone IPCs?
4. For the GPU SIMD question, why does a branch condition that fully diverges some warps and fully converges others require writing separate utilization equations for each group of warps?
5. Why does adding a read port reduce pipeline execution time in the example shown, while adding a write port does not?