Lecture 07 – Ch3 Ch4 Implementations Data Flow Implementation in Hardware and Software Analysis of Control and Data Flow

• \(\dagger\) A Practical Introduction to Hardware Software Codesign Patrick Shaumont

• Book's mapping rules (assumptions):
  • actors implemented as combinational circuits
  • queues implemented as wires
  • initial tokens become registers
• Therefore
  • Actors implemented as combinational circuits will operate within a single clock cycle
  • A chain of back-to-back actors without a register (initial token) between must operate as a whole in less than a clock cycle, their combinatorial delays add
  • A critical path can be identified from the resource graph as the back-to-back actor chain with the largest sum of delays, which related to the maximum allowed clock speed

• We'll now analyze a process for converting a limited subset of C code to combinational HW
• We'll first need to identify connections required in the hardware

• For the moment, view C as algorithm behavior description
• Data Edge
  • defines data production and consumption relationship
  • fundamental aspect of algorithm (information flow)
  • must always be implemented
• Control Edge
  • defines order of execution/firing (e.g. actor X must fire before actor Y)
  • consequence of implementation
  • not fundamental, may be removed in case of possible concurrency

\(\dagger\)

• C allows writing to variables multiple times before use making identification of data producer-consumer relationships difficult
• To construct the data flow graph, we'll use a control flow graph (CFG)
• A control path is identified according to conditional branching conventions in C

• IF,WHILE,DO\(\dagger\):

†Shaumont

• FOR LOOP\(\dagger\):

†Shaumont

• Edges from Explicit Assignment Statements:
  • Start by identifying a node \(\bf j\) which consumes a variable \(\bf v\) .
    
  • Identify all possible nodes \(\bf i\) which write to \(\bf v\) .
  • Draw a line from \(\bf i\) to \(\bf j\) if a control path exist from \(\bf i\) to \(\bf j\)
    AND no node in that path also writes to \(\bf v\)
  • Repeat for every node \(\bf j\) and every variable \(\bf v\) it uses
• Edges from Conditional Expression Evaluations (have implicit output flag variable)
• Add data edge from conditional expression evaluation node \(\bf i\) to \(\bf j\) if a control path exists from \(\bf i\) to \(\bf j\)

DFG for node 5\(\dagger\):

†Shaumont

DFG\(\dagger\) showing only a and b…must then include computed condition flags:

†Shaumont

• Assumptions for this approach of C to Hardware translation
  1. Only scaler code ( no pointers or arrays)
  2. Each C statement is a single clock cycle (will visit alternatives later)

1. C variables implemented in HW as registers w/multiplexer if multiple sources (mux controlled by FSM controller)
2. C expressions implemented as Combinatorial Code, output results appropriately as either
3. data for datapath (example where b is a register: "b=a+1;" The expression a+1 is in the data path )
4. flags for controller (example: "if (a>b) b = a+1;" a>b is a generated flag fed to the controller)
3. data path and register variables connected according to DFG
4. for each assignment, connect combinatorial to register
5. for each data edge, connect register to input of combinatorial circuit
6. connect appropriate system inputs and outputs

CFG\(\dagger\):

†Shaumont

Data Path Hardware\(\dagger\):

†Shaumont

• The controller unit is responsible for operating the data path elements
• The CFG directly translates to a finite-state machine (FSM)
• The controller together with the datapath then represent a Finite-State Machine with Datapath FSMD
• FSMD may be used to represent any algorithm intended for single clock domain hardware. FSMD will be discussed more later.

CFG:

• next state logic directly from CFG with conditions
• control outputs are added to each state to complete the FSM
• a decoder implemented as a lookup table can help

†Shaumont

Controller State machine and Datapath:

LUT:

• Previous implementation assumed only at least one line of code per clock cycle
• Need method to identify multiple lines of code to be executed in a clock cycle
• The primary approach is using blocks of code representing Signal Assignment Code where each variable is assigned once. We need to examine the question, “When can multiple lines of code be executed in a clock cycle?”
• This is related to writing a proper block of Verilog code that represents combinatorial logic terminated by one set of register updates in a cycle

a=b+1;
a=a*3;

a = (b+1)*3;

• can be implemented in hardware with

  

  or perhaps

  

• ensure the in a pass of code a given variable is only assigned once
• conversion involves
  • introduction of new variAbles and
  • renaming to ensure single assignments in a section of code.

a=b+1;
a=a*3;

a1=b+1;
a2=a1*3;

• simplifies identification of the producing expression
• easier to understand the underlying data-flow
• data-dependency graphs can be generated more easily from single-assignment code
• unique identifiers facilitate association of hardware nets to variables in code

MERGE is a conceptual tool that can be introduced facilitate code analysis. We'll first motivate MERGE with an example.

a=b;
for(i=1;i<6;i++){
   a=a+i;


}
//(Schaumont 2010)

a1=b;
for(i=1;i<6;i++){
  a2= a? + i; //what to use? 
             // for  first iteration need a1, 
             //      thereafter       need a2
}
//(Schaumont 2010)

Solution is to use introduce the concept of a MERGE**. A MERGE maps to a mux in hardware, typically creating a loop or feedback.

Still must ensure that no combinatorial loops are formed, adding registers and multiple clock cycles as needed (below a2 may be implemented a register to ensure this).

a1=b;
for(i=1;i<6;i++){
   a3=MERGE(i==1?a1:a2);    
                        //now a1 and a2 will be registers 
   a2=a3+1;
}
// (Schaumont 2010)

†Shaumont

• Warning MERGE is CONCEPT not a Verilog Construct Do not attempt to use merge in your code.

• Unrolling is another technique to create single assignment code:

  a1=b;
  a2=a1+1;
  a3=a2+2;
  a4=a3+3;
  a5=a4+4;
  a6=a5+5;
  

  hardware if implemented in one clock cycle with 5 adders

  

• Algorithmic simplification , in this case arithmetic simplification can trim unnecessary complexity

  a = b+15;
  

  implies a single addition
  

  

This example code describes an iterative algorithm that will be implemented with registers

int gcd(int a , int b) {
  while ( a != b) {



    if ( a > b )
      a = a-b;
    else
      b = b-a;
  }
  return a;
}
// Shaumont 2010

int gcd(int a1 , int b1) {
    while (MERGE(_?a1:a2)!=
                  MERGE(_?b1:b2){
      a3 = MERGE(_?a1:a2);
      b3 = MERGE(_?b1:b2);
      if (a3 > b3)
        a2 = a3-b3;
      else
        b2 = b3-a3;
    }
    return a2;
}
// Schaumont 2010

Hardware Implementation:

• Fill in conditions of MERGE to complete the code
• For this iterative algorithm, the single-assignment code helps reveal that one full iteration of the algorithm can be completed without any intermediate registers
  • implies that one full iteration might be computed in combinational logic if timing allows
    • i.e. implies that one full iteration might be computed per clock cycle if timing allows

• Single Assignment Code allows examination of data dependencies and hardware resources such as what can be done in a single clock cycle (combinatorial) and where a register is required.
• In the previous code, multiple lines may be computed in one cycle
  • modifying the datapath or providing forwarding of the the flags allows for combining the comparison, subtraction, and update
  • The logic in red could be implemented in either the controller or the datapath (partioning of datapath and fsm controller is not unique in finite state machine with datapath FSMD)
    • Later we'll see that implementing the logic in a REPROGRAMMABLE controller allows for datapath reuse,
    • whereas implementation in the datapath could be more optimal but tailors the datapath rigidly for the application, making the datapath less flexible

• These concepts are also important when writing behavioral HDL code in Verilog or VHDL.