Implementing Finite State Machines for Control

In this lesson, you will learn how to design a Finite State Machine (FSM) to orchestrate the sequential steps required to execute a single instruction across multiple clock cycles.

Moving Beyond Single-Cycle Constraints

In a single-cycle processor, every instruction must complete in one clock period, which forces the clock to be as slow as the longest instruction. By moving to a multi-cycle datapath, we break an instruction into smaller pieces, like "Fetch," "Decode," and "Execute." An FSM acts as the "brain" or controller that sequences these steps, ensuring the right hardware components—like the ALU or Memory—are active at the exact right moment.

How the FSM Orchestrates Control

An FSM consists of states, transitions, and outputs. Each state corresponds to one clock cycle of the instruction execution. The "Control Unit" logic reads the current state and the Opcode from the instruction register to determine which signals to assert (e.g., RegWrite, MemRead, or ALUSrc).

Imagine a simple instruction that needs to fetch data from memory and then add it to a register. The FSM would move through these states:

1. State 0 (Fetch): Send PC to memory, increment PC.
2. State 1 (Decode): Read registers.
3. State 2 (Execute): Perform the addition in the ALU.
4. State 3 (Write Back): Update the register file.

The logic looks conceptually like this:

// Pseudo-code for state transition logic
switch (current_state) {
    case FETCH:
        ControlSignals = {MemRead, IorD_0, IRWrite};
        next_state = DECODE;
        break;
    case DECODE:
        ControlSignals = {ALUSrcA_0, ALUSrcB_11};
        next_state = EXECUTE;
        break;
    // ... remaining states
}

Why State Matters

The power of the FSM is that it allows hardware reuse. Because the FSM keeps track of where we are in the process, we can use the same ALU or the same Memory unit for different stages of the instruction. By "holding" the CPU in a specific state, we prevent data hazards and ensure that the signals driving our registers are stable before the next clock edge triggers a write.

Key Takeaway: An FSM controls multi-cycle execution by sequences of states that dictate which hardware components to enable, allowing complex instructions to be broken into manageable, clocked steps.