Cycle-by-Cycle Trace: Running a Real Program on Our CPU

This is Lesson 2, Part 4 — the capstone of this mini-course. Part 2 built the single-cycle datapath and Part 3 derived the control unit that drives it; neither one meant anything until a real instruction flowed through it. Here we run a real seven-instruction program on that exact CPU, one clock cycle at a time, tracing every wire that matters.

How to Read These Traces

Before Instruction 1, a quick recap of what we're driving, and the format every trace below will follow.

The datapath from Part 2 has five structural pieces that every instruction passes through, in this order, all within a single clock cycle: instruction fetch (PC addresses instruction memory, a 32-bit word comes out), decode (the fetched word is split into opcode/rs/rt/rd/funct or opcode/rs/rt/immediate fields, and the control unit turns the opcode into control signals), register read (the register file's two combinational read ports supply operand values), execute (the ALU computes, using an operation selected by the ALU-control logic reading ALUOp and, for R-type, funct), and memory/write-back (data memory is optionally read or written, and a result is optionally written back into the register file). None of this is new — it's exactly the structure Part 2 wired up and Part 3 put a control unit on top of. What's new in this post is that we stop reasoning about the datapath in the abstract and instead push seven concrete instructions through it, verifying every number by hand.

Each instruction below gets the same eight-part trace, in the same order, so that by Instruction 7 you can predict every table before reading it:

1. Fetch — the PC value and the 32-bit instruction word, in binary and hex.
2. Decode — the fields pulled out of that word.
3. Control signals — every one of RegDst, ALUSrc, MemToReg, RegWrite, MemRead, MemWrite, Branch, ALUOp, read straight off the main control truth table from Part 3.
4. Register file read — which registers are addressed on the two read ports, and what values come back.
5. ALU — the two inputs, which operation the ALU control logic selects, the numeric result, and the zero flag.
6. Memory stage — read, write, or not used, with address and data where applicable.
7. Write-back — what value lands in which register, or "nothing" if RegWrite = 0.
8. Next PC — sequential PC + 4, or (for BEQ) the branch-target arithmetic, shown explicitly.

One timing detail worth stating up front, because it's easy to trip over: register-file reads are combinational (Lesson 1, Part 3), so whatever a given instruction's cycle reads on the register file is whatever the previous instruction's write committed at the end of its cycle. There is no pipelining here — one instruction completely finishes (including its register write, if any) before the next one's cycle begins — but the register values an instruction reads are still, mechanically, "whatever is sitting in the flip-flops right now," which is exactly the effect of the prior instruction's completed write.

Initial architectural state, before cycle 1 begins:

R1 = 10    R2 = 20    R3 = 0     R4 = 100
R5 = 0     R6 = 0     R7 = 0     R8 = 0
 
Mem[100] = 0
 
PC = 0x00400000

The program, for reference through the rest of this post:

0x00400000: ADD  R3, R1, R2
0x00400004: SW   R3, 0(R4)
0x00400008: LW   R5, 0(R4)
0x0040000C: SUB  R6, R5, R1
0x00400010: BEQ  R6, R2, 1
0x00400014: ADD  R7, R1, R1     ; never fetched — see Instruction 6
0x00400018: OR   R8, R1, R2

Instruction 1: ADD R3, R1, R2

1. Fetch

PC = 0x00400000. This address is presented to instruction memory, which returns the 32-bit word stored there — the ADD encoding, built field-by-field from the R-type layout in the shared spec.

opcode   rs      rt      rd      shamt   funct
000000   00001   00010   00011   00000   100000
(R-type) (R1)    (R2)    (R3)    (0)     (ADD, 0x20)
 
Full word:  00000000 00100010 00011000 00100000
Hex:        0x00221820

Worked out from the shift-and-add form the control unit ultimately implements: opcode<<26 | rs<<21 | rt<<16 | rd<<11 | shamt<<6 | funct = (1<<21) | (2<<16) | (3<<11) | 0x20 = 0x200000 + 0x20000 + 0x1800 + 0x20 = 0x221820. Zero-extended to 32 bits, that's 0x00221820.

2. Decode

opcode = 000000 tells the main decoder this is an R-type instruction, which is the only fact it needs to drive every signal in the next table. funct isn't consulted by the main decoder at all — it's consumed downstream by the ALU-control logic, once ALUOp has already routed the decision there.

3. Control Signals

This is the R-type row of Part 3's control table, verbatim — RegDst=1, ALUSrc=0, MemToReg=0, RegWrite=1, MemRead=0, MemWrite=0, Branch=0, ALUOp=10.

4. Register File Read

ReadAddr1 = rs = R1, ReadAddr2 = rt = R2. Both reads are combinational and happen off the initial architectural state, since this is the first instruction:

ReadData1 = R1 = 10
ReadData2 = R2 = 20

5. ALU

ALUSrc = 0, so the ALU's second operand is ReadData2 directly (not the sign-extended immediate). With ALUOp = 10, the ALU-control logic reads funct = 100000 (ADD) and selects the ADD operation.

Input A = 10
Input B = 20
Operation = ADD  (selected via ALUOp=10 + funct=0x20)
Result = 10 + 20 = 30
Zero flag = (Result == 0) = 0        ; 30 is not zero

The zero flag is computed on every single instruction, R-type included — it's just wired to nothing downstream unless Branch = 1. Here it's simply unused.

6. Memory Stage

MemRead = 0, MemWrite = 0. Data memory is not addressed at all this cycle; the ALU's result flows straight past the memory stage toward the write-back mux.

7. Write-Back

RegDst = 1 selects rd = R3 as the write address. MemToReg = 0 selects the ALU result (not memory data) as the write value. RegWrite = 1, so this commits on the rising edge that ends this cycle:

WriteAddr = R3
WriteData = 30   (the ALU result)
R3 ← 30

8. Next PC

Branch = 0, so the PC-select mux takes the sequential path unconditionally:

Next PC = PC + 4 = 0x00400000 + 4 = 0x00400004

Instruction 2: SW R3, 0(R4)

1. Fetch

PC = 0x00400004. This is an I-type instruction: SW opcode 101011 (0x2B), base register R4 in the rs field, source register R3 in the rt field, and an immediate offset of 0.

opcode   rs      rt      immediate
101011   00100   00011   0000000000000000
(SW)     (R4)    (R3)    (0)
 
Full word:  10101100 10000011 00000000 00000000
Hex:        0xAC830000

Arithmetic check: (0x2B<<26) | (4<<21) | (3<<16) | 0 = 0xAC000000 + 0x800000 + 0x30000 = 0xAC830000.

2. Decode

Note the field-naming shift from Instruction 1: in an I-type store, rt is not a destination — it names the register whose value is written to memory. This is exactly why SW's RegDst and MemToReg are marked X (don't-care) in the control table: no register gets written this cycle at all, so it doesn't matter which mux those two signals would otherwise select.

