Lecture 30: Problem Solving V

What this lecture covers

This is a problem-solving session where teaching assistants walk through exam questions from a previous Digital Design and Computer Architecture final, rather than presenting new material. Each TA takes a topic and solves it on screen the way a student would in an exam: reading the question carefully, sketching a mental model, then working out the answer step by step.

The session assumes you already know the course's core topics, since it revisits nearly all of them: boolean logic minimization, Verilog syntax, finite state machines, the ISA/microarchitecture distinction, CPI and performance formulas, pipelining with data forwarding, Tomasulo's algorithm, GPU SIMD utilization, cache reverse-engineering, branch prediction, and VLIW instruction scheduling. After watching, you should be able to apply the same worked techniques to similar exam-style problems, and pick up several general exam strategies the TAs repeat throughout.

Key ideas

• NAND-only rewriting: boolean circuit minimization questions are solved by applying double negation (not-not) to expose NAND structure in a sum-of-products expression.
• Sequential vs combinational Verilog: a case statement that does not assign every output in every branch implies the circuit must remember a previous value, which synthesizes as a latch, making the circuit sequential.
• Hardware vs software interlocking: hardware interlocking means the processor detects data dependencies and stalls automatically; software interlocking means the compiler inserts explicit no-ops instead.
• ISA vs microarchitecture: anything a programmer can see or control (register widths, addressable memory size, system call mechanism) belongs to the ISA; internal implementation details (reorder buffer size, replacement policy, fetch width) belong to the microarchitecture.
• CPI and execution time: CPI is the weighted sum of each instruction type's cycle count by its frequency, and execution time equals instruction count times CPI divided by clock frequency; Amdahl's law is used to compare partial speedups.
• Reverse-engineering Tomasulo traces: cache hit/miss latency, reservation station size, and number of ALUs can all be inferred from how many instructions overlap in the execute stage of a given execution diagram.
• SIMD utilization: computed as executed operations divided by the maximum possible operations (warp size times instruction count), and it depends only on which array values drive branch divergence.
• VLIW scheduling: the compiler, not the hardware, is responsible for packing independent instructions into slots and checking dependencies, which is why VLIW reduces hardware complexity but increases compiler complexity.

Walkthrough

Boolean minimization and Verilog code analysis (0:00)

The session opens with a boolean algebra simplification exercise, rewriting a sum-of-products expression into a single NAND gate by applying double negation and factoring out common terms. The TA then works through several short Verilog snippets, judging whether each one is combinational or sequential, whether it correctly implements a divide-by-three counter, what values its registers hold after specific input changes given non-blocking assignment semantics, and where a design has bugs such as missing begin/end blocks, multiple drivers on the same wire, or an assign statement misused on a register.

Finite state machines (27:01)

The TA draws a Moore machine that detects the bit pattern 011 in a streaming input, explaining how each state tracks how much of the pattern has been seen so far and why the output depends only on the current state, not the input, in a Moore design. A second part classifies a given machine as Mealy (since its output depends on both state and input), removes an unreachable state, merges two states with identical transition behavior into one, and identifies the simplified machine's purpose as an edge detector that fires on 0-to-1 and 1-to-0 transitions.

ISA vs. microarchitecture and performance evaluation (37:37)

Given a scenario where a student can only afford one of two manuals, an ISA reference or a microarchitecture reference, the TA sorts a long list of processor details (branch misprediction penalty, TLB flush mechanism, reorder buffer size, SIMD support, fetch width, addressable memory size) into whichever manual would actually document them, reinforcing the boundary between what a programmer needs to know and what only the hardware designer controls. The performance section then computes CPI for two processor designs from given instruction-type latencies and mix percentages, derives execution time, and uses Amdahl's law to decide whether adding a faster branch unit or a faster memory device gives a better speedup.

Pipelining and data forwarding (1:01:38)

Working from an execution timeline with visible stalls, the TA identifies which forwarding paths (execute-to-execute, and forwarding of condition registers for a jump) must exist to produce exactly those stall cycles, and concludes the machine uses hardware interlocking because there are no no-ops in the code and it stalls only when necessary. The same code is then rewritten with explicit no-ops to simulate software interlocking, and the resulting cycle table is used to compute the total cycle count for a 98-iteration loop and the dynamic instruction number at a given point in execution.

Tomasulo's algorithm (1:27:01)

This section is framed explicitly as an exam-technique demonstration: read the question fully before solving, and build a mental diagram of the processor (in-order fetch, out-of-order dispatch, in-order retirement, one ALU reservation station, one memory reservation station) before touching the numbers. From a table of seven dynamic instructions' pipeline stages, the TA infers the cache hit latency (one cycle) and miss latency (eight cycles) by comparing two accesses to the same address, deduces that the reservation stations likely hold two entries each from overlapping execute stages, and reconstructs the original squashed-and-corrected instruction stream after a branch misprediction, including where the branch's true target must be.

GPUs, SIMD, and caches (2:10:41)

For a GPU kernel with 64-thread warps, the TA computes the total warp count from the iteration count, then uses a given SIMD utilization fraction to work out which array values drive branch divergence, and separately derives the array conditions needed for 100% and for minimum possible utilization. The cache section reverse-engineers a cache's block size, associativity, and replacement policy (LRU vs FIFO) purely from hit-rate statistics on two back-to-back access sequences, then designs a three-address probe sequence to distinguish a 4KB cache from an 8KB cache.

Branch prediction and VLIW (2:49:01)

Using a formula relating total cycles to instruction count, pipeline depth, and misprediction penalty, the TA first derives that a mystery predictor must produce exactly six mispredictions on a given loop, then tests static (always-taken, always-not-taken), last-time, backward-taken-forward-not-taken, and two-bit counter predictors against that target to find which configurations fit. The closing VLIW segment schedules twelve short instructions (loads, integer adds, floating-point adds, a branch) into a four-slot long instruction word by tracking each operation's data dependencies and pipelined latency, then computes the total cycle count and the resulting slot utilization percentage.

Before you watch

• Review boolean algebra simplification, Verilog syntax (blocking vs non-blocking assignments, always sensitivity lists), and the CPI/execution-time formulas from earlier lectures in this course.
• Be comfortable with Tomasulo's algorithm, cache associativity and replacement policies, GPU SIMD execution, branch prediction schemes, and VLIW scheduling, since each section assumes you already know the underlying concept and only reviews how to apply it under exam conditions.
• Have Amdahl's law ready, since it is used directly without re-derivation.

Check your understanding

1. Why does an incompletely-specified case statement in a Verilog always @* block synthesize as a latch instead of pure combinational logic?
2. Given instruction-type latencies and a mix breakdown, how do you compute CPI, and how does that differ from computing execution time?
3. In a Tomasulo execution diagram, what clue tells you that two instructions could be sharing a reservation station or executing on separate ALUs?
4. How is SIMD utilization defined, and why do only some arrays in a kernel affect it?
5. What is the key difference between hardware and software interlocking, and how does the choice change what appears in the assembly code?