6.3 The Fetch–Decode–Execute Cycle & RTL Traces

Theory: The Fetch–Decode–Execute Cycle & RTL Traces

A program is a sequence of stored instructions. The CPU runs it by repeating one loop, the fetch–decode–execute cycle (also called the instruction cycle), from power-on until it halts. Every instruction, no matter how simple or complex, passes through the same stages. Being able to trace the registers through this cycle is one of the most common exam questions on MARIE.

The Four Stages

1. Fetch: copy the instruction whose address is in the PC from memory into the IR, and advance the PC so it points at the next instruction.
2. Decode: look at the opcode IR[15–12] to find out which instruction this is, and copy the address field IR[11–0] into the MAR.
3. Get operand (only if needed): if the instruction uses a value from memory (Load, Add, Subt, AddI, …), read it into the MBR.
4. Execute: carry out the instruction’s remaining microoperations. Then go back to step 1.

The RTL of Fetch and Decode

These microoperations are identical for every instruction:

Fetch:   MAR <- PC
         IR  <- M[MAR]
         PC  <- PC + 1
Decode:  MAR <- IR[11-0]
         (decode IR[15-12])
Operand: MBR <- M[MAR]            (only if the instruction needs it)
Execute: ... depends on the opcode ...

The PC is incremented during fetch, before the instruction executes. So while an instruction is executing, the PC already holds the address of the next instruction. This is why Skipcond skips by doing one more PC ← PC + 1, and why JnS saves the PC as the return address.

Mini-example

The PC holds 100 and $M[100] = \text{1104}$ (Load 104). Fetch: MAR = 100, IR = 1104, PC = 101. Decode: MAR = IR[11–0] = 104, opcode 1 = Load. Operand: MBR = M[104]. Execute: AC ← MBR.

Reading a Trace Table

A trace table has one row per microoperation and one column per register (PC, IR, MAR, MBR, AC). Write a register’s value after that microoperation; values that do not change are copied down. Dashes mean “unknown / not yet set”. Highlighting in your head which cell changes in each row is the fastest way to check yourself: each microoperation changes exactly one register (the one on the left of the arrow), except the fetch step that also increments the PC.

The Addition Program (Null & Lobur, Table 4.3)

It computes $\text{0023}_{16} + \text{FFE9}_{16}$, i.e. $35 + (-23) = 12 = \text{000C}_{16}$, and stores the result in 106. The full register traces are in Worked Example 1.

Interrupts (brief)

Real machines add one more step to the loop: after each instruction, the CPU checks for an interrupt (a signal from an I/O device, a timer, or an error such as division by zero; a program can also raise a software interrupt). If one is pending, the CPU saves the PC (and other state), runs an interrupt service routine, then restores the state and continues the interrupted program. MARIE’s basic cycle omits interrupts so the core loop stays simple.

Worked Examples

        ORG 010
        load x
        subt y
        output
        halt
x,      dec -12
y,      dec 20