Seyed Masoud Hosseini · Overview · Study log · Weekly summaries · Ideas · Search · Transcript · RSS feed

Digital Design & Computer Architecture · Lecture 32 of 37 · 2:50:40

Lecture 26: Problem Solving I

Digital Design & Comp. Arch: L26: Problem Solving I (Spring 2025) on YouTube

Study guide

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?

Vocabulary

state encoding (noun)
The choice of bit patterns used to represent each state of a finite state machine.
The instructors compare one-hot, binary, and output state encoding.
reset line (noun)
A signal that forces a circuit to start in a known, defined state.
The FSM was missing an explicit reset line.
output encoding (noun)
A state encoding where the state bits directly match the desired output bits.
Output encoding minimizes the separate output logic needed.
callee (noun)
The function being called, as opposed to the function that made the call.
The callee must save any registers it plans to overwrite.
calling convention (noun)
The agreed rules for how arguments, return values, and registers are handled across a function call.
Register-saving follows the standard calling convention.
dynamic instruction count (noun)
The total number of instructions actually executed while a program runs, including repeats from loops.
The loop's dynamic instruction count depends on the copy-count register.
hardware interlocking (noun)
Circuitry that automatically detects and resolves dependencies between instructions.
Without hardware interlocking, the compiler must insert nops by hand.
nop (noun)
An instruction that does nothing, used to create a delay in a pipeline.
A nop is inserted to prevent a data hazard.
reservation station (noun)
A hardware buffer that holds an instruction until its operands are ready.
Each functional unit has its own set of reservation stations.
register alias table (noun)
A table that maps each architectural register to the reservation station tag that will supply its next value.
The register alias table tracks pending register values.
tag comparator (noun)
A circuit that checks whether a broadcast tag matches a waiting instruction's expected tag.
Each entry needs enough tag comparators for every functional unit.
product-of-sums (noun)
A way of writing a Boolean expression as several OR terms multiplied together with AND.
Product-of-sums form can be shorter when there are few zero outputs.
sum-of-products (noun)
A way of writing a Boolean expression as several AND terms added together with OR.
Sum-of-products form works best when there are few one outputs.
De Morgan's law (noun)
A rule for rewriting NOT of AND/OR expressions using the opposite operator.
De Morgan's law proves the two circuits are equivalent.
token (noun)
A piece of data flowing through a dataflow graph into a node.
A node fires only once all of its input tokens have arrived.
base case (noun)
The simplest case of a recursive or repeated computation that stops further recursion.
The dataflow graph first handles the base case of n=0.
flip-flop (noun)
A small circuit that stores one bit of a state machine's current state.
Binary encoding minimizes the number of flip-flops needed.
clarifying question (phrase)
A question asked to make an unclear point more understandable.
Students ask clarifying questions while the answer is worked out.
guided answer key (phrase)
A worked set of solutions explained step by step, not just given as final answers.
The session works as a guided answer key across nine topics.
push (verb)
To place a value onto a stack.
The callee pushes registers onto the stack before overwriting them.
code size (noun)
The amount of memory a program's instructions take up.
The MIPS loop's code size is much larger than the single x86 instruction.
bubble (noun)
An empty cycle inserted into a pipeline to wait for a dependency.
A nop bubble is added where reordering cannot hide the dependency.
address (verb)
To select or refer to a specific memory or storage location.
The tag width must be enough to address every reservation-station entry.
equivalent (adjective)
Having the same effect or result, even if built differently.
The XOR-based circuit is proven equivalent to the original.
generalize (verb)
To extend a specific solution into a broader, reusable pattern.
The graph generalizes from the base cases into a full loop.

Chapters

From the YouTube description