3. Control Signals

This is the SW row of the shared control table: ALUSrc=1, RegWrite=0, MemWrite=1, ALUOp=00, with RegDst/MemToReg don't-cares.

4. Register File Read

ReadAddr1 = rs = R4, ReadAddr2 = rt = R3. Both reads happen off the register-file state as it stands at the start of this cycle — which already includes Instruction 1's write, because that write committed on the clock edge that ended cycle 1, before cycle 2's combinational reads even begin:

ReadData1 = R4 = 100
ReadData2 = R3 = 30      (the value ADD wrote back last cycle)

5. ALU

ALUSrc = 1, so the second ALU input is the sign-extended 16-bit immediate, not ReadData2. ALUOp = 00 forces ADD unconditionally — the ALU control logic doesn't even look at funct for this ALUOp value (SW has no funct field to look at):

Input A = ReadData1 = 100
Input B = sign_extend(0x0000) = 0
Operation = ADD  (forced by ALUOp=00)
Result = 100 + 0 = 100          ; this is the effective memory address
Zero flag = (Result == 0) = 0   ; unused this cycle, Branch=0

The ALU here is not doing "the instruction's operation" in any semantic sense — it's doing address arithmetic. This is the same ALU, doing the same ADD it always does; only the operand sources changed, via the ALUSrc mux.

