Abstract
Original language  Undefined 

Awarding Institution 

Supervisors/Advisors 

Sponsors  
Date of Award  3 Jul 2015 
Place of Publication  Enschede 
Publisher  
Print ISBNs  9789036538879 
DOIs  
State  Published  3 Jul 2015 
Fingerprint
Keywords
 Higherorder functions
 EWI26125
 IR96278
 METIS310874
 transformations
 Hardware design
Cite this
}
A transformationbased approach to hardware design using higherorder functions. / Wester, Rinse.
Enschede : Universiteit Twente, 2015. 136 p.Research output: Scientific › PhD Thesis  Research UT, graduation UT
TY  THES
T1  A transformationbased approach to hardware design using higherorder functions
AU  Wester,Rinse
PY  2015/7/3
Y1  2015/7/3
N2  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 highlevel languages to hardware have been developed based on imperative languages like C. Parallelism is achieved by parallelization of forloops. 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 higherorder functions, an abstraction commonly used in functional programming languages. The main contribution of this thesis is a design methodology based on exploiting regularity of higherorder functions. A mathematical formula, e.g., a DSP algorithm, is first formulated using higherorder functions. Then, transformation rules are applied to these higherorder functions to distribute computations over space and time. Using these transformations, an optimal tradeoff 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 higherorder functions and prove that the transformations are meaningpreserving. 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 onedimensional higherorder functions and twodimensional higher order functions have been derived and applied to several case studies: a dot product, a particle filter and stencil computations.
AB  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 highlevel languages to hardware have been developed based on imperative languages like C. Parallelism is achieved by parallelization of forloops. 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 higherorder functions, an abstraction commonly used in functional programming languages. The main contribution of this thesis is a design methodology based on exploiting regularity of higherorder functions. A mathematical formula, e.g., a DSP algorithm, is first formulated using higherorder functions. Then, transformation rules are applied to these higherorder functions to distribute computations over space and time. Using these transformations, an optimal tradeoff 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 higherorder functions and prove that the transformations are meaningpreserving. 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 onedimensional higherorder functions and twodimensional higher order functions have been derived and applied to several case studies: a dot product, a particle filter and stencil computations.
KW  Higherorder functions
KW  EWI26125
KW  IR96278
KW  METIS310874
KW  transformations
KW  Hardware design
U2  10.3990/1.9789036538879
DO  10.3990/1.9789036538879
M3  PhD Thesis  Research UT, graduation UT
SN  9789036538879
PB  Universiteit Twente
ER 