0 1 00:00:02,600 --> 00:00:07,640 In this lecture, we are going to have a close look at the general structure of combinational circuits 1 2 00:00:07,910 --> 00:00:11,420 and introduce a graphical technique to model such circuits 2 3 00:00:11,960 --> 00:00:19,070 This graphical representation which is called directed acyclic graph or DAG for short gives us 3 4 00:00:19,070 --> 00:00:22,920 a set of guidelines to describe a combinational circuit in HLS. 4 5 00:00:24,830 --> 00:00:30,950 Let’s first define the dataflow concept. Dataflow represents the movement of data through a design from 5 6 00:00:30,950 --> 00:00:32,240 inputs to the outputs. 6 7 00:00:32,690 --> 00:00:38,060 Dataflow graph (DFG) is one of the common modelling techniques for computational systems. 7 8 00:00:38,690 --> 00:00:47,240 A dataflow graph is a directed graph in which operators such as logical, arithmetic and assignment operators 8 9 00:00:47,240 --> 00:00:52,880 are represented by the graph nodes, and information flow is represented by the arcs. 9 10 00:00:53,330 --> 00:00:53,990 For example. 10 11 00:00:54,200 --> 00:00:57,290 this arithmetic expression can be modelled by this graph. 11 12 00:00:59,020 --> 00:01:05,470 As the expression has two operators which are an addition and a multiplication, the graph has two notes. 12 13 00:01:06,010 --> 00:01:08,770 The graph also has three inputs and an output. 13 14 00:01:09,890 --> 00:01:17,450 The first node multiplies the c and b inputs. The second operator adds the result of the multiplication 14 15 00:01:17,450 --> 00:01:18,050 to the d input. 15 16 00:01:20,420 --> 00:01:26,570 As the second example, let’s consider this Boolean expression. The corresponding dataflow graph has five 16 17 00:01:26,570 --> 00:01:29,510 operators, four inputs and one output. 17 18 00:01:32,890 --> 00:01:41,160 Acyclic Dataflow graph (ADFG) is a dataflow graph without a cycle path or loop. In other words, 18 19 00:01:41,610 --> 00:01:44,760 the graph is a Directed Acyclic Graph or DAG. 19 20 00:01:46,470 --> 00:01:53,310 This DAG represents the dataflow of a three-layer perceptron neural network. It consists of six operators, 20 21 00:01:53,580 --> 00:01:55,380 two inputs and one output. 21 22 00:01:55,390 --> 00:02:00,150 The flow of data is from inputs to the output without any feedback or loop. 22 23 00:02:00,840 --> 00:02:04,470 The second example of a dataflow graph contains a loop. 23 24 00:02:04,680 --> 00:02:09,150 Therefore, this DFG is not an ADFG or DAG. 24 25 00:02:09,540 --> 00:02:15,570 The operators in an ADFG can be arithmetic, logical, assignment and select operators. 25 26 00:02:16,920 --> 00:02:24,030 An ADFG can model a combinational circuit. In other words, if we can model an HLS hardware description 26 27 00:02:24,210 --> 00:02:29,100 with an ADFG, then it can be synthesised into a combinational circuit. 27 28 00:02:30,540 --> 00:02:39,300 A typical HLS tool can convert a cyclic DFG into an acyclic DFG if the loop can be unrolled to break 28 29 00:02:39,300 --> 00:02:45,730 the cycles. For this purpose, The HLS should be able to predict the exact number of loop execution. 29 30 00:02:46,200 --> 00:02:51,990 For example, if in this circuit the loop should be run three times, then, the HLS repeats the circuit 30 31 00:02:51,990 --> 00:02:54,000 three times to break the cycles. 31 32 00:02:55,980 --> 00:03:01,950 I will explain practically how to describe this technique in an HLS source code in the combinational 32 33 00:03:01,950 --> 00:03:04,260 loop section later in this course. 33 34 00:03:06,440 --> 00:03:14,210 This if-statement has two branches. A DAG can model this code. The DAG consists of four nodes 34 35 00:03:14,210 --> 00:03:22,600 corresponding to the operators in the code. The add-operators perform normal addition. The greater than 35 36 00:03:22,620 --> 00:03:31,190 operator generates one if a > 3 otherwise 0. The select operator acts as a switch, 36 37 00:03:31,910 --> 00:03:41,240 if s equals to 1 then connects the t1 to the x otherwise passes the t2 to the x output. 37 38 00:03:43,920 --> 00:03:52,680 This code is a case that can lead to a cyclic DFG. The code explicitly uses a variable on both sides 38 39 00:03:52,680 --> 00:03:53,580 of an expression. 39 40 00:04:00,280 --> 00:04:07,730 This code shows an example of an implicit data dependency that can lead to a loop in DFG if it is used inside 40 41 00:04:07,730 --> 00:04:11,350 a software loop-statement. The code updates the x variable 41 42 00:04:11,530 --> 00:04:16,390 if a is greater than three otherwise x should keep its previous value. 42 43 00:04:16,480 --> 00:04:24,070 This example and the previous one can easily be converted into an ADFG or a combinational circuit if 43 44 00:04:24,070 --> 00:04:28,060 the HLS knows the number of iterations that the cycle runs. 44 45 00:04:29,380 --> 00:04:35,530 As I mentioned earlier, later in this course, the combinational loop section will explain the corresponding 45 46 00:04:35,530 --> 00:04:39,120 techniques to guide the HLS tool to do this conversion. 46 47 00:04:41,630 --> 00:04:47,000 How can we use the combinational circuit description to implement a real example? In the next lecture, 47 48 00:04:47,240 --> 00:04:49,410 taking a simple traffic light controller, 48 49 00:04:49,610 --> 00:04:53,120 I will explain how to describe a real combinational circuit in HLS. 49 50 00:04:57,950 --> 00:05:04,490 These are our takeaway messages. A combinational circuit can be modelled by an acyclic dataflow graph, 50 51 00:05:04,670 --> 00:05:07,190 also known as DAG 51 52 00:05:07,190 --> 00:05:14,180 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 53 00:05:14,180 --> 00:05:14,810 cycles. 53 54 00:05:17,660 --> 00:05:18,800 Now, the quiz question. 54 55 00:05:20,510 --> 00:05:23,150 Draw the DAG modelling the following code.