6. Memory Stage

MemWrite = 1, MemRead = 0. The ALU's result (100) is the address; ReadData2 (30, R3's value) is the data:

Address = 100
Data written = 30
Mem[100] ← 30

7. Write-Back

RegWrite = 0. Nothing is written to the register file this cycle — the write port's WriteEnable is simply deasserted, and whatever garbage might be floating on WriteAddr/WriteData (recall RegDst/MemToReg are don't-cares) never reaches any flip-flop.

8. Next PC

Branch = 0, sequential path again:

Next PC = PC + 4 = 0x00400004 + 4 = 0x00400008

Instruction 3: LW R5, 0(R4)

1. Fetch

PC = 0x00400008. LW opcode 100011 (0x23), base register R4 in rs, destination register R5 in rt, immediate offset 0.

opcode   rs      rt      immediate
100011   00100   00101   0000000000000000
(LW)     (R4)    (R5)    (0)
 
Full word:  10001100 10000101 00000000 00000000
Hex:        0x8C850000

Arithmetic check: (0x23<<26) | (4<<21) | (5<<16) | 0 = 0x8C000000 + 0x800000 + 0x50000 = 0x8C850000.

2. Decode

For LW, rt flips meaning again — back to a destination, exactly like rd was for the R-type ADD. This is precisely why RegDst = 0 for LW: the write-address mux must select rt, not rd, because LW's encoding has no rd field at all to select.

3. Control Signals

LW row of the shared table: RegDst=0, ALUSrc=1, MemToReg=1, RegWrite=1, MemRead=1, MemWrite=0, Branch=0, ALUOp=00.

4. Register File Read

ReadAddr1 = rs = R4, ReadAddr2 = rt = R5. LW does technically drive a ReadAddr2 (the field is always decoded regardless of instruction type — the datapath is fixed hardware, not conditionally wired per opcode), but nothing downstream uses ReadData2 for LW, since ALUSrc = 1 routes the immediate into the ALU instead:

ReadData1 = R4 = 100
ReadData2 = R5 = 0     (read, but unused this cycle — ALUSrc bypasses it)

5. ALU

Input A = ReadData1 = 100
Input B = sign_extend(0x0000) = 0
Operation = ADD  (forced by ALUOp=00)
Result = 100 + 0 = 100          ; effective address
Zero flag = (Result == 0) = 0   ; unused, Branch=0

6. Memory Stage

MemRead = 1. The ALU's result (100) addresses data memory, and the word stored there is read out onto the memory-data bus feeding the write-back mux:

Address = 100
Mem[100] = 30
Data read = 30

This is the payoff of Instruction 2's store: Mem[100] was set to 30 one cycle ago, and now LW reads that exact value back.

7. Write-Back

MemToReg = 1 selects the memory-read data (not the ALU result) as the write value. RegDst = 0 selects rt = R5 as the destination:

WriteAddr = R5
WriteData = 30   (from data memory, not from the ALU)
R5 ← 30

8. Next PC

Next PC = PC + 4 = 0x00400008 + 4 = 0x0040000C

Instruction 4: SUB R6, R5, R1

1. Fetch

PC = 0x0040000C. Back to R-type: SUB shares ADD's opcode (000000) and differs only in funct.

opcode   rs      rt      rd      shamt   funct
000000   00101   00001   00110   00000   100010
(R-type) (R5)    (R1)    (R6)    (0)     (SUB, 0x22)
 
Full word:  00000000 10100001 00110000 00100010
Hex:        0x00A13022

Arithmetic check: (5<<21) | (1<<16) | (6<<11) | 0x22 = 0xA00000 + 0x10000 + 0x3000 + 0x22 = 0xA13022, zero-extended to 0x00A13022.