Digital Design and Computer Architecture, ETH Zürich, Spring 2025 (https://safari.ethz.ch/ddca/spring2025/)

Lecture 26: Problem Solving I
Lecturer: Prof. Onur Mutlu
Date: 18 July 2025

Questions:
00:00:00 - Finite State Machines (FSM) II (HW2, Q5, Spring 2023)
00:32:26 - The MIPS ISA (HW3, Q2, Spring 2023)
00:57:56 - Pipelining (HW4, Q3, Spring 2023)
01:19:01 - Tomasulo’s Algorithm (HW4, Q5, Spring 2023)
01:30:05 - Tomasulo’s Algorithm (Rev. Engineering) (HW4, Q6, Spring 2023)
01:46:56 - Out-of-Order Execution - Rev. Engineering (HW4, Q8, Spring 2023)
02:06:51 - Boolean Logic and Truth Tables (HW1, Q6, Spring 2021)
02:17:18 - Dataflow I (HW3, Q3, Spring 2022)
02:38:56 - Pipelining I (HW4, Q1, Spring 2022)

Lecture 26 Slides (pptx): https://safari.ethz.ch/ddca/spring2025/lib/exe/fetch.php?media=onur-ddca-2025-problem-solving-i-beforelecture.pptx
Lecture 26 Slides (pdf): https://safari.ethz.ch/ddca/spring2025/lib/exe/fetch.php?media=onur-ddca-2025-problem-solving-i-beforelecture.pdf

Recommended Reading:
====================
A Modern Primer on Processing in Memory
https://arxiv.org/pdf/2012.03112.pdf

Memory-Centric Computing: Solving Computing's Memory Problem
https://www.arxiv.org/pdf/2505.00458

Memory-Centric Computing: Recent Advances in Processing-in-DRAM
https://arxiv.org/pdf/2412.19275

Intelligent Architectures for Intelligent Computing Systems
https://people.inf.ethz.ch/omutlu/pub/intelligent-architectures-for-intelligent-computingsystems-invited_paper_DATE21.pdf

RowHammer: A Retrospective
https://people.inf.ethz.ch/omutlu/pub/RowHammer-Retrospective_ieee_tcad19.pdf

Fundamentally Understanding and Solving RowHammer
https://arxiv.org/pdf/2211.07613.pdf

Accelerating Genome Analysis via Algorithm-Architecture Co-Design
https://people.inf.ethz.ch/omutlu/pub/AcceleratingGenomeAnalysis_dac23.pdf

From Molecules to Genomic Variations: Accelerating Genome Analysis via Intelligent Algorithms and Architectures
https://people.inf.ethz.ch/omutlu/pub/IntelligentGenomeAnalysis_csbj22.pdf

RECOMMENDED LECTURE VIDEOS & PLAYLISTS:
========================================
Digital Design and Computer Architecture Spring 2025 Livestream Lectures Playlist:
https://www.youtube.com/watch?v=ubhxKNlOlRg&list=PL5Q2soXY2Zi9Eo29LMgKVcaydS7V1zZW3&index=3

Fundamentals of Computer Architecture Fall 2025 Livestream Lectures Playlist:
https://www.youtube.com/watch?v=uKgMFj1eQQc&list=PL5Q2soXY2Zi_ZMtqz1r-GHm-zzuE1QfIg&index=2

Seminar in Computer Architecture Spring 2025 Livestream Lectures Playlist:
https://www.youtube.com/watch?v=rqeKNZrLzng&list=PL5Q2soXY2Zi-oIW66TLOjtiqQxlDwNHng&index=2

Computer Architecture Fall 2024 Lectures Playlist:
https://www.youtube.com/watch?v=ziMRjDlLEwo&list=PL5Q2soXY2Zi-LfDdGgWyLcTSqzm6a26wD&index=2

Interview with Professor Onur Mutlu:
https://www.youtube.com/watch?v=8ffSEKZhmvo&list=PL5Q2soXY2Zi8VrmOTz44l2WupethSdh-M&index=9

TCuARCH meets Prof. Onur Mutlu
https://www.youtube.com/watch?v=6Hpn4SAX0dI

Arch. Mentoring Workshop @ISCA'21 - Doing Impactful Research
https://www.youtube.com/watch?v=83tlorht7Mc

The Story of RowHammer Lecture:
https://www.youtube.com/watch?v=sgd7PHQQ1AI&list=PL5Q2soXY2Zi8D_5MGV6EnXEJHnV2YFBJl&index=39

Accelerating Genome Analysis Lecture:
https://www.youtube.com/watch?v=r7sn41lH-4A&list=PL5Q2soXY2Zi8D_5MGV6EnXEJHnV2YFBJl&index=41

Memory-Centric Computing Systems Tutorial at IEDM 2021:
https://www.youtube.com/watch?v=H3sEaINPBOE&list=PL5Q2soXY2Zi8D_5MGV6EnXEJHnV2YFBJl&index=35

Intelligent Architectures for Intelligent Machines Lecture:
https://www.youtube.com/watch?v=GTieZPY4Wmc&list=PL5Q2soXY2Zi8D_5MGV6EnXEJHnV2YFBJl&index=38

Featured Lectures:
https://www.youtube.com/watch?v=jVYCchBGNVc&list=PL5Q2soXY2Zi8VrmOTz44l2WupethSdh-M&index=1

← Lecture 25: Prefetching II and Parting Thoughts · Lecture 27: Problem Solving II →