Iterative programming structures such as for-loops are the most valuable techniques in developing 1
repetitive parametric hardware structures. 2
What is the structure of a repetitive combinational logic circuit? 3
In this lecture, I am going to give you a big picture of a repetitive hardware structure to be used later 4
throughout this section. 5
Software loop statements represent the repetitive patterns in an algorithm. 6
As we consider only combinational circuits in this course, we should understand how these types of circuits 7
can run a piece of code described by a software loop statement. 8
For the sake of simplicity, I’ll consider for-loop statements. However, some examples 9
that use while-loop statements will be explained later during the course. 10
Let’s have a look at a for-loop statement in C language. According to the loop index and its condition, 11
this for-loop has three iterations, each of which executes two tasks named task1 and task2. 12
The software 13
execution of this loop can be shown by a flow-chart graph or a control-data flow graph. 14
First, the loop index gets 0 as its initial value. 15
Then as it is less than 3, the loop body will be executed. After executing the tasks, the loop 16
index is incremented, and as it is still less than 3, the second iteration of the loop is executed. 17
And then the third iteration is performed. 18
After the third iteration, the loop index would be 3, which does not satisfy the for-loop condition; 19
therefore, the execution control passes to the next statement after the loop in the program. 20
This behaviour shows the sequential execution of the loop body on a CPU. Notice that, there is one instance of 21
each task invoking several times. 22
Now let’s have a look at the hardware implementation. 23
The execution of the corresponding combinational hardware is a little bit different. Based on the dependency 24
among tasks, 25
there can be different scenarios. 26
First of all, the combinational circuit of this loop should instantiate separate hardware for each 27
task in the loop iterations. 28
That means, as the loop has three iterations, and each iteration has two tasks, the hardware implementation 29
should have 6 hardware modules implementing the tasks individually. 30
In the first scenario, all consecutive tasks are dependent on each other results, 31
that means they need the results generated by their previous one. 32
In this case, as shown in this figure, sequential task execution is expected. In the second scenario, 33
the tasks in an iteration are dependent, but the tasks in different iterations are independent as they 34
receive different parts of data. 35
Therefore, all task1 from different iterations can be executed in parallel and all task2 36
instances are performed afterwards. 37
In the third scenario, we assume all tasks are independent as they may work on different data and don’t 38
use the other tasks results. 39
In this case, all tasks run in parallel. 40
Please don’t be scared of the little bit complexity in hardware execution flow, as most of them will 41
be managed by the HLS tools automatically. 42
Let’s consider a real example. An N-bit binary adder is a combinational hardware circuit with 43
a repetitive computation pattern. It uses N full-adders executed sequentially in order to add 44
two N-bit binary numbers. As each full-adder should use the carry-bit generated by its predecessor, 45
then the execution is sequential. 46
Another example of a combinational circuit with a repetitive pattern is one-counter which count 47
the number of 1s in a binary representation of a given number. This circuit can use N-adders executed 48
sequentially, to find the number of 1s. 49
In addition, there is another hardware implementation of this design that uses logN level of adders, 50
connected through a binary tree structure. 51
This implementation is preferable because it is faster than the previous implementation. In the rest of this section, 52
I will explain how to describe an algorithm to guide the HLS tool utilising these types of optimisations. 53
In the next step, I will explain how to describe a combinational loop in Xilinx Vivado-HLS environment. 54
These are the takeaway messages of this lecture. 55
Using software loop statements is necessary for describing combinational circuits in HLS 56
In hardware designs, Statements in a loop iteration can execute in parallel (intra-iteration parallelism), Statements among loop iterations 57
can also execute in parallel (iter-iteration parallelism) 58
Now the first quiz: Let’s consider the following for-loop. Then draw an execution graph for a combinational 59
circuit that performs this loop. 60
As the second quiz perform the same task on this for-loop.