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

Rinse Wester

    Research output: ThesisPhD Thesis - Research UT, graduation UT

    573 Downloads (Pure)


    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.
    Original languageUndefined
    Awarding Institution
    • University of Twente
    • Smit, Gerardus Johannes Maria, Supervisor
    • Kuper, Jan , Supervisor
    Thesis sponsors
    Award date3 Jul 2015
    Place of PublicationEnschede
    Print ISBNs978-90-365-3887-9
    Publication statusPublished - 3 Jul 2015


    • Higher-order functions
    • EWI-26125
    • IR-96278
    • METIS-310874
    • transformations
    • Hardware design

    Cite this