Lecture 26: Problem Solving I

What this lecture covers

This is a teaching-assistant problem-solving session for Digital Design and Computer Architecture, working through past exam questions rather than introducing new material. Each question is read aloud, then solved on a whiteboard while students ask clarifying questions, so the session functions as a guided answer key across nine separate topics: finite state machines, MIPS assembly, pipeline hazards, Tomasulo's algorithm (twice, once forward and once as reverse engineering), out-of-order execution reverse engineering, Boolean logic, and dataflow computing.

After watching, you should be able to reproduce the reasoning steps for each question type: encoding an FSM three different ways and comparing their logic cost, hand-tracing MIPS assembly for a calling convention, inserting nops or reordering code for a non-interlocked pipeline, filling in Tomasulo reservation stations and register alias tables, and reconstructing an unknown instruction sequence from before/after register snapshots.

Key ideas

• FSM encoding trade-offs: one-hot encoding minimizes next-state logic, binary encoding minimizes flip-flops, and output encoding is chosen to minimize the output logic directly.
• Reset line versus initial state: a reset line is what actually guarantees an FSM starts in its defined initial state, even when a textbook treats it as optional.
• Register-saving convention: a callee saves registers it will overwrite (such as R16-R18) onto the stack at function entry and restores them before returning, protecting the caller's values.
• Reservation station tags: a tag identifies the reservation station entry that will produce a needed operand; a valid bit of 0 means the value is still pending on that tag.
• Tag comparator sizing: the number of comparators needed equals the number of source tags per entry multiplied by the number of functional units, since any unit's result must be checked against every waiting tag each cycle.
• Reverse engineering an instruction sequence: comparing register-file values before and after execution, combined with reservation-station dependency tags, lets you infer both instruction order and operands even when some fields are hidden.
• Product-of-sums versus sum-of-products: choosing the form with fewer terms (fewer zeros or fewer ones in the truth table) makes the resulting Boolean equation shorter to derive.
• Dataflow execution: a node fires only once all of its input tokens are available, and constant or looped values are modeled as repeating token streams feeding back into the graph.

Walkthrough

Finite state machines: encoding and the missing reset line (0:00)

The session opens with an FSM question that gives states, an output, and two inputs, then asks what critical component is missing. The instructors identify the missing reset line and discuss when a book treats it as optional versus a "critical component" in a homework answer. They then build a truth table for the FSM and derive Boolean equations for the next-state and output logic under three encodings: one-hot, binary, and a custom output encoding designed so each output bit depends on a single state bit. Comparing the number of logic terms and flip-flops across all three shows output encoding using the fewest total gates for this particular FSM.

MIPS assembly for Fibonacci and a byte-copy loop (32:26)

The next question asks for MIPS assembly implementing an iterative Fibonacci calculation, following register-saving conventions: temporary registers used by the function are pushed to the stack on entry and restored before returning, since the calling function may already be using them. The instructors then translate the x86 rep movsb instruction, which repeatedly copies a byte from a source to a destination array, into an equivalent MIPS loop, and compute its code size (28 bytes versus 2 bytes for the single x86 instruction) and its dynamic instruction count as a function of the copy-count register.

Pipelining without hardware interlocking (57:56)

Given two hypothetical five-stage pipelines, one without hardware interlocking (the compiler must reorder code and insert nops) and one with hardware-based forwarding, the instructors manually schedule a short loop for the non-interlocked machine. They draw out fetch/decode/execute/memory/write-back stages cycle by cycle, insert independent instructions between dependent ones where possible, and add explicit nop bubbles where no reordering can hide the dependency. They then compare static code size and total cycle count between the two machines.

Tomasulo's algorithm: sizing reservation stations (1:19:01)

This question is less about tracing execution and more about counting hardware resources. Given eight functional units, 32 registers, and 16 reservation-station entries per unit, the instructors work out how many tag comparators are needed per entry (source-operand count times functional-unit count), how many comparators the register alias table itself needs, the minimum tag width to address every reservation-station entry, and the total bits of tag storage across the whole machine.

Reverse-engineering register state from Tomasulo execution (1:30:05)

Two related exam questions give a register-file snapshot before and after four or five instructions execute out of order, along with partial reservation-station information, and ask students to reconstruct the instruction sequence itself. The method shown is to look for which register values changed, trace back which combination of known values could produce each new value, and use the dependency chain revealed by reservation-station tags to order the instructions. The same walkthrough continues into filling out reservation stations and the register alias table cycle by cycle for a fixed clock cycle snapshot.

Boolean logic and dataflow (2:06:51)

A four-input truth table problem asks for one function written in product-of-sums form and another in sum-of-products form, followed by a circuit built only from XOR and AND gates. The instructors show how choosing the representation with fewer terms simplifies the derivation, and prove the XOR-based circuit is equivalent using De Morgan's law.

Dataflow Fibonacci and a second pipelining exercise (2:17:18)

The final major question asks for a dataflow-graph implementation of the Fibonacci function using only addition, comparison, copy, and branch nodes. The instructors build the graph incrementally, first handling the base case of n=0, then n=1, then generalizing to a loop that feeds results back into the addition node, and trace token flow through the graph for n=2 to confirm it produces the correct output. The session closes with a second pipelining scheduling question comparing scoreboarding with and without data forwarding, and with one versus five functional units.

Before you watch

• Review the course's earlier lectures on finite state machines and state encoding, since the first question assumes familiarity with one-hot, binary, and output encoding.
• Be comfortable with basic MIPS instructions and the register-saving calling convention covered in the ISA lectures.
• Review Tomasulo's algorithm, reservation stations, and the register alias table from the out-of-order execution lectures before the two Tomasulo questions.
• Have the dataflow computing lecture fresh in mind, since the final question assumes you already know how dataflow nodes and token firing work.

Check your understanding

1. Why does adding a reset line change a state diagram from merely having an "assumed" initial state to actually guaranteeing one?
2. For the same FSM, why can output encoding sometimes need fewer total logic gates than binary encoding despite using more bits than the theoretical minimum?
3. Why must a MIPS function save registers it uses to the stack even if the calling function is not currently using those specific registers for anything important?
4. In Tomasulo's algorithm, why does the number of tag comparators depend on the number of functional units rather than just the number of reservation-station entries?
5. In the dataflow Fibonacci graph, why can a node only fire once all of its input tokens have arrived, and what would go wrong if it fired early?