A transformation-based approach to hardware design using higher-order functions

The amount of resources available on reconfigurable logic devices like FPGAs has seen a tremendous growth over the last thirty years. During this period, the amount of programmable resources (CLBs and RAMs) has increased by more than three orders of magnitude. Programming these reconfigurable architectures has been dominated by the hardware description languages VHDL and Verilog. However, it has become generally accepted that these languages do not provide adequate abstraction mechanisms to deliver the design productivity for designing more and more complex applications. To raise the abstraction level, techniques to translate high-level languages to hardware have been developed based on imperative languages like C. Parallelism is achieved by parallelization of for-loops. Whether parallelization of loops is possible, is determined using dependency analysis which is a very hard problem. To mitigate this problem, other abstractions are needed to express parallelism. In this thesis, parallelism is expressed using higher-order functions, an abstraction commonly used in functional programming languages. The main contribution of this thesis is a design methodology based on exploiting regularity of higher-order functions. A mathematical formula, e.g., a DSP algorithm, is first formulated using higher-order functions. Then, transformation rules are applied to these higher-order functions to distribute computations over space and time. Using these transformations, an optimal trade-off can be made between space and time. Finally, hardware is generated using the CLaSH compiler by translating the result of the transformation to VHDL. In this thesis, we derive transformation rules for several higher-order functions and prove that the transformations are meaning-preserving. After transformation, a mathematically equivalent description is derived in which the computations are distributed over space and time. The designer can control the amount of parallelism using a parameter that is introduced by the transformation. Transformation rules for both one-dimensional higher-order functions and two-dimensional higher- order functions have been derived and applied to several case studies: a dot product, a particle filter and stencil computations.