Thomas Bollaert’s Blog

HLS Fundamentals / Part 2

In my last two posts, I introduced the question that proved the most challenging in the HLS Bluebook quiz (here) and presented some fundamental concepts about loop unrolling and loop pipelining and explained why answer 2 was not the right one (here).

Let’s now see what happens in the case of answer 1, when we unroll LOOP0 by 4 and pipeline the design with II=1.

Partially unrolling by 4 means that we transform the loop into a new one which now has only 8/4=2 iterations, and where each iteration of the new loop implements 4 iterations of the original loop. The corresponding C code would look like:

void acc(int din[8], int &dout)

{

  int tmp;

  LOOP0: for(int i=0; i<8; i+=4) {

    tmp+=din[i+0];

    tmp+=din[i+1];

    tmp+=din[i+2];

    tmp+=din[i+3];

  }

  dout = tmp;

}

The schedule for one loop iteration would look like as follows:

|RD0|ADD|ADD|

|RD1|   |   |

|RD2|ADD|   |

|RD3|   |   |

In the first cycle, 4 inputs are read. In the following cycles, these 4 values are summed together, possibly using a balanced adder tree.

If the design was not pipelined, the second iteration of the partially unrolled LOOP0 would start after the end of the first iteration and the schedule would look like:

|RD0|ADD|ADD|RD4|ADD|ADD|

|RD1|   |   |RD5|   |   |

|RD2|ADD|   |RD6|ADD|   |

|RD3|   |   |RD7|   |OUT|

Instead, the design is pipelined with II=1, meaning that the second iteration of LOOP0 should start 1 cycle after the start of the first iteration. Similarly the next design iteration (to process a new set of inputs) would start 1 cycle after the start of the last LOOP0 iteration. The schedule drawn below shows the two iterations of the partially unrolled LOOP0 corresponding to one design iteration, followed by two more iterations of LOOP0 corresponding to a second loop iteration.

|RD0|ADD|ADD|

|RD1|   |   |

|RD2|ADD|   |

|RD3|   |   |

    |RD4|ADD|ADD|

    |RD5|   |   |

    |RD6|ADD|   |

    |RD7|   |OUT|

        |RD0|ADD|ADD|   

        |RD1|   |   |   

        |RD2|ADD|   |   

        |RD3|   |   |   

            |RD4|ADD|ADD|

            |RD5|   |   |

            |RD6|ADD|   |

            |RD7|   |OUT|

There are 2 iterations of LOOP0, new iterations start every clock cycle, the output is produced at the end of the last iteration: this implies that the RTL generated with these constraints will produce new results every 2 cycles.

An important point to notice as well is that the throughput of the design is independent of its latency. The above examples were drawn with the assumption that each addition took a full clock cycle. One loop iteration is shown to take 3 clock cycles. Faster adders could have produced a shorter schedule. This would have meant a shorter ramp-up time (time to first output), but the data rate would stay the same (1 output every 2 clock cycles).

So answer 1 is not the correct one. There are only two possible choices left, and I hope that with all these recent explanations, finding the solution should now be easy…

Tags: ANSI C++, Bluebook, C synthesis, high-level synthesis, HLS, How-to, Learning, Loop, Pipelining, Unrolling

HLS Fundamentals: Loop Unrolling and Loop Pipelining

The dust has settled and four winners have emerged from the HLS Bluebook contest, and this week, as promised, I will discuss the question that proved to be the most challenging in third and final round of the contest.

The culprit was the following question, which only 15% of the contenders answered correctly:

HLS Contest - Round 3, Question 1

What this simple C code does is: reading 8 input values (din), summing them in an intermediate variable (tmp) and returning the final results (dout).

Before going over the various answers and explaining the correct one, let’s review two important concepts covered in this question:

• Loop pipelining provides a way to increase the throughput of a loop by initiating the (i+1)th iteration of the loop before the ith iteration has completed. Overlapping the execution of subsequent iterations of a loop exploits parallelism across loop iterations. The number of cycles between iterations of the loop is called the “Initiation Interval” (II).
• Loop unrolling provides a way be used to reduce the latency of a loop by reducing the number of its iterations. When a loop is unrolled – either fully or partially – the loop body is duplicated as many times as the loop is unrolled. This exposes parallelism that exists across subsequent iterations of the loop. The number of times a loop is unrolled is called the “Unroll Factor”.

If these definitions sound a bit theoretical, the following explanations and charts should help make them clearer. And an earlier blog post on this topic is still available here for reference.

• Default behavior

Assuming that the accumulation takes one clock cycle, a single iteration of LOOP0 would look as follows:

|RDi|ACC|

This notation indicates that in the first cycle an input is read and in the second cycle, the data is accumulated.

If not special synthesis contraints are applied to this design, loops either unrolled or pipelined. This means that the next loop iteration will start right after the previous loop iteration completes. In this case the schedule of the design would look like as follows:

|RD0|ACC|RD1|ACC|RD2|ACC|RD3|ACC|RD4|ACC|RD5|ACC|RD6|ACC|RD7|ACC|

In other words, a very serial design is built where in first cycle din[0] is read, in the second cycle the data is accumulated, in the third cycle din[1] is read, etc… In this case, the output would come out every 16 cycles.

•  Analysis of Answer #2

Let’s now see what happens in the case of answer 2, when we leave LOOP0 rolled and pipeline the design with II=3.

As in the default case, the loop is kept rolled, therefore one iteration would look like this:

|RDi|ACC|

But now we pipeline the design with II=3, implying that we are building a design were each new iteration of LOOP0 starts 3 cycles after the beginning of the previous iteration.

|RD0|ACC|   |           |           |           |           |           |           |           |

|           |RD1|ACC|   |           |           |           |           |           |           |

|           |           |RD2|ACC|   |           |           |           |           |           |

|           |           |           |RD3|ACC|   |           |           |           |           |

|           |           |           |           |RD4|ACC|   |           |           |           |

|           |           |           |           |           |RD5|ACC|   |           |           |

|           |           |           |           |           |           |RD6|ACC|   |           |

|           |           |           |           |           |           |           |RD7|ACC|   |

|<-3cycles->|           |           |           |           |           |           |           |

Consequently, the next design iteration (to process a new set of inputs) would start 3 cycles after the start of the last LOOP0 iteration. There are 8 iterations of LOOP0 and each iteration starts every 3 clock cycles: this implies that the design processes new inputs and produces a new result every 24 cycles.

So answer 2 is not the correct one. Have you found the correct answer yet? In my next blog post, I’ll explain what happens when you start unrolling loops.

Tags: ANSI C++, Bluebook, C synthesis, high-level synthesis, HLS, How-to, Learning, Loop, Pipelining, Unrolling