N queens on an fpga: mathematics,programming, or both?

Jan Kuper, Rinse Wester

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

This paper presents a design methodology for deriving an FPGA implementation directly from a mathematical specification, thus avoiding the switch in semantic perspective as is present in widely applied methods which include an imperative implementation as an intermediate step. The first step in the method presented in this paper is to transform a mathematical specification into a Haskell program. The next step is to make repetition structures explicit by higher order functions, and after that rewrite the specification in the form of a Mealy Machine. Finally, adaptations have to be made in order to comply to the fixed nature of hardware. The result is then given to CaSH, a compiler which generates synthesizable VHDL from the resulting Haskell code. An advantage of the approach presented here is that in all phases of the process the design can be directly simulated by executing the defining code in a standard Haskell environment. To illustrate the design process, the N queens problem is chosen as a running example.
LanguageUndefined
Title of host publicationCommunicating Processes Architectures 2014
PublisherOpen Channel Publishing Ltd
Pages181-203
Number of pages23
ISBN (Print)978-0-9565409-8-0
StatePublished - 2014
EventCommunicating Process Architectures, CPA 2014 - University of Oxford, Oxford, United Kingdom
Duration: 24 Aug 201427 Aug 2014
Conference number: 36
http://www.wotug.org/cpa2014/

Publication series

Name
PublisherOpen Channel Publishing Ltd

Conference

ConferenceCommunicating Process Architectures, CPA 2014
Abbreviated titleCPA
CountryUnited Kingdom
CityOxford
Period24/08/1427/08/14
Internet address

Keywords

  • EC Grant Agreement nr.: FP7/610686
  • EWI-25851
  • CAES-EEA: Efficient Embedded Architectures
  • METIS-309934
  • FPGA Design
  • IR-94663
  • CλaSH
  • Model-based design

Cite this

Kuper, J., & Wester, R. (2014). N queens on an fpga: mathematics,programming, or both? In Communicating Processes Architectures 2014 (pp. 181-203). Open Channel Publishing Ltd.
Kuper, Jan ; Wester, Rinse. / N queens on an fpga: mathematics,programming, or both?. Communicating Processes Architectures 2014. Open Channel Publishing Ltd, 2014. pp. 181-203
@inproceedings{85e6e73710864e678c5b44469800b83f,
title = "N queens on an fpga: mathematics,programming, or both?",
abstract = "This paper presents a design methodology for deriving an FPGA implementation directly from a mathematical specification, thus avoiding the switch in semantic perspective as is present in widely applied methods which include an imperative implementation as an intermediate step. The first step in the method presented in this paper is to transform a mathematical specification into a Haskell program. The next step is to make repetition structures explicit by higher order functions, and after that rewrite the specification in the form of a Mealy Machine. Finally, adaptations have to be made in order to comply to the fixed nature of hardware. The result is then given to CaSH, a compiler which generates synthesizable VHDL from the resulting Haskell code. An advantage of the approach presented here is that in all phases of the process the design can be directly simulated by executing the defining code in a standard Haskell environment. To illustrate the design process, the N queens problem is chosen as a running example.",
keywords = "EC Grant Agreement nr.: FP7/610686, EWI-25851, CAES-EEA: Efficient Embedded Architectures, METIS-309934, FPGA Design, IR-94663, CλaSH, Model-based design",
author = "Jan Kuper and Rinse Wester",
note = "http://wotug.org/cpa2014/",
year = "2014",
language = "Undefined",
isbn = "978-0-9565409-8-0",
publisher = "Open Channel Publishing Ltd",
pages = "181--203",
booktitle = "Communicating Processes Architectures 2014",

}

Kuper, J & Wester, R 2014, N queens on an fpga: mathematics,programming, or both? in Communicating Processes Architectures 2014. Open Channel Publishing Ltd, pp. 181-203, Communicating Process Architectures, CPA 2014, Oxford, United Kingdom, 24/08/14.

N queens on an fpga: mathematics,programming, or both? / Kuper, Jan; Wester, Rinse.

Communicating Processes Architectures 2014. Open Channel Publishing Ltd, 2014. p. 181-203.

Research output: Chapter in Book/Report/Conference proceedingConference contribution

TY - GEN

T1 - N queens on an fpga: mathematics,programming, or both?

AU - Kuper,Jan

AU - Wester,Rinse

N1 - http://wotug.org/cpa2014/

PY - 2014

Y1 - 2014

N2 - This paper presents a design methodology for deriving an FPGA implementation directly from a mathematical specification, thus avoiding the switch in semantic perspective as is present in widely applied methods which include an imperative implementation as an intermediate step. The first step in the method presented in this paper is to transform a mathematical specification into a Haskell program. The next step is to make repetition structures explicit by higher order functions, and after that rewrite the specification in the form of a Mealy Machine. Finally, adaptations have to be made in order to comply to the fixed nature of hardware. The result is then given to CaSH, a compiler which generates synthesizable VHDL from the resulting Haskell code. An advantage of the approach presented here is that in all phases of the process the design can be directly simulated by executing the defining code in a standard Haskell environment. To illustrate the design process, the N queens problem is chosen as a running example.

AB - This paper presents a design methodology for deriving an FPGA implementation directly from a mathematical specification, thus avoiding the switch in semantic perspective as is present in widely applied methods which include an imperative implementation as an intermediate step. The first step in the method presented in this paper is to transform a mathematical specification into a Haskell program. The next step is to make repetition structures explicit by higher order functions, and after that rewrite the specification in the form of a Mealy Machine. Finally, adaptations have to be made in order to comply to the fixed nature of hardware. The result is then given to CaSH, a compiler which generates synthesizable VHDL from the resulting Haskell code. An advantage of the approach presented here is that in all phases of the process the design can be directly simulated by executing the defining code in a standard Haskell environment. To illustrate the design process, the N queens problem is chosen as a running example.

KW - EC Grant Agreement nr.: FP7/610686

KW - EWI-25851

KW - CAES-EEA: Efficient Embedded Architectures

KW - METIS-309934

KW - FPGA Design

KW - IR-94663

KW - CλaSH

KW - Model-based design

M3 - Conference contribution

SN - 978-0-9565409-8-0

SP - 181

EP - 203

BT - Communicating Processes Architectures 2014

PB - Open Channel Publishing Ltd

ER -

Kuper J, Wester R. N queens on an fpga: mathematics,programming, or both? In Communicating Processes Architectures 2014. Open Channel Publishing Ltd. 2014. p. 181-203.