Parametric polyhedral optimisation for high-level synthesis

High-level synthesis (HLS) improves hardware design productivity by using high-level programming languages for design entry. Although various automatic optimisations have been supported in modern HLS tools, manual effort is still required to achieve sufficient hardware acceleration. Loop pipelining is one of the most important opti- mization methods in HLS for increasing loop parallelism. In this thesis, we extend the capability of loop pipelining in HLS to handle loops with uncertain dependencies (i.e., parameterised by an undetermined variable) and/or non-uniform dependencies (i.e., varying between loop iterations). Our optimisations allow a pipeline to be scheduled without the aforementioned memory dependencies at compile time, but an associated controller will change the execution speed of loop iterations at runtime. A parametric polyhedral analysis is developed to generate the control logic and is integrated in an automated source-to-source code transformation framework. Experiments over a suite of benchmarks show that transformed pipelines can achieve 3.7-11× faster acceleration with a reasonable resource overhead. To tackle the challenge of memory and communication bottlenecks, we have also developed a tile size selection for loop tiling to improve data locality. The size of the tiles, which can significantly affect the memory requirement, is usually determined by partial enumeration. We propose an analytical methodology in this thesis to automate the selection of a tile size for optimised memory reuse in HLS. A new parametric polyhedral analysis for memory mapping is introduced to capture memory usage analytically for arbitrary tile sizes. To determine the tile size for data reuse in constrained on-chip memory, an algorithm is then developed to optimize over this model, using non-linear solvers to minimize communication overhead. We show experimentally that our tile size selection can quickly produce high-quality solutions associated with an efficient memory mapping.Open Acces