From loop transformation to hardware generation

Multimedia applications are examples of a class of algorithms that are both calculation and data intensive and have real-time requirements. As a result dedicated hardware acceleration is often needed. Usually the on-chip memory is not sufficient to store all data and has to be extended with external memory. The bandwidth to this memory often becomes a bottle neck. Loop transformations are needed to reduce this bandwidth, by improving the temporal and spatial data locality. They can also unveil the parallelism present in the algorithm. The polyhedral model offers a flexible program representation that allows to automate this kind of transformations. The class of applications that can be transformed with the polyhedral model fits very well into the class of applications that can benefit from hardware acceleration. This paper describes how the existing tools, that generate software from a polyhedral program representation, have been extended to generate a VHDL description of a hardware controller. The corresponding data path is generated semi-automatically. Combining the generation of controller and data path creates a fast path to hardware. Our techniques enable an easy exploration of the design space, by generating a lot of implementation variants. The techniques are demonstrated on an inverse discrete wavelet transform resulting in several synthesizable designs, of which one has been hand-optimized towards a FPGA implementation. The results outperform those of a commercial C-to-VHDL compiler. The generated variants run 5 to 10 times faster while consuming less resources