2. Decode

Same opcode as Instruction 1, so the main decoder's outputs — the whole control-signal table below — are byte-for-byte identical to Instruction 1's. The only thing that differs between ADD and SUB anywhere in this datapath is a single 6-bit field, funct, consumed three stages downstream in the ALU control logic.

3. Control Signals

Identical to Instruction 1's table — again, because both instructions share opcode = 000000.

4. Register File Read

ReadAddr1 = rs = R5, ReadAddr2 = rt = R1:

ReadData1 = R5 = 30    (written by LW two cycles ago... actually one cycle ago, by Instruction 3)
ReadData2 = R1 = 10

5. ALU

ALUOp = 10, so ALU control reads funct = 100010 and selects SUBTRACT this time, not ADD:

Input A = 30
Input B = 10
Operation = SUBTRACT  (selected via ALUOp=10 + funct=0x22)
Result = 30 - 10 = 20
Zero flag = (Result == 0) = 0    ; 20 is not zero

6. Memory Stage

Not used. MemRead = 0, MemWrite = 0.

7. Write-Back

WriteAddr = R6
WriteData = 20
R6 ← 20

8. Next PC

Next PC = PC + 4 = 0x0040000C + 4 = 0x00400010

Instruction 5: BEQ R6, R2, 1

This is the instruction the whole program has been building toward — the first (and only) time Branch is asserted, and the first time the zero flag actually drives a decision instead of sitting unused.

1. Fetch

PC = 0x00400010. BEQ opcode 000100 (0x04), compared registers R6 and R2 in rs/rt, and a signed 16-bit immediate of 1 (a word count, not a byte count — see step 8).

opcode   rs      rt      immediate
000100   00110   00010   0000000000000001
(BEQ)    (R6)    (R2)    (1)
 
Full word:  00010000 11000010 00000000 00000001
Hex:        0x10C20001

Arithmetic check: (0x04<<26) | (6<<21) | (2<<16) | 1 = 0x10000000 + 0xC00000 + 0x20000 + 1 = 0x10C20001.

2. Decode

Both rs and rt here are pure sources — BEQ never writes a register, so there's no destination field to decode at all, consistent with RegDst/MemToReg being don't-cares in the next table.

3. Control Signals

The BEQ row of the shared table: ALUSrc=0, RegWrite=0, Branch=1, ALUOp=01. Notice ALUSrc = 0 here — unlike LW/SW, BEQ doesn't need the immediate as an ALU input at all; the immediate is only needed later, for the branch-target adder, which is entirely separate hardware from the main ALU.

4. Register File Read

ReadAddr1 = rs = R6, ReadAddr2 = rt = R2:

ReadData1 = R6 = 20    (written by SUB last cycle)
ReadData2 = R2 = 20    (unchanged since the initial state)

5. ALU

ALUOp = 01 forces SUBTRACT unconditionally — this is how "are these two registers equal" gets implemented with the same ALU that does everything else: subtract them, and check whether the result is exactly zero.

Input A = 20
Input B = 20
Operation = SUBTRACT  (forced by ALUOp=01)
Result = 20 - 20 = 0
Zero flag = (Result == 0) = 1     ; equal — this is the bit that decides the branch

This is the one instruction in the whole program where the zero flag isn't a spectator. Branch = 1 AND Zero = 1 together assert the PC-select mux's branch-taken input — both conditions are necessary; Branch alone would let any non-branch instruction's incidental zero result accidentally redirect the PC, and Zero alone would make every ALU operation that happens to produce 0 into a branch.

6. Memory Stage

Not used. MemRead = 0, MemWrite = 0.

7. Write-Back

RegWrite = 0. Nothing is written back — BEQ only ever affects control flow, never register or memory state.

8. Next PC

This is where BEQ diverges from every instruction so far. The datapath always computes both candidate next-PC values in parallel — the sequential PC + 4 and the branch target — and a mux, controlled by Branch AND Zero, picks between them after the fact. Nothing is "skipped" at this stage; both adders just run every cycle, and only one result gets used.

