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

Jan Kuper, Rinse Wester

    Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

    341 Downloads (Pure)

    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.
    Original languageUndefined
    Title of host publicationCommunicating Processes Architectures 2014
    PublisherOpen Channel Publishing Ltd
    Pages181-203
    Number of pages23
    ISBN (Print)978-0-9565409-8-0
    Publication statusPublished - 2014
    EventCommunicating Process Architectures, CPA 2014: 36th WoTUG Conference on Concurrent and Parallel Programming 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