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

Rinse Wester

Abstract

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
Supervisors/Advisors
  • Smit, Gerardus Johannes Maria, Supervisor
  • Kuper, Jan , Supervisor
Sponsors
Date of Award3 Jul 2015
Place of PublicationEnschede
Publisher
Print ISBNs978-90-365-3887-9
DOIs
StatePublished - 3 Jul 2015

Fingerprint

Computer hardware description languages
Hardware
Reconfigurable architectures
Functional programming
Logic devices
High level languages
Random access storage
Computer programming
Computer programming languages
Field programmable gate arrays (FPGA)
Productivity

Keywords

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

Cite this

Wester, Rinse. / A transformation-based approach to hardware design using higher-order functions. Enschede : Universiteit Twente, 2015. 136 p.
@misc{83f0dbb9c625476ab035d744754ae20b,
title = "A transformation-based approach to hardware design using higher-order functions",
abstract = "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.",
keywords = "Higher-order functions, EWI-26125, IR-96278, METIS-310874, transformations, Hardware design",
author = "Rinse Wester",
year = "2015",
month = "7",
doi = "10.3990/1.9789036538879",
isbn = "978-90-365-3887-9",
publisher = "Universiteit Twente",
school = "University of Twente",

}

A transformation-based approach to hardware design using higher-order functions. / Wester, Rinse.

Enschede : Universiteit Twente, 2015. 136 p.

Research output: ScientificPhD Thesis - Research UT, graduation UT

TY - THES

T1 - A transformation-based approach to hardware design using higher-order 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 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.

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 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.

KW - Higher-order functions

KW - EWI-26125

KW - IR-96278

KW - METIS-310874

KW - transformations

KW - Hardware design

U2 - 10.3990/1.9789036538879

DO - 10.3990/1.9789036538879

M3 - PhD Thesis - Research UT, graduation UT

SN - 978-90-365-3887-9

PB - Universiteit Twente

ER -

Wester R. A transformation-based approach to hardware design using higher-order functions. Enschede: Universiteit Twente, 2015. 136 p. Available from, DOI: 10.3990/1.9789036538879