The branch target is computed from PC + 4 (not the original PC), plus the sign-extended immediate shifted left by 2 bits — the left-shift converts an instruction-count offset into a byte-count offset, since instructions are 4 bytes apart:

sequential candidate = PC + 4 = 0x00400010 + 4 = 0x00400014
 
branch-target candidate:
  sign_extend(1)      = 0x00000001
  sign_extend(1) << 2 = 0x00000004        ; 1 word = 4 bytes
  branch target = (PC + 4) + (sign_extend(imm) << 2)
                = 0x00400014 + 0x00000004
                = 0x00400018
 
Branch AND Zero = 1 AND 1 = 1   → mux selects the branch-target candidate
 
Next PC = 0x00400018

R6 == R2 (20 == 20), the branch is taken, and the CPU's next fetch address is 0x00400018 — not 0x00400014. The instruction sitting at 0x00400014 is about to become the interesting case.

Instruction 6: ADD R7, R1, R1 — Skipped

There is no cycle for this instruction. Say that precisely: it isn't "fetched and then discarded," and it isn't "executed with its effects suppressed." A single-cycle CPU has exactly one PC register, and instruction fetch always means "whatever address is currently in that register, present it to instruction memory." At the end of Instruction 5's cycle, the clock edge that commits the PC's new value loaded 0x00400018 into it — not 0x00400014. So on the very next cycle, the address that goes out to instruction memory is 0x00400018. The word encoded at 0x00400014 (which would decode to ADD R7, R1, R1 if anyone ever asked for it) is simply never addressed. No fetch happens against it, so no opcode is ever decoded, no control signals are ever generated, no register is ever read, and nothing in the datapath ever "knows" that instruction exists.

