Lecture 27: Problem Solving II

What this lecture covers

This is a second teaching-assistant problem-solving session for Digital Design and Computer Architecture, run by several different presenters back to back over more than three hours. Rather than teaching new concepts, it works through a long list of past exam questions: ISA versus microarchitecture classification, reverse-engineering a pipeline's forwarding paths from a timing diagram, true/false questions on memory technology, FSM simplification and design, vector processing with banked memory, Boolean logic circuits built from NAND gates, CPI and speedup calculations, systolic arrays, VLIW instruction scheduling, cache reverse engineering, prefetcher identification, and a closing Verilog debugging question.

Because each segment is a self-contained exam question with its own setup and answer, you can watch the whole session in order to rehearse a broad slice of the course's exam-style problems, or jump to a single topic when reviewing for that part of the material. After watching, you should be able to reproduce the reasoning strategy for each question type, not just the final numeric answers.

Key ideas

• ISA versus microarchitecture: anything defined by the instruction encoding or programmer-visible behavior is ISA; anything about how it is implemented in hardware (algorithms, cache sizes, bus widths) is microarchitecture.
• Reverse-engineering forwarding paths: given only a pipeline timing diagram, you can infer forwarding paths by finding which register is read before its producing instruction reaches write-back, and reading off which stage the value came from.
• Hardware versus software interlocking: a timing diagram with no stall bubbles around data-dependent instructions indicates the hardware itself detects and resolves dependencies.
• DRAM versus SRAM trade-offs: DRAM is used as main memory because SRAM's larger transistor count costs more static power, while phase-change memory is non-volatile but has asymmetric read/write latency.
• Bank parallelism and stride: the minimum number of memory banks needed to avoid stalls depends on a request's round-trip latency and its access stride, since consecutive addresses map to different banks.
• VLIW static scheduling: a compiler must place independent operations into the same instruction word up front, since the hardware itself does not reorder or stall for dependencies.
• Cache reverse engineering: choosing test addresses that will conflict differently under direct-mapped, set-associative, and fully associative layouts lets you distinguish a cache's configuration purely from its hit/miss pattern.
• Prefetcher accuracy versus coverage: comparing how many prefetch requests go unused (accuracy) versus how many real accesses are predicted (coverage) can identify which prefetch policy a machine uses without simulating every request.

Walkthrough

ISA versus microarchitecture, and reverse-engineering a pipeline (3:19)

The session opens with a rapid classification exercise: fifteen properties (immediate field width, multiplication algorithm, cache size, memory bus width, and so on) are sorted into "ISA" or "microarchitecture." The presenter then moves to a longer question that gives only a timeline of pipeline stages for an unnamed processor and asks students to reverse-engineer its data forwarding paths. By marking which registers are read before their producing instruction's write-back stage, the presenter identifies specific forwarding paths (for example, execute-to-execute and memory-to-execute), concludes the machine uses hardware interlocking because no stall bubbles appear, and then uses a snapshot of a register value mid-loop to calculate an unknown clock cycle and instruction count.

Memory technology true/false (39:03)

A run of true/false statements covers DRAM, SRAM, phase-change memory, virtual memory, and TLBs: for example, why DRAM rather than SRAM is used as main memory, why phase-change memory reads are faster than writes, why a bit line connects cells down a column rather than across a row, and why virtual memory simplifies software design rather than reducing access latency. Each answer is justified with a one- or two-sentence explanation rather than just stated.

FSM simplification and a Mealy-to-Moore design problem (45:14)

Given a four-state FSM, the presenter shows that three of the four states behave identically (invert the input to produce the output and always transition among themselves), so the entire machine collapses to two states. The second part asks for a Moore FSM that outputs 1 only after observing a "0011" pattern (two repeated zeros followed by two repeated ones), built incrementally by defining one state per partial pattern matched so far, including a state representing the reset condition where the input is assumed to have been high for a long time.

Vector processing: bank count, stride, and VLIW-style code (1:00:28)

Working from an ISA description with vector load/store instructions, per-bank row-hit and row-miss latencies, and address interleaving across banks, the presenter first works out the minimum number of banks needed to avoid stalls for even and odd address strides. The question then asks for hand-written vector assembly implementing a masked conditional loop (copying one array or computing a multiply-add depending on a per-element test), using instructions such as vld, vst, vcompare, and ldm to build the mask register, and finally computes the total cycle count including DRAM row-miss penalties for the resulting code.

Boolean logic, CPI, and systolic arrays (1:50:54)

A new presenter opens with a four-input circuit whose two outputs are 1 for Fibonacci-numbered inputs and for inputs greater than three; after deriving and simplifying the sum-of-products expression, the second output is rebuilt using only two-input NAND gates. A CPI question follows, computing cycles-per-instruction and execution time for two processor designs with different instruction mixes and latencies, then choosing between an ALU or load-store-unit optimization based on which lowers CPI more. The segment ends with a systolic array question tracing how a 2x2 processing-element grid computes a matrix multiply cycle by cycle, then scaling that timing to a 4x4 matrix.

VLIW scheduling and reverse-engineering a cache's associativity (2:29:41)

A VLIW question asks for hand-scheduled instructions across seven functional units (three load, one store, one add, one multiply, one branch) for a small loop, filling in nop slots wherever a dependency blocks parallel issue, then computing the ratio of useful operations to VLIW instruction words and total execution time as a function of the loop count. The following cache question asks how a malicious program could issue only two extra memory accesses to reverse-engineer whether an L1 cache is direct-mapped, two-way set associative, or fully associative, by choosing addresses that conflict differently under each configuration and observing the resulting hit/miss pattern; a follow-up shows why the same trick fails under an MRU (rather than LRU) replacement policy.

Prefetcher identification and a Verilog debugging exercise (2:51:19)

Given coverage and accuracy statistics for two machines running a stride-friendly and a non-stride access pattern, the presenter shows a shortcut for identifying which of three candidate prefetchers (stride, next-block, or next-plus-4-block) each machine uses, based on which prefetcher would require waiting for a second access before it can act. In the closing segment, a remote presenter walks through a Verilog module that outputs Fibonacci numbers based on an internal cycle counter, then reviews a second, AI-generated module simulating character movement on a grid, identifying a logic bug where the character keeps moving even when no direction input is set.

Before you watch

• This session assumes you have already seen the course's lectures on FSMs, MIPS/ISA design, pipelining and hazards, memory technology (DRAM, SRAM, PCM), caches, vector processing, VLIW, and Verilog, since each segment reviews exam questions on those topics without re-teaching them.
• Watching "Lecture 26: Problem Solving I" first is useful background, since it works through related FSM, pipelining, and Tomasulo's algorithm questions using the same problem-solving format.

Check your understanding

1. What distinguishes a property that belongs to the ISA from one that belongs to the microarchitecture, and why does cache size fall into the latter category?
2. How can you tell from a pipeline timing diagram alone whether a machine uses hardware or software interlocking?
3. Why does an odd address stride require fewer memory banks to avoid stalls than an even stride, given a fixed row-miss latency?
4. Why does the reverse-engineering trick for identifying cache associativity fail once the replacement policy is changed from LRU to MRU?
5. Why can comparing prefetcher accuracy alone, without simulating every access, be enough to distinguish a stride prefetcher from a next-block prefetcher?