Loop shifting and compaction for the high-level synthesis of designs with complex control flow
Sumit Kumar Gupta, Nikil D. Dutt, Rajesh K. Gupta, Alexandru Eugen Nicolau · 2004
Emerging embedded system applications in multimedia and image processing are characterized by complex control flow consisting of deeply nested conditionals and loops. Effective hardware generation using high-level synthesis tools for these applications requires the ability to move code across condition and loop boundaries and exploit the algorithmic parallelism. Traditional loop transformations such as loop unrolling and loop pipelining have been shown to be effective only in the presence of substantive resource allocation. In case of high level synthesis, it has been shown earlier that straightforward exposition of maximum parallelism does not yield the highest performance designs, due to the control and multiplexing overheads. In this paper, we present a technique that implicitly and incrementally exploits loop level parallelism across iterations 2aa by shifting and compacting operations across loop iterations. We demonstrate the effectiveness of this technique, even under tight resource constraints, in terms of circuit performance, controller size and total size of the design. We have implemented loop shifting within a parallelizing high-level synthesis system, Spark. We achieve improvements of up to 20 % in input-to-output delay in the synthesized circuit for experiments on designs derived from two moderately complex industrial-strength applications, MPEG-1 and the GIMP image processing tool.