This is worth sitting with because it's a different mechanism from how you might picture "skipping" from software intuition — there's no conditional-fetch logic, no instruction that gets voided mid-pipeline, nothing analogous to a pipeline bubble (that's a real mechanism, but it belongs to pipelined designs, which is exactly where Part 5 of this lesson is headed). In a single-cycle machine, control flow is entirely a matter of which address the PC holds next, decided once, at the very end of the branch instruction's cycle. Every subsequent stage just does its ordinary job on whatever address it's handed.

Concretely, the register file's state confirms nothing changed: R7 is still 0, exactly as it was in the initial state, because no write to R7 was ever attempted — not "attempted and rolled back," but genuinely never attempted at all.

Instruction 7: OR R8, R1, R2

The branch target. This is the instruction the CPU actually executes right after BEQ.

1. Fetch

PC = 0x00400018 — delivered here directly by Instruction 5's branch-target mux, not by any PC + 4 step. OR shares ADD/SUB's opcode and differs, as always, only in funct.

opcode   rs      rt      rd      shamt   funct
000000   00001   00010   01000   00000   100101
(R-type) (R1)    (R2)    (R8)    (0)     (OR, 0x25)
 
Full word:  00000000 00100010 01000000 00100101
Hex:        0x00224025

Arithmetic check: (1<<21) | (2<<16) | (8<<11) | 0x25 = 0x200000 + 0x20000 + 0x4000 + 0x25 = 0x224025, zero-extended to 0x00224025.

2. Decode

3. Control Signals

Once again identical to the ADD and SUB control tables — the third R-type instruction in this program to share this exact signal set, differing from ADD and SUB only in funct and, downstream, in which ALU operation that funct selects.

4. Register File Read

ReadAddr1 = rs = R1, ReadAddr2 = rt = R2:

ReadData1 = R1 = 10   (never modified by this program)
ReadData2 = R2 = 20   (never modified by this program)

5. ALU

ALUOp = 10, funct = 100101 (OR) selects the bitwise-OR operation:

Input A = 10   = 0b01010
Input B = 20   = 0b10100
Operation = OR  (selected via ALUOp=10 + funct=0x25)
 
  01010
| 10100
-------
  11110  = 30
 
Result = 10 OR 20 = 30
Zero flag = (Result == 0) = 0

10 and 20 happen to have no overlapping set bits in this range (0b01010 vs 0b10100), so bitwise OR and arithmetic addition produce the same numeric answer here — 30 either way. That's a coincidence of these particular operand values, not a general property of OR; it's a useful sanity check on the hand arithmetic, not evidence the two operations are interchangeable.

6. Memory Stage

Not used. MemRead = 0, MemWrite = 0.

7. Write-Back

WriteAddr = R8
WriteData = 30
R8 ← 30

8. Next PC

Branch = 0 — this instruction has nothing to do with the branch that landed the CPU here; it's an ordinary R-type instruction that happens to sit at the branch target. Sequential PC advance applies exactly as it did for every non-branch instruction in this trace:

Next PC = PC + 4 = 0x00400018 + 4 = 0x0040001C

0x0040001C is past the end of the listed program — in a real toolchain something would need to live there (another instruction, or a halt/exit mechanism), but that's outside the scope of this seven-instruction trace.

Final State: Registers and Memory

Every value below was produced by exactly one write, in exactly one instruction's cycle, traced above — nothing here is asserted without having been derived.

And the full instruction-level trace of the PC itself, showing the one place it deviates from +4:

0x00400000 → 0x00400004   (ADD,  sequential)
0x00400004 → 0x00400008   (SW,   sequential)
0x00400008 → 0x0040000C   (LW,   sequential)
0x0040000C → 0x00400010   (SUB,  sequential)
0x00400010 → 0x00400018   (BEQ,  TAKEN — branch target, not PC+4)
                            [0x00400014 never fetched]
0x00400018 → 0x0040001C   (OR,   sequential)

Key takeaway: Every one of these 30 values — R3, R5, R6, R8, and Mem[100] — came out of the same fixed hardware (one ALU, one register file, one data memory, one control unit) doing exactly what its control signals told it to on each cycle. Nothing instruction-specific exists in the datapath itself; all of the instruction-specific behavior lives entirely in which control signals get asserted, which is entirely a function of six bits of opcode (and, for R-type, six more bits of funct). That's the single-cycle CPU's whole story, now verified end to end on a real program.

Further Reading

• David A. Patterson and John L. Hennessy, Computer Organization and Design (MIPS/RISC-V editions) — the canonical single-cycle datapath and control-signal derivation this whole lesson follows, including the worked lw/sw/beq/R-type traces this post extends.
• MIT OpenCourseWare, 6.004 Computation Structures, Chapter 14 — Datapath and Control: ocw.mit.edu/courses/6-004-computation-structures-spring-2017/pages/c14/c14s1/
• Sarah L. Harris and David Money Harris, Digital Design and Computer Architecture — a second worked single-cycle datapath trace (RISC-V rather than MIPS), useful for cross-checking the control-signal reasoning against a different but structurally identical ISA.
• GeeksforGeeks, Multi-Cycle Data Path and Control: geeksforgeeks.org/computer-organization-architecture/multi-cycle-data-path-and-control — useful contrast case: the same instruction set executed across multiple clock cycles instead of one, which is the mirror image of everything traced in this post.
• University of Maryland CS411 online notes, Execution of a Complete Instruction — Datapath Implementation: cs.umd.edu/~meesh/411/CA-online/chapter/execution-of-a-complete-instruction-datapath-implementation/index.html — a second worked-example treatment of the fetch/decode/execute/memory/write-back sequence for individual MIPS instructions.

Every instruction in this trace still took exactly one clock cycle — including SW, which never even reads its result back before the cycle ends, and ADD, which never touches memory at all. That's the single-cycle CPU's defining feature and, as the next post argues, also its defining flaw: the clock period has to be long enough for the slowest instruction's signal to propagate through the entire datapath, every single cycle, even for instructions that only need a fraction of that hardware. Lesson 2, Part 5 — "Why Single-Cycle Design Doesn't Scale — The Bridge to Pipelining" — is where that cost gets made precise, and where the fix begins.