In this lecture, we are going to have a close look at the general structure of combinational circuits 1
and introduce a graphical technique to model such circuits 2
This graphical representation which is called directed acyclic graph or DAG for short gives us 3
a set of guidelines to describe a combinational circuit in HLS. 4
Let’s first define the dataflow concept. Dataflow represents the movement of data through a design from 5
inputs to the outputs. 6
Dataflow graph (DFG) is one of the common modelling techniques for computational systems. 7
A dataflow graph is a directed graph in which operators such as logical, arithmetic and assignment operators 8
are represented by the graph nodes, and information flow is represented by the arcs. 9
For example. 10
this arithmetic expression can be modelled by this graph. 11
As the expression has two operators which are an addition and a multiplication, the graph has two notes. 12
The graph also has three inputs and an output. 13
The first node multiplies the c and b inputs. The second operator adds the result of the multiplication 14
to the d input. 15
As the second example, let’s consider this Boolean expression. The corresponding dataflow graph has five 16
operators, four inputs and one output. 17
Acyclic Dataflow graph (ADFG) is a dataflow graph without a cycle path or loop. In other words, 18
the graph is a Directed Acyclic Graph or DAG. 19
This DAG represents the dataflow of a three-layer perceptron neural network. It consists of six operators, 20
two inputs and one output. 21
The flow of data is from inputs to the output without any feedback or loop. 22
The second example of a dataflow graph contains a loop. 23
Therefore, this DFG is not an ADFG or DAG. 24
The operators in an ADFG can be arithmetic, logical, assignment and select operators. 25
An ADFG can model a combinational circuit. In other words, if we can model an HLS hardware description 26
with an ADFG, then it can be synthesised into a combinational circuit. 27
A typical HLS tool can convert a cyclic DFG into an acyclic DFG if the loop can be unrolled to break 28
the cycles. For this purpose, The HLS should be able to predict the exact number of loop execution. 29
For example, if in this circuit the loop should be run three times, then, the HLS repeats the circuit 30
three times to break the cycles. 31
I will explain practically how to describe this technique in an HLS source code in the combinational 32
loop section later in this course. 33
This if-statement has two branches. A DAG can model this code. The DAG consists of four nodes 34
corresponding to the operators in the code. The add-operators perform normal addition. The greater than 35
operator generates one if a > 3 otherwise 0. The select operator acts as a switch, 36
if s equals to 1 then connects the t1 to the x otherwise passes the t2 to the x output. 37
This code is a case that can lead to a cyclic DFG. The code explicitly uses a variable on both sides 38
of an expression. 39
This code shows an example of an implicit data dependency that can lead to a loop in DFG if it is used inside 40
a software loop-statement. The code updates the x variable 41
if a is greater than three otherwise x should keep its previous value. 42
This example and the previous one can easily be converted into an ADFG or a combinational circuit if 43
the HLS knows the number of iterations that the cycle runs. 44
As I mentioned earlier, later in this course, the combinational loop section will explain the corresponding 45
techniques to guide the HLS tool to do this conversion. 46
How can we use the combinational circuit description to implement a real example? In the next lecture, 47
taking a simple traffic light controller, 48
I will explain how to describe a real combinational circuit in HLS. 49
These are our takeaway messages. A combinational circuit can be modelled by an acyclic dataflow graph, 50
also known as DAG 51
A cyclic DFG can be converted to a DAG if we know the number of loop execution and unroll the loop to break the 52
cycles. 53
Now, the quiz question. 54
Draw the DAG modelling the following code.