Classroom Public page

Lab 7.1: Fetch-Decode-Execute Trace on Paper

608 words

~75 minutes. Trace a 7-instruction program through the FDE cycle, tracking the state of every register and the PC at each step.

Goal: trace a short program through the fetch-decode-execute cycle, writing down the state of the machine (PC, IR, registers, flags, relevant memory) after each instruction.

Estimated time: 75 minutes

Prerequisites: Week 7 lecture (FDE cycle, instruction set table, branch mechanics)

The instruction set for this lab

Use the minimal ISA from the Week 7 lecture:

Instruction Meaning
MOV rx, imm rx = imm (immediate value)
LOAD rx, addr rx = memory[addr]
STORE addr, rx memory[addr] = rx
ADD rx, ry, rz rx = ry + rz
SUB rx, ry, rz rx = ry - rz
CMP rx, ry set zero flag if rx = ry; clear zero flag otherwise
JMP addr PC = addr
JEQ addr if zero flag = 1: PC = addr; else PC = PC + 1

PC increments by 1 per instruction (word-addressed for simplicity).

The program to trace

Initial state: all registers = 0, all flags = 0, memory is as shown below.

Memory layout:

Addr 0: MOV r0, 0        (initialize sum)
Addr 1: MOV r1, 3        (loop limit)
Addr 2: MOV r2, 1        (decrement amount)
Addr 3: ADD r0, r0, r1   (sum = sum + r1)
Addr 4: SUB r1, r1, r2   (r1 = r1 - 1)
Addr 5: CMP r1, r3       (compare r1 to r3; r3 starts at 0)
Addr 6: JEQ 8            (if r1 = 0, jump to address 8)
Addr 7: JMP 3            (else loop back to address 3)
Addr 8: STORE 20, r0     (store the result at memory address 20)

This program sums 3 + 2 + 1 = 6 and stores the result at address 20.

Part A: Full trace table

For each executed instruction (in the order the CPU actually executes them, including loop iterations), fill in one row of this table:

Step Addr fetched Instruction r0 after r1 after r2 after r3 after PC after zero flag after
1 0 MOV r0, 0 0 0 0 0 1 0
2
...

Continue until the STORE instruction at address 8 executes. You will execute more than 9 steps total because of the loop.

Write the final value of r0 when the loop terminates. Does it match 3+2+1=6?

Part B: Identify the branch

In your trace table, find:

  1. The first time JEQ executes and the branch is NOT taken (zero flag = 0). What does the PC become?
  2. The first time JEQ executes and the branch IS taken (zero flag = 1). What does the PC become?

Part C: Memory state at end

After STORE executes, what is memory[20]? Write the value.

Part D: Written reflection

Answer in your worksheet:

  1. How many times total did the instruction at address 3 (ADD r0, r0, r1) execute?
  2. How many total FDE cycles did the program take from start (address 0) to end (address 8 completed)?
  3. If the loop limit were 100 instead of 3 (i.e., MOV r1, 100 at address 1), how many total cycles would the program take? You do not have to trace it; reason from the pattern.

Expected output / artifact

lab-7-1-fde-trace.txt with:

  • The complete trace table (all rows filled in)
  • Part B identification of branch behavior
  • Part C memory state
  • Part D written answers
git add lab-7-1-fde-trace.txt
git commit -m "lab-7-1: fetch-decode-execute trace"

Common pitfalls

  • PC increment: PC increments by 1 after the fetch, before the instruction executes. JMP and JEQ override the PC during execute. So after a JMP 3, the PC is 3 (not 8).
  • CMP instruction: CMP sets the zero flag based on the comparison but does NOT write a result to a register. r1 does not change when CMP executes.
  • r3 is always 0: the program never writes to r3. It starts at 0 and stays at 0. CMP r1, r3 compares r1 to 0.
  • Loop count: the loop runs 3 times (r1 decrements from 3 to 2 to 1 to 0). Count your iterations carefully.

Stretch (optional)

Modify the program to sum 1+2+3+4+5 instead of 3+2+1. Describe the change you make to the program (which instruction changes, and to what). How many total ADD executions would the new program need?

Lab 7.1 v0.1.