Lecture 29: Problem Solving IV

What this lecture covers

This is a problem-solving session (lecture 35 of 37 in the course) where the teaching staff works through the previous year's final exam, question by question, in the original exam order. It is not new material: it is a worked review of everything the course has covered, aimed at showing how to apply the concepts under exam conditions.

By the end you will have seen full solutions to problems on Boolean logic simplification and NOR-only conversion, Verilog module completion, finite state machine minimization and design, the ISA-versus-microarchitecture distinction, CPI and execution-time calculations with Amdahl's law, pipeline hazard scheduling, Tomasulo's algorithm and data-flow graphs, GPU/SIMD utilization, branch predictor accuracy, cache reverse-engineering, runahead execution, and systolic-array convolution. Each solution also models the reasoning process an exam grader expects to see, not just the final answer.

Key ideas

• Karnaugh-map simplification: grouping min-terms by shared literals (for example BC'D') is used to reduce a sum-of-products expression before converting it further.
• NOR-only conversion: to rewrite a formula using only NOR gates, repeatedly simplify, apply De Morgan's law, or double-negate (x = (x')') terms until every operator is a NOR.
• ISA vs. microarchitecture: the ISA manual documents anything a programmer or compiler must know to write correct code (registers, instruction formats, memory model); the microarchitecture manual documents implementation details (pipeline stages, execution unit counts) that do not affect program correctness.
• CPI and execution time: average CPI is the weighted sum of each instruction type's latency by its frequency; execution time equals instruction count times CPI divided by clock frequency, which is the formula used to compare two processor designs.
• Amdahl's law: speedup from optimizing a fraction P of execution at factor S is 1 / ((1 - P) + P / S), used to pick between two competing hardware optimizations.
• Tomasulo's algorithm: reservation stations track dependent operands by tag, and a register alias table records which reservation station will eventually produce each register's value, which lets you reconstruct a program's data-flow graph from a snapshot.
• SIMD utilization: a warp wastes lanes whenever some of its threads take a branch and others do not; utilization is the ratio of instructions actually executed to the instructions that would run if every thread in every warp took the same path.
• Cache reverse engineering: by trying candidate block sizes, associativities, replacement policies, and total sizes against observed hit rates, you can eliminate configurations one at a time until only one is consistent with all the sequences.

Walkthrough

Boolean logic circuits (0:00)

The session opens with simplifying a sum of min-terms into a reduced Boolean expression by grouping common literals, similar to a Karnaugh map. It then shows how to rewrite that expression using only NOR gates, using a fixed toolkit of moves: simplify first, then apply De Morgan's law, double negation, or AND/OR a term with itself, repeating until every remaining operator is a NOR.

Verilog module completion (24:10)

Given a partially blanked Verilog module with two always blocks, the instructor works out which signals must be declared as registers (because they are written inside a clocked always block) versus outputs, why case-statement branches use default instead of an illegal binary literal, and why signals assigned inside a clock-triggered block must use non-blocking (<=) rather than blocking (=) assignment. A second part traces a small state machine's output over 16 clock cycles by hand, showing how two parallel always blocks each read the previous cycle's values.

Finite state machines (51:53)

The first exercise minimizes a Mealy machine by removing unreachable states and confirms the remaining states cannot be merged because they behave differently on the same input. The second exercise designs a Moore machine that outputs 1 exactly when the bit-serial input read so far is divisible by eight, built around detecting three trailing zero bits, with explicit reset behavior for the all-zero starting case.

ISA vs. microarchitecture and performance evaluation (1:04:40)

For a list of processor properties (number of addressable memory locations, instructions fetched per cycle, number of general-purpose registers, endianness, cache coherence protocol, pipeline stage count, and more), each item is classified as belonging in the ISA manual only if a programmer needs it to write correct code, or in the microarchitecture manual if it only affects implementation or performance. The lecture then computes CPI for two processor designs from an instruction-mix breakdown, applies the execution-time formula to show which design is faster and by how much, and uses Amdahl's law to compare two candidate optimizations for the same workload.

Pipelining and Tomasulo's algorithm (1:34:50)

For a five-stage MIPS-like pipeline, the lecture schedules a loop body on a machine without hardware interlocking (inserting NOPs by hand to respect data dependencies) and on a machine with hardware interlocking and forwarding, then computes total cycle counts for 100 loop iterations on each. The Tomasulo section works backward from a snapshot of reservation stations and a register alias table to reconstruct the data-flow graph of five in-flight instructions, then writes the equivalent instruction sequence in program order.

GPU/SIMD, branch prediction, caches, and systolic arrays (2:20:21)

The remaining questions cover: computing SIMD utilization for warps executing a conditional inner loop, where utilization drops whenever some threads in a warp diverge from others; comparing misprediction rates across an always-taken predictor, a shared global two-bit saturating counter, and a per-branch two-bit counter, for a loop with five branches; reverse-engineering an unknown cache's block size, associativity, replacement policy, and total size purely from observed hit rates on three access sequences; a short question on how a runahead-execution bug can make a processor faster or slower without ever breaking correctness, since nothing in runahead mode is committed; and mapping four parallel convolutions onto a 4x4 systolic array by tracking how each input and weight value propagates between processing elements over successive cycles.

Before you watch

• This session assumes you have already sat through the course's lectures on Boolean logic, Verilog, finite state machines, ISA design, performance evaluation, pipelining, Tomasulo's algorithm, GPU/SIMD execution, branch prediction, caches, runahead execution, and systolic arrays.
• Have the referenced final exam questions in front of you, since the video works through them without restating every detail of the problem text.
• A basic grasp of Karnaugh maps and De Morgan's law will make the Boolean logic segment easier to follow.

Check your understanding

1. Why must a signal that is assigned inside a clocked always block be declared as a register rather than a wire or plain output?
2. What distinguishes information that belongs in an ISA manual from information that belongs in a microarchitecture manual?
3. Why does hardware interlocking with forwarding reduce the number of pipeline cycles needed per loop iteration compared to a machine without interlocking?
4. In a warp executing a diverging branch, what determines whether SIMD utilization for that warp is 100%, partial, or wasted entirely?
5. Why can a bug that corrupts every other instruction in runahead mode change a processor's speed but never cause an incorrect final result?