Module 2.2: Designing Custom Single-Purpose Processors - The FSMD Approach

Problem Description and Algorithmic Representation: The Starting Point

• Defining the Problem: Before any design work begins, a clear, unambiguous, and complete specification of the problem is essential. What are the inputs? What are the outputs? What is the exact transformation or computation required? What are the performance constraints (speed, throughput, latency)? What are the resource constraints (area, power)?
• High-Level Algorithmic Representation: Once the problem is defined, the first step towards hardware design is to express the solution as a high-level algorithm. This step is crucial because it allows us to reason about the logic and control flow without immediately worrying about hardware details.
• Common Notations:
  • Pseudocode: An informal, high-level description of an algorithm's operating principle. It uses the structural conventions of programming languages but is intended for human reading rather than machine execution.
  • C/C++ Code: A common starting point for hardware design, as many algorithms are initially developed and verified in these languages. Tools exist to synthesize hardware from a subset of C/C++ (High-Level Synthesis - HLS).
  • Flowcharts: Graphical representation of an algorithm, showing steps as boxes of various kinds and their order by connecting them with arrows. Useful for visualizing control flow.
• Importance: This step helps in:
  • Clarity: Ensuring a shared understanding of the problem and its solution among designers.
  • Verification: The algorithm can be simulated and tested in software to ensure its correctness before committing to costly hardware design.
  • Abstraction: It allows focusing on the 'what' (the logic) before the 'how' (the hardware implementation).
• Example: A Simple Finite Impulse Response (FIR) Filter: Let's consider a simple 3-tap FIR filter, commonly used in DSP. y[n] = c0 * x[n] + c1 * x[n-1] + c2 * x[n-2] Where:
  • y[n] is the current output sample.
  • x[n] is the current input sample.
  • x[n-1] and x[n-2] are previous input samples (delayed versions).
  • c0, c1, c2 are filter coefficients (constants). Pseudocode representation for a single output calculation:

    function Compute_FIR_Output(current_input_x, coeff_c0, coeff_c1, coeff_c2):
      // Assume registers for previous inputs: X_prev1, X_prev2
      // Shift operations (oldest input drops, current input becomes latest previous)
      X_prev2 = X_prev1
      X_prev1 = current_input_x
      // Perform multiplications
      term0 = coeff_c0 * current_input_x
      term1 = coeff_c1 * X_prev1
      term2 = coeff_c2 * X_prev2
      // Perform additions
      sum01 = term0 + term1
      final_output = sum01 + term2
      return final_output

Finite State Machine with Datapath (FSMD) Model: The Blueprint

• Introduction to FSMD: The Synergy of Control and Data
• Finite State Machine (FSM) - The Controller: This is the "brain" of the SPP. It dictates the sequence of operations. It transitions between a finite number of states, each representing a distinct phase or step in the algorithm. Transitions are triggered by internal conditions (status signals from the datapath) or external inputs. In each state, the FSM generates control signals that orchestrate the operations within the datapath.
• Datapath - The Data Processor: This is the "muscle" of the SPP. It comprises the hardware units that store and manipulate data. These include:
  • Registers: For storing variables and intermediate results.
  • Functional Units: Logic blocks that perform arithmetic (adders, multipliers, ALUs) and logical operations (AND, OR, XOR).
  • Multiplexers: For selecting data paths.
  • Interconnections: Wires that connect these components.
• Interaction: The controller provides control signals to the datapath (e.g., "load register A," "enable adder," "select input 0 on mux"). The datapath, in turn, provides status signals (conditions) back to the controller (e.g., "result is zero," "overflow occurred") that influence the next state transition of the FSM.
• Translating Algorithmic Constructs into FSMD States and Operations: This is the most critical step in conceptualizing your SPP. You systematically map each part of your algorithm to components and actions within the FSMD.
• Variable Declarations: Each persistent variable in your algorithm (X_prev1, X_prev2 in our FIR example) will typically map to a dedicated register in the datapath. Inputs and outputs will also be associated with registers or I/O ports.
• Assignment Statements (variable = expression): These require routing data. The expression part dictates the functional units needed (e.g., term0 = c0 * current_input_x requires a multiplier). The result of the expression needs to be written into the target variable's register. This means enabling the write operation of that register (a control signal from the FSM) and ensuring the correct data path is selected to its input (using a multiplexer, if multiple sources can write to it).
• Example (FIR): X_prev2 = X_prev1 implies routing the output of the X_prev1 register to the input of the X_prev2 register, and asserting the load_X_prev2 control signal.

Partitioning FSMD into Controller and Datapath: The Two Pillars

• Controller Design: The Brain of the SPP
• Role and Function: The controller is a sequential circuit responsible for generating the necessary control signals to orchestrate the datapath's operations in the correct sequence. It interprets inputs (external controls, status signals from datapath) and current state to determine the next state and corresponding outputs.
• Extracting Control Logic:
  • States: Identify all the distinct states identified in your FSMD (e.g., IDLE, LOAD_INPUTS, MULTIPLY, ADD1, ADD2, DONE).
  • Transitions: Define the conditions under which the FSM moves from one state to another (e.g., start_signal, zero_flag).
  • Control Signals: For each state, list all the specific control signals that must be asserted (set to '1') or de-asserted (set to '0') to make the datapath perform its intended operation in that cycle. These are the outputs of the controller.
  • Status Signals: Identify all inputs the controller needs from the datapath or external world to make decisions about state transitions. These are the inputs to the controller.
  • Representing the Controller as a Pure Finite State Machine (FSM):
  • State Diagram: A graphical representation showing states as nodes and transitions as directed edges, labeled with input conditions and output control signals.
  • State Table: A tabular representation listing current state, inputs, next state, and outputs for all possible combinations.
• Implementing the FSM:
  • State Register: A bank of D-type flip-flops (typically) whose outputs represent the current state. The number of flip-flops depends on the number of states (e.g., for 5 states, 3 flip-flops: lceillog_25rceil=3).
  • Next-State Logic (Combinational Logic): This is a combinational circuit that takes the current state (from the state register) and the controller inputs (status signals, external controls) and calculates the next state to be loaded into the state register at the next clock edge. This logic is derived from the state table.
  • Output Logic (Combinational Logic): This is another combinational circuit that takes the current state (and sometimes, the controller inputs, for Mealy-type FSMs) and generates all the necessary control signals that drive the datapath. This logic is also derived from the state table.