X-Git-Url: https://git.stderr.nl/gitweb?p=matthijs%2Fmaster-project%2Fdsd-paper.git;a=blobdiff_plain;f=c%CE%BBash.lhs;h=12ab1d968c9161f821c1cb8c3be4b4128eb52e3b;hp=643d41ca6b670e358d3b5c8a36d23ae9923f723a;hb=9b3fa71d1966be5a8b2ef467c64c3405bece1434;hpb=b70320599df1351798d1d726614b2203db6e882e diff --git "a/c\316\273ash.lhs" "b/c\316\273ash.lhs" index 643d41c..12ab1d9 100644 --- "a/c\316\273ash.lhs" +++ "b/c\316\273ash.lhs" @@ -65,6 +65,7 @@ % \documentclass[conference,pdf,a4paper,10pt,final,twoside,twocolumn]{IEEEtran} +\IEEEoverridecommandlockouts % Add the compsoc option for Computer Society conferences. % % If IEEEtran.cls has not been installed into the LaTeX system files, @@ -342,9 +343,12 @@ % Macro for certain acronyms in small caps. Doesn't work with the % default font, though (it contains no smallcaps it seems). \def\acro#1{{\small{#1}}} +\def\acrop#1{\acro{#1}s} +\def\acrotiny#1{{\scriptsize{#1}}} \def\VHDL{\acro{VHDL}} \def\GHC{\acro{GHC}} \def\CLaSH{{\small{C}}$\lambda$a{\small{SH}}} +\def\CLaSHtiny{{\scriptsize{C}}$\lambda$a{\scriptsize{SH}}} % Macro for pretty printing haskell snippets. Just monospaced for now, perhaps % we'll get something more complex later on. @@ -375,10 +379,26 @@ \newcommand{\fref}[1]{\cref{#1}} \newcommand{\Fref}[1]{\Cref{#1}} +\usepackage{epstopdf} + +\epstopdfDeclareGraphicsRule{.svg}{pdf}{.pdf}{rsvg-convert --format=pdf < #1 > \noexpand\OutputFile} %include polycode.fmt %include clash.fmt +\newcounter{Codecount} +\setcounter{Codecount}{0} + +\newenvironment{example} + { + \refstepcounter{equation} + } + { + \begin{flushright} + (\arabic{equation}) + \end{flushright} + } + \begin{document} % % paper title @@ -389,10 +409,13 @@ % author names and affiliations % use a multiple column layout for up to three different % affiliations -\author{\IEEEauthorblockN{Christiaan P.R. Baaij, Matthijs Kooijman, Jan Kuper, Marco E.T. Gerards, Bert Molenkamp, Sabih H. Gerez} -\IEEEauthorblockA{University of Twente, Department of EEMCS\\ +\author{\IEEEauthorblockN{Matthijs Kooijman, Christiaan P.R. Baaij, Jan Kuper, Marco E.T. Gerards}%, Bert Molenkamp, Sabih H. Gerez} +\IEEEauthorblockA{%Computer Architecture for Embedded Systems (CAES)\\ +Department of EEMCS, University of Twente\\ P.O. Box 217, 7500 AE, Enschede, The Netherlands\\ -c.p.r.baaij@@utwente.nl, matthijs@@stdin.nl, j.kuper@@utwente.nl}} +matthijs@@stdin.nl, c.p.r.baaij@@utwente.nl, j.kuper@@utwente.nl} +% \thanks{Supported through the FP7 project: S(o)OS (248465)} +} % \and % \IEEEauthorblockN{Homer Simpson} % \IEEEauthorblockA{Twentieth Century Fox\\ @@ -439,10 +462,24 @@ c.p.r.baaij@@utwente.nl, matthijs@@stdin.nl, j.kuper@@utwente.nl}} % make the title area \maketitle - \begin{abstract} %\boldmath -The abstract goes here. +\CLaSH\ is a functional hardware description language that borrows both its +syntax and semantics from the functional programming language Haskell. +Polymorphism and higher-order functions provide a level of abstraction and +generality that allow a circuit designer to describe circuits in a more +natural way than possible in a traditional hardware description language. + +Circuit descriptions can be translated to synthesizable VHDL using the +prototype \CLaSH\ compiler. As the circuit descriptions, simulation code, and +test input are also valid Haskell, complete simulations can be compiled as an +executable binary by a Haskell compiler allowing high-speed simulation and +analysis. + +% \CLaSH\ supports stateful descriptions by explicitly making the current +% state an argument of the function, and the updated state part of the result. +% This makes \CLaSH\ descriptions in essence the combinational parts of a +% mealy machine. \end{abstract} % IEEEtran.cls defaults to using nonbold math in the Abstract. % This preserves the distinction between vectors and scalars. However, @@ -466,71 +503,91 @@ The abstract goes here. % creates the second title. It will be ignored for other modes. \IEEEpeerreviewmaketitle - \section{Introduction} -Hardware description languages has allowed the productivity of hardware -engineers to keep pace with the development of chip technology. Standard -Hardware description languages, like \VHDL~\cite{VHDL2008} and +Hardware description languages (\acrop{HDL}) have allowed the productivity of +hardware engineers to keep pace with the development of chip technology. +Traditional \acrop{HDL}, like \VHDL~\cite{VHDL2008} and Verilog~\cite{Verilog}, allowed an engineer to describe circuits using a -programming language. These standard languages are very good at describing +`programming' language. These standard languages are very good at describing detailed hardware properties such as timing behavior, but are generally cumbersome in expressing higher-level abstractions. In an attempt to raise the abstraction level of the descriptions, a great number of approaches based on -functional languages has been proposed \cite{T-Ruby,Hydra,HML2,Hawk1,Lava, -ForSyDe1,Wired,reFLect}. The idea of using functional languages for hardware -descriptions started in the early 1980s \cite{Cardelli1981, muFP,DAISY,FHDL}, -a time which also saw the birth of the currently popular hardware description -languages such as \VHDL. The merit of using a functional language to describe -hardware comes from the fact that combinatorial circuits can be directly -modeled as mathematical functions and that functional languages are very good -at describing and composing mathematical functions. - -In an attempt to decrease the amount of work involved with creating all the -required tooling, such as parsers and type-checkers, many functional hardware -description languages are embedded as a domain specific language inside the -functional language Haskell \cite{Hydra,Hawk1,Lava,ForSyDe1,Wired}. This -means that a developer is given a library of Haskell~\cite{Haskell} functions -and types that together form the language primitives of the domain specific -language. As a result of how the signals are modeled and abstracted, the -functions used to describe a circuit also build a large domain-specific -datatype (hidden from the designer) which can be further processed by an -embedded compiler. This compiler actually runs in the same environment as the -description; as a result compile-time and run-time become hard to define, as -the embedded compiler is usually compiled by the same Haskell compiler as the -circuit description itself. - -The approach taken in this research is not to make another domain specific -language embedded in Haskell, but to use (a subset of) the Haskell language -itself for the purpose of describing hardware. By taking this approach, we can -capture certain language constructs, such as Haskell's choice elements -(if-constructs, case-constructs, pattern matching, etc.), which are not -available in the functional hardware description languages that are embedded -in Haskell as a domain specific languages. As far as the authors know, such -extensive support for choice-elements is new in the domain of functional -hardware description languages. As the hardware descriptions are plain Haskell -functions, these descriptions can be compiled for simulation using an -optimizing Haskell compiler such as the Glasgow Haskell Compiler (\GHC). - -Where descriptions in a conventional hardware description language have an -explicit clock for the purpose state and synchronicity, the clock is implied -in this research. A developer describes the behavior of the hardware between -clock cycles, as such, only synchronous systems can be described. Many -functional hardware description model signals as a stream of all values over -time; state is then modeled as a delay on this stream of values. The approach -taken in this research is to make the current state of a circuit part of the -input of the function and the updated state part of the output. - -Like the standard hardware description languages, descriptions made in a -functional hardware description language must eventually be converted into a -netlist. This research also features a prototype translator called \CLaSH\ -(pronounced: clash), which converts the Haskell code to equivalently behaving -synthesizable \VHDL\ code, ready to be converted to an actual netlist format -by any (optimizing) \VHDL\ synthesis tool. +functional languages has been proposed \cite{Cardelli1981,muFP,DAISY, +T-Ruby,HML2,Hydra,Hawk1,Lava,Wired,ForSyDe1,reFLect}. The idea of using +functional languages for hardware descriptions started in the early 1980s +\cite{Cardelli1981,muFP,DAISY}, a time which also saw the birth of the +currently popular hardware description languages, such as \VHDL. Functional +languages are especially well suited to describe hardware because +combinational circuits can be directly modeled as mathematical functions and +functional languages are very good at describing and composing these +mathematical functions. + +In an attempt to decrease the amount of work involved in creating all the +required tooling, such as parsers and type-checkers, many functional +\acrop{HDL} \cite{Hydra,Hawk1,Lava,Wired} are embedded as a domain +specific language (\acro{DSL}) within the functional language Haskell +\cite{Haskell}. This means that a developer is given a library of Haskell +functions and types that together form the language primitives of the +\acro{DSL}. The primitive functions used to describe a circuit do not actually +process any signals, they instead compose a large domain-specific datatype +(which is usually hidden from the designer). This datatype is then further +processed by an embedded circuit compiler which can perform for example +simulation or synthesis. As Haskell's choice elements (\hs{if}-expressions, +\hs{case}-expressions, etc.) are evaluated at the time the domain-specific +datatype is being build, they are no longer visible to the embedded compiler +that processes the datatype. Consequently, it is impossible the capture +Haskell's choice elements within a circuit description when taking the +embedded language approach. This does not mean that circuits specified in an +embedded language can not contain choice, just that choice elements only +exists as functions, e.g. a multiplexer function, and not as language +elements. + +The approach taken in this research is not to make another \acro{DSL} embedded +in Haskell, but to use (a subset of) the Haskell language \emph{itself} for +the purpose of describing hardware. By taking this approach, this research +\emph{can} capture certain language constructs, such as Haskell's choice +elements, within circuit descriptions. To the best knowledge of the authors, +supporting polymorphism, higher-order functions and such an extensive array of +choice-elements is new in the domain of (functional) \acrop{HDL}. +% As the hardware descriptions are plain Haskell +% functions, these descriptions can be compiled to an executable binary +% for simulation using an optimizing Haskell compiler such as the Glasgow +% Haskell Compiler (\GHC)~\cite{ghc}. + +Where descriptions in a conventional \acro{HDL} have an explicit clock for the +purposes state and synchronicity, the clock is implied in the context of the +research presented in this paper. A circuit designer describes the behavior of +the hardware between clock cycles. Many functional \acrop{HDL} model signals +as a stream of all values over time; state is then modeled as a delay on this +stream of values. The approach taken in this research is to make the current +state an additional input and the updated state a part of the output of a +function. This abstraction of state and time limits the descriptions to +synchronous hardware, there is however room within the language to eventually +add a different abstraction mechanism that will allow for the modeling of +asynchronous systems. + +Like the traditional \acrop{HDL}, descriptions made in a functional \acro{HDL} +must eventually be converted into a netlist. This research also features a +prototype translator, which has the same name as the language: +\CLaSH\footnote{\CLaSHtiny: \acrotiny{CAES} Language for Synchronous Hardware} +(pronounced: clash). This compiler converts the Haskell code to equivalently +behaving synthesizable \VHDL\ code, ready to be converted to an actual netlist +format by an (optimizing) \VHDL\ synthesis tool. + +Besides trivial circuits such as variants of both the \acro{FIR} filter and +the simple \acro{CPU} shown in \Cref{sec:usecases}, the \CLaSH\ compiler has +also been able to successfully translate non-trivial functional descriptions +such as a streaming reduction circuit~\cite{reductioncircuit} for floating +point numbers. \section{Hardware description in Haskell} +The following section describes the basic language elements of \CLaSH\ and the +extensiveness of the support of these elements within the \CLaSH\ compiler. In +various subsections, the relation between the language elements and their +eventual netlist representation is also highlighted. \subsection{Function application} - The basic syntactic elements of a functional program are functions + Two basic syntactic elements of a functional program are functions and function application. These have a single obvious translation to a netlist format: \begin{inparaenum} @@ -540,107 +597,176 @@ by any (optimizing) \VHDL\ synthesis tool. and \item function applications are translated to component instantiations. \end{inparaenum} - The output port can have a complex type (such as a tuple), so having just - a single output port does not pose any limitation. The arguments of a - function applications are assigned to a signal, which are then mapped to - the corresponding input ports of the component. The output port of the - function is also mapped to a signal, which is used as the result of the - application itself. - - Since every top level function generates its own component, the - hierarchy of function calls is reflected in the final netlist,% aswell, - creating a hierarchical description of the hardware. This separation in - different components makes the resulting \VHDL\ output easier to read and - debug. - - As an example we can see the netlist of the |mac| function in - \Cref{img:mac-comb}; the |mac| function applies both the |mul| and |add| - function to calculate $a * b + c$: + The result value can have a composite type (such as a tuple), so having + just a single result value does not pose any limitation. The actual + arguments of a function application are assigned to signals, which are + then mapped to the corresponding input ports of the component. The output + port of the function is also mapped to a signal, which is used as the + result of the application itself. Since every top level function generates + its own component, the hierarchy of function calls is reflected in the + final netlist. %, creating a hierarchical description of the hardware. + % The separation in different components makes it easier for a developer + % to understand and possibly hand-optimize the resulting \VHDL\ output of + % the \CLaSH\ compiler. + + The short example (\ref{lst:code1}) demonstrated below gives an indication + of the level of conciseness that can be achieved with functional hardware + description languages when compared with the more traditional hardware + description languages. The example is a combinational multiply-accumulate + circuit that works for \emph{any} word length (this type of polymorphism + will be further elaborated in \Cref{sec:polymorhpism}). The corresponding + netlist is depicted in \Cref{img:mac-comb}. + \hspace{-1.7em} + \begin{minipage}{0.93\linewidth} \begin{code} mac a b c = add (mul a b) c \end{code} + \end{minipage} + \begin{minipage}{0.07\linewidth} + \begin{example} + \label{lst:code1} + \end{example} + \end{minipage} \begin{figure} - \centerline{\includegraphics{mac}} - \caption{Combinatorial Multiply-Accumulate} + \centerline{\includegraphics{mac.svg}} + \caption{Combinational Multiply-Accumulate} \label{img:mac-comb} + \vspace{-1.5em} \end{figure} - The result of using a complex input type can be seen in - \cref{img:mac-comb-nocurry} where the |mac| function now uses a single - input tuple for the |a|, |b|, and |c| arguments: + The use of a composite result value is demonstrated in the next example + (\ref{lst:code2}), where the multiply-accumulate circuit not only returns + the accumulation result, but also the intermediate multiplication result. + Its corresponding netlist can be seen in \Cref{img:mac-comb-composite}. + \hspace{-1.7em} + \begin{minipage}{0.93\linewidth} \begin{code} - mac (a, b, c) = add (mul a b) c + mac a b c = (z, add z c) + where + z = mul a b \end{code} + \end{minipage} + \begin{minipage}{0.07\linewidth} + \begin{example} + \label{lst:code2} + \end{example} + \end{minipage} \begin{figure} - \centerline{\includegraphics{mac-nocurry}} - \caption{Combinatorial Multiply-Accumulate (complex input)} - \label{img:mac-comb-nocurry} + \centerline{\includegraphics{mac-nocurry.svg}} + \caption{Combinational Multiply-Accumulate (composite output)} + \label{img:mac-comb-composite} + \vspace{-1.5em} \end{figure} \subsection{Choice} - In Haskell, choice can be achieved by a large set of language constructs, - consisting of: \hs{case} constructs, \hs{if-then-else} constructs, - pattern matching, and guards. The easiest of these are the \hs{case} - constructs (\hs{if} expressions can be very directly translated to - \hs{case} expressions). A \hs{case} construct is translated to a - multiplexer, where the control value is linked to the selection port and - the output of each case is linked to the corresponding input port on the - multiplexer. + In Haskell, choice can be achieved by a large set of syntactic elements, + consisting of: \hs{case} expressions, \hs{if-then-else} expressions, + pattern matching, and guards. The most general of these are the \hs{case} + expressions (\hs{if} expressions can be directly translated to + \hs{case} expressions). When transforming a \CLaSH\ description to a + netlist, a \hs{case} expression is translated to a multiplexer. The + control value of the \hs{case} expression is fed into a number of + comparators and their combined output forms the selection port of the + multiplexer. The result of each alternative in the \hs{case} expression is + linked to the corresponding input port of the multiplexer. % A \hs{case} expression can in turn simply be translated to a conditional % assignment in \VHDL, where the conditions use equality comparisons % against the constructors in the \hs{case} expressions. - We can see two versions of a contrived example below, the first - using a \hs{case} construct and the other using a \hs{if-then-else} - constructs, in the code below. The example sums two values when they are - equal or non-equal (depending on the predicate given) and returns 0 - otherwise. Both versions of the example roughly correspond to the same - netlist, which is depicted in \Cref{img:choice}. + Two versions of a contrived example are displayed below, the first + (\ref{lst:code3}) using a \hs{case} expression and the second + (\ref{lst:code4}) using an \hs{if-then-else} expression. Both examples + sum two values when they are equal or non-equal (depending on the given + predicate, the \hs{pred} variable) and return 0 otherwise. The \hs{pred} + variable is of the following, user-defined, enumeration datatype: \begin{code} - sumif pred a b = case pred of - Eq -> case a == b of - True -> a + b - False -> 0 - Neq -> case a != b of - True -> a + b - False -> 0 + data Pred = Equal | NotEqual \end{code} + The naive netlist corresponding to both versions of the example is + depicted in \Cref{img:choice}. Note that the \hs{pred} variable is only + compared to \hs{Equal}, as an inequality immediately implies that + \hs{pred} is \hs{NotEqual}. + + \hspace{-1.7em} + \begin{minipage}{0.93\linewidth} + \begin{code} + sumif pred a b = case pred of + Equal -> case a == b of + True -> a + b + False -> 0 + NotEqual -> case a != b of + True -> a + b + False -> 0 + \end{code} + \end{minipage} + \begin{minipage}{0.07\linewidth} + \begin{example} + \label{lst:code3} + \end{example} + \end{minipage} + + \hspace{-1.7em} + \begin{minipage}{0.93\linewidth} \begin{code} sumif pred a b = - if pred == Eq then + if pred == Equal then if a == b then a + b else 0 else if a != b then a + b else 0 \end{code} + \end{minipage} + \begin{minipage}{0.07\linewidth} + \begin{example} + \label{lst:code4} + \end{example} + \end{minipage} \begin{figure} - \centerline{\includegraphics{choice-case}} + \vspace{1em} + \centerline{\includegraphics{choice-case.svg}} \caption{Choice - sumif} \label{img:choice} + \vspace{-1.5em} \end{figure} - A slightly more complex (but very powerful) form of choice is pattern - matching. A function can be defined in multiple clauses, where each clause - specifies a pattern. When the arguments match the pattern, the - corresponding clause will be used. Expressions can also contain guards, - where the expression is only executed if the guard evaluates to true. Like - \hs{if-then-else} constructs, pattern matching and guards have a - (straightforward) translation to \hs{case} constructs and can as such be - mapped to multiplexers. A third version of the earlier example, using both - pattern matching and guards, can be seen below. The version using pattern - matching and guards also has roughly the same netlist representation - (\Cref{img:choice}) as the earlier two versions of the example. + A user-friendly and also very powerful form of choice that is not found in + the traditional hardware description languages is pattern matching. A + function can be defined in multiple clauses, where each clause corresponds + to a pattern. When an argument matches a pattern, the corresponding clause + will be used. Expressions can also contain guards, where the expression is + only executed if the guard evaluates to true, and continues with the next + clause if the guard evaluates to false. Like \hs{if-then-else} + expressions, pattern matching and guards have a (straightforward) + translation to \hs{case} expressions and can as such be mapped to + multiplexers. A third version (\ref{lst:code5}) of the earlier example, + now using both pattern matching and guards, can be seen below. The guard + is the expression that follows the vertical bar (\hs{|}) and precedes the + assignment operator (\hs{=}). The \hs{otherwise} guards always evaluate to + \hs{true}. + + The version using pattern matching and guards corresponds to the same + naive netlist representation (\Cref{img:choice}) as the earlier two + versions of the example. + \hspace{-1.7em} + \begin{minipage}{0.93\linewidth} \begin{code} - sumif Eq a b | a == b = a + b - sumif Neq a b | a != b = a + b - sumif _ _ _ = 0 + sumif Equal a b | a == b = a + b + | otherwise = 0 + sumif NotEqual a b | a != b = a + b + | otherwise = 0 \end{code} + \end{minipage} + \begin{minipage}{0.07\linewidth} + \begin{example} + \label{lst:code5} + \end{example} + \end{minipage} % \begin{figure} % \centerline{\includegraphics{choice-ifthenelse}} @@ -651,15 +777,20 @@ by any (optimizing) \VHDL\ synthesis tool. \subsection{Types} Haskell is a statically-typed language, meaning that the type of a variable or function is determined at compile-time. Not all of Haskell's - typing constructs have a clear translation to hardware, as such this - section will only deal with the types that do have a clear correspondence + typing constructs have a clear translation to hardware, this section will + therefore only deal with the types that do have a clear correspondence to hardware. The translatable types are divided into two categories: \emph{built-in} types and \emph{user-defined} types. Built-in types are - those types for which a direct translation is defined within the \CLaSH\ - compiler; the term user-defined types should not require any further - elaboration. The translatable types are also inferable by the compiler, + those types for which a fixed translation is defined within the \CLaSH\ + compiler. The \CLaSH\ compiler has generic translation rules to + translate the user-defined types, which are described later on. + + The \CLaSH\ compiler is able to infer unspecified (polymorphic) types, meaning that a developer does not have to annotate every function with a - type signature. + type signature. % (even if it is good practice to do so). + Given that the top-level entity of a circuit design is annotated with + concrete/monomorphic types, the \CLaSH\ compiler can specialize + polymorphic functions to functions with concrete types. % Translation of two most basic functional concepts has been % discussed: function application and choice. Before looking further @@ -677,26 +808,26 @@ by any (optimizing) \VHDL\ synthesis tool. % using translation rules that are discussed later on. \subsubsection{Built-in types} - The following types have direct translation defined within the \CLaSH\ + The following types have fixed translations defined within the \CLaSH\ compiler: \begin{xlist} \item[\bf{Bit}] - This is the most basic type available. It can have two values: - \hs{Low} and \hs{High}. + the most basic type available. It can have two values: + \hs{Low} or \hs{High}. % It is mapped directly onto the \texttt{std\_logic} \VHDL\ type. \item[\bf{Bool}] - This is a basic logic type. It can have two values: \hs{True} - and \hs{False}. + this is a basic logic type. It can have two values: \hs{True} + or \hs{False}. % It is translated to \texttt{std\_logic} exactly like the \hs{Bit} % type (where a value of \hs{True} corresponds to a value of % \hs{High}). Supporting the Bool type is required in order to support the - \hs{if-then-else} construct, which requires a \hs{Bool} value for + \hs{if-then-else} expression, which requires a \hs{Bool} value for the condition. - \item[\bf{SizedWord}, \bf{SizedInt}] - These are types to represent integers. A \hs{SizedWord} is unsigned, - while a \hs{SizedInt} is signed. Both are parametrizable in their - size. + \item[\bf{Signed}, \bf{Unsigned}] + these are types to represent integers and both are parametrizable in + their size. The overflow behavior of the numeric operators defined for + these types is \emph{wrap-around}. % , so you can define an unsigned word of 32 bits wide as follows: % \begin{code} @@ -710,12 +841,14 @@ by any (optimizing) \VHDL\ synthesis tool. % types are translated to the \VHDL\ \texttt{unsigned} and % \texttt{signed} respectively. \item[\bf{Vector}] - This is a vector type that can contain elements of any other type and - has a fixed length. The \hs{Vector} type constructor takes two type + this is a vector type that can contain elements of any other type and + has a static length. The \hs{Vector} type constructor takes two type arguments: the length of the vector and the type of the elements contained in it. The short-hand notation used for the vector type in - the rest of paper is: \hs{[a|n]}. Where the \hs{a} is the element - type, and \hs{n} is the length of the vector. + the rest of paper is: \hs{[a|n]}, where \hs{a} is the element + type, and \hs{n} is the length of the vector. Note that this is + a notation used in this paper only, vectors are slightly more + verbose in real \CLaSH\ descriptions. % The state type of an 8 element register bank would then for example % be: @@ -730,12 +863,13 @@ by any (optimizing) \VHDL\ synthesis tool. % \hs{RegisterState} type is a vector of 8 32-bit words. A fixed size % vector is translated to a \VHDL\ array type. \item[\bf{Index}] - This is another type to describe integers, but unlike the previous + this is another type to describe integers, but unlike the previous two it has no specific bit-width, but an upper bound. This means that its range is not limited to powers of two, but can be any number. An \hs{Index} only has an upper bound, its lower bound is - implicitly zero. The main purpose of the \hs{Index} type is to be - used as an index to a \hs{Vector}. + implicitly zero. If a value of this type exceeds either bounds, an + error will be thrown at simulation-time. The main purpose of the + \hs{Index} type is to be used as an index into a \hs{Vector}. % \comment{TODO: Perhaps remove this example?} To define an index for % the 8 element vector above, we would do: @@ -756,26 +890,28 @@ by any (optimizing) \VHDL\ synthesis tool. There are three ways to define new types in Haskell: algebraic data-types with the \hs{data} keyword, type synonyms with the \hs{type} keyword and datatype renaming constructs with the \hs{newtype} keyword. - \GHC\ offers a few more advanced ways to introduce types (type families, - existential typing, {\small{GADT}}s, etc.) which are not standard Haskell. - As it is currently unclear how these advanced type constructs correspond - with hardware, they are for now unsupported by the \CLaSH\ compiler + % \GHC\ offers a few more advanced ways to introduce types (type families, + % existential typing, {\acro{GADT}}s, etc.) which are not standard + % Haskell. As it is currently unclear how these advanced type constructs + % correspond to hardware, they are for now unsupported by the \CLaSH\ + % compiler. Only an algebraic datatype declaration actually introduces a - completely new type. Type synonyms and renaming constructs only define new + completely new type. Type synonyms and type renaming only define new names for existing types, where synonyms are completely interchangeable - and renaming constructs need explicit conversions. Therefore, these do not - need any particular translation, a synonym or renamed type will just use - the same representation as the original type. For algebraic types, we can - make the following distinctions: - + and a type renaming requires an explicit conversion. Type synonyms and + type renaming do not need any particular translation, a synonym or + renamed type will just use the same representation as the original type. + + For algebraic types, we can make the following distinctions: \begin{xlist} \item[\bf{Single constructor}] Algebraic datatypes with a single constructor with one or more fields, are essentially a way to pack a few values together in a record-like structure. Haskell's built-in tuple types are also defined - as single constructor algebraic types An example of a single - constructor type is the following pair of integers: + as single constructor algebraic types (but with a bit of + syntactic sugar). An example of a single constructor type with + multiple fields is the following pair of integers: \begin{code} data IntPair = IntPair Int Int \end{code} @@ -785,9 +921,10 @@ by any (optimizing) \VHDL\ synthesis tool. Algebraic datatypes with multiple constructors, but without any fields are essentially a way to get an enumeration-like type containing alternatives. Note that Haskell's \hs{Bool} type is also - defined as an enumeration type, but we have a fixed translation for - that. An example of such an enum type is the type that represents the - colors in a traffic light: + defined as an enumeration type, but that there is a fixed translation + for that type within the \CLaSH\ compiler. An example of such an + enumeration type is the type that represents the colors in a traffic + light: \begin{code} data TrafficLight = Red | Orange | Green \end{code} @@ -797,19 +934,23 @@ by any (optimizing) \VHDL\ synthesis tool. % value. \item[\bf{Multiple constructors with fields}] Algebraic datatypes with multiple constructors, where at least - one of these constructors has one or more fields are not - currently supported. + one of these constructors has one or more fields are currently not + supported. \end{xlist} - \subsection{Polymorphism} - A powerful construct in most functional languages is polymorphism, it - allows a function to handle values of different data types in a uniform - way. Haskell supports \emph{parametric polymorphism}~\cite{polymorphism}, - meaning functions can be written without mention of any specific type and - can be used transparently with any number of new types. + \subsection{Polymorphism}\label{sec:polymorhpism} + A powerful feature of most (functional) programming languages is + polymorphism, it allows a function to handle values of different data + types in a uniform way. Haskell supports \emph{parametric + polymorphism}~\cite{polymorphism}, meaning functions can be written + without mention of any specific type and can be used transparently with + any number of new types. As an example of a parametric polymorphic function, consider the type of - the following \hs{append} function, which appends an element to a vector: + the following \hs{append} function, which appends an element to a + vector:\footnote{The \hs{::} operator is used to annotate a function + with its type.} + \begin{code} append :: [a|n] -> a -> [a|n + 1] \end{code} @@ -833,121 +974,84 @@ by any (optimizing) \VHDL\ synthesis tool. type classes, where a class definition provides the general interface of a function, and class instances define the functionality for the specific types. An example of such a type class is the \hs{Num} class, which - contains all of Haskell's numerical operation. A developer can make use of - this ad-hoc polymorphism by adding a constraint to a parametrically + contains all of Haskell's numerical operations. A designer can make use + of this ad-hoc polymorphism by adding a constraint to a parametrically polymorphic type variable. Such a constraint indicates that the type variable can only be instantiated to a type whose members supports the overloaded functions associated with the type class. - As an example we will take a look at type signature of the function - \hs{sum}, which sums the values in a vector: + An example of a type signature that includes such a constraint if the + signature of the \hs{sum} function, which sums the values in a vector: \begin{code} sum :: Num a => [a|n] -> a \end{code} This type is again parameterized by \hs{a}, but it can only contain types that are \emph{instances} of the \emph{type class} \hs{Num}, so that - we know that the addition (+) operator is defined for that type. - \CLaSH's built-in numerical types are also instances of the \hs{Num} - class, so we can use the addition operator on \hs{SizedWords} as - well as on \hs{SizedInts}. - - In \CLaSH, parametric polymorphism is completely supported. Any function - defined can have any number of unconstrained type parameters. The \CLaSH\ - compiler will infer the type of every such argument depending on how the - function is applied. There is one exception to this: The top level - function that is translated, can not have any polymorphic arguments (as - they are never applied, so there is no way to find out the actual types - for the type parameters). - - \CLaSH\ does not support user-defined type classes, but does use some - of the built-in type classes for its built-in function, such as: \hs{Num} - for numerical operations, \hs{Eq} for the equality operators, and - \hs{Ord} for the comparison/order operators. - - \subsection{Higher order} + the compiler knows that the addition (+) operator is defined for that + type. + % \CLaSH's built-in numerical types are also instances of the \hs{Num} + % class. + % so we can use the addition operator (and thus the \hs{sum} + % function) with \hs{Signed} as well as with \hs{Unsigned}. + + \CLaSH\ supports both parametric polymorphism and ad-hoc polymorphism. Any + function defined can have any number of unconstrained type parameters. A + developer can also specify his own type classes and corresponding + instances. The \CLaSH\ compiler will infer the type of every polymorphic + argument depending on how the function is applied. There is however one + constraint: the top level function that is being translated can not have + any polymorphic arguments. The arguments of the top-level can not be + polymorphic as the function is never applied and consequently there is no + way to determine the actual types for the type parameters. + + With regard to the built-in types, it should be noted that members of + some of the standard Haskell type classes are supported as built-in + functions. These include: the numerial operators of \hs{Num}, the equality + operators of \hs{Eq}, and the comparison/order operators of \hs{Ord}. + + \subsection{Higher-order functions \& values} Another powerful abstraction mechanism in functional languages, is - the concept of \emph{higher order functions}, or \emph{functions as - a first class value}. This allows a function to be treated as a + the concept of \emph{functions as a first class value}, also called + \emph{higher-order functions}. This allows a function to be treated as a value and be passed around, even as the argument of another - function. Let's clarify that with an example: + function. The following example should clarify this concept: + \hspace{-1.7em} + \begin{minipage}{0.93\linewidth} + %format not = "\mathit{not}" \begin{code} - notList xs = map not xs + negateVector xs = map not xs \end{code} - - This defines a function \hs{notList}, with a single list of booleans - \hs{xs} as an argument, which simply negates all of the booleans in - the list. To do this, it uses the function \hs{map}, which takes - \emph{another function} as its first argument and applies that other - function to each element in the list, returning again a list of the - results. - - As you can see, the \hs{map} function is a higher order function, - since it takes another function as an argument. Also note that - \hs{map} is again a polymorphic function: It does not pose any - constraints on the type of elements in the list passed, other than - that it must be the same as the type of the argument the passed - function accepts. The type of elements in the resulting list is of - course equal to the return type of the function passed (which need - not be the same as the type of elements in the input list). Both of - these can be readily seen from the type of \hs{map}: - - \begin{code} - map :: (a -> b) -> [a] -> [b] - \end{code} - - As an example from a common hardware design, let's look at the - equation of a FIR filter. - - \begin{equation} - y_t = \sum\nolimits_{i = 0}^{n - 1} {x_{t - i} \cdot h_i } - \end{equation} - - A FIR filter multiplies fixed constants ($h$) with the current and - a few previous input samples ($x$). Each of these multiplications - are summed, to produce the result at time $t$. - - This is easily and directly implemented using higher order - functions. Consider that the vector \hs{hs} contains the FIR - coefficients and the vector \hs{xs} contains the current input sample - in front and older samples behind. How \hs{xs} gets its value will be - show in the next section about state. + \end{minipage} + \begin{minipage}{0.07\linewidth} + \begin{example} + \label{lst:code6} + \end{example} + \end{minipage} + + The code above defines the \hs{negateVector} function, which takes a + vector of booleans, \hs{xs}, and returns a vector where all the values are + negated. It achieves this by calling the \hs{map} function, and passing it + \emph{another function}, boolean negation, and the vector of booleans, + \hs{xs}. The \hs{map} function applies the negation function to all the + elements in the vector. + + The \hs{map} function is called a higher-order function, since it takes + another function as an argument. Also note that \hs{map} is again a + parametric polymorphic function: it does not pose any constraints on the + type of the input vector, other than that its elements must have the same + type as the first argument of the function passed to \hs{map}. The element + type of the resulting vector is equal to the return type of the function + passed, which need not necessarily be the same as the element type of the + input vector. All of these characteristics can readily be inferred from + the type signature belonging to \hs{map}: \begin{code} - fir ... = foldl1 (+) (zipwith (*) xs hs) + map :: (a -> b) -> [a|n] -> [b|n] \end{code} - Here, the \hs{zipwith} function is very similar to the \hs{map} - function: It takes a function two lists and then applies the - function to each of the elements of the two lists pairwise - (\emph{e.g.}, \hs{zipwith (+) [1, 2] [3, 4]} becomes - \hs{[1 + 3, 2 + 4]}. - - The \hs{foldl1} function takes a function and a single list and applies the - function to the first two elements of the list. It then applies to - function to the result of the first application and the next element - from the list. This continues until the end of the list is reached. - The result of the \hs{foldl1} function is the result of the last - application. - - As you can see, the \hs{zipwith (*)} function is just pairwise - multiplication and the \hs{foldl1 (+)} function is just summation. - - To make the correspondence between the code and the equation even - more obvious, we turn the list of input samples in the equation - around. So, instead of having the the input sample received at time - $t$ in $x_t$, $x_0$ now always stores the current sample, and $x_i$ - stores the $ith$ previous sample. This changes the equation to the - following (Note that this is completely equivalent to the original - equation, just with a different definition of $x$ that better suits - the \hs{x} from the code): - - \begin{equation} - y_t = \sum\nolimits_{i = 0}^{n - 1} {x_i \cdot h_i } - \end{equation} - - So far, only functions have been used as higher order values. In + So far, only functions have been used as higher-order values. In Haskell, there are two more ways to obtain a function-typed value: partial application and lambda abstraction. Partial application means that a function that takes multiple arguments can be applied @@ -955,36 +1059,51 @@ by any (optimizing) \VHDL\ synthesis tool. that takes one argument less). As an example, consider the following expression, that adds one to every element of a vector: + \hspace{-1.7em} + \begin{minipage}{0.93\linewidth} \begin{code} - map ((+) 1) xs + map (add 1) xs \end{code} - - Here, the expression \hs{(+) 1} is the partial application of the - plus operator to the value \hs{1}, which is again a function that - adds one to its argument. - - A labmda expression allows one to introduce an anonymous function - in any expression. Consider the following expression, which again - adds one to every element of a list: - + \end{minipage} + \begin{minipage}{0.07\linewidth} + \begin{example} + \label{lst:code7} + \end{example} + \end{minipage} + + Here, the expression \hs{(add 1)} is the partial application of the + addition function to the value \hs{1}, which is again a function that + adds one to its (next) argument. A lambda expression allows one to + introduce an anonymous function in any expression. Consider the following + expression, which again adds one to every element of a vector: + + \hspace{-1.7em} + \begin{minipage}{0.93\linewidth} \begin{code} map (\x -> x + 1) xs \end{code} - - Finally, higher order arguments are not limited to just builtin - functions, but any function defined in \CLaSH\ can have function - arguments. This allows the hardware designer to use a powerful - abstraction mechanism in his designs and have an optimal amount of - code reuse. - - \comment{TODO: Describe ALU example (no code)} + \end{minipage} + \begin{minipage}{0.07\linewidth} + \begin{example} + \label{lst:code8} + \end{example} + \end{minipage} + + Finally, not only built-in functions can have higher order arguments (such + as the \hs{map} function), but any function defined in \CLaSH\ may have + functions as arguments. This allows the circuit designer to use a + powerful amount of code reuse. The only exception is again the top-level + function: if a function-typed argument is not applied with an actual + function, no hardware can be generated. + + % \comment{TODO: Describe ALU example (no code)} \subsection{State} - A very important concept in hardware it the concept of state. In a + A very important concept in hardware is the concept of state. In a stateful design, the outputs depend on the history of the inputs, or the state. State is usually stored in registers, which retain their value during a clock cycle. As we want to describe more than simple - combinatorial designs, \CLaSH\ needs an abstraction mechanism for state. + combinational designs, \CLaSH\ needs an abstraction mechanism for state. An important property in Haskell, and in most other functional languages, is \emph{purity}. A function is said to be \emph{pure} if it satisfies two @@ -992,89 +1111,430 @@ by any (optimizing) \VHDL\ synthesis tool. \begin{inparaenum} \item given the same arguments twice, it should return the same value in both cases, and - \item when the function is called, it should not have observable - side-effects. + \item that the function has no observable side-effects. \end{inparaenum} - This purity property is important for functional languages, since it - enables all kinds of mathematical reasoning that could not be guaranteed - correct for impure functions. Pure functions are as such a perfect match - for a combinatorial circuit, where the output solely depends on the - inputs. When a circuit has state however, it can no longer be simply - described by a pure function. Simply removing the purity property is not a - valid option, as the language would then lose many of it mathematical - properties. In an effort to include the concept of state in pure - functions, the current value of the state is made an argument of the - function; the updated state becomes part of the result. A simple example - is adding an accumulator register to the earlier multiply-accumulate - circuit, of which the resulting netlist can be seen in + % This purity property is important for functional languages, since it + % enables all kinds of mathematical reasoning that could not be guaranteed + % correct for impure functions. + Pure functions are as such a perfect match for combinational circuits, + where the output solely depends on the inputs. When a circuit has state + however, it can no longer be simply described by a pure function. + % Simply removing the purity property is not a valid option, as the + % language would then lose many of it mathematical properties. + In \CLaSH\ we deal with the concept of state in pure functions by making + the current state an additional argument of the function, and the + updated state part of result. In this sense the descriptions made in + \CLaSH\ are the combinational parts of a mealy machine. + + A simple example is adding an accumulator register to the earlier + multiply-accumulate circuit, of which the resulting netlist can be seen in \Cref{img:mac-state}: + \hspace{-1.7em} + \begin{minipage}{0.93\linewidth} \begin{code} - macS a b (State c) = (State c', outp) + macS (State c) a b = (State c', c') where - outp = mac a b c - c' = outp + c' = mac a b c \end{code} + \end{minipage} + \begin{minipage}{0.07\linewidth} + \begin{example} + \label{lst:code9} + \end{example} + \end{minipage} \begin{figure} - \centerline{\includegraphics{mac-state}} + \centerline{\includegraphics{mac-state.svg}} \caption{Stateful Multiply-Accumulate} \label{img:mac-state} + \vspace{-1.5em} \end{figure} - This approach makes the state of a circuit very explicit: which variables - are part of the state is completely determined by the type signature. This - approach to state is well suited to be used in combination with the - existing code and language features, such as all the choice constructs, as - state values are just normal values. -\section{\CLaSH\ prototype} - -foo\par bar + Note that the \hs{macS} function returns both the new state and the value + of the output port. The \hs{State} keyword indicates which arguments are + part of the current state, and what part of the output is part of the + updated state. This aspect will also be reflected in the type signature of + the function. Abstracting the state of a circuit in this way makes it very + explicit: which variables are part of the state is completely determined + by the type signature. This approach to state is well suited to be used in + combination with the existing code and language features, such as all the + choice elements, as state values are just normal values. We can simulate + stateful descriptions using the recursive \hs{run} function: + + \hspace{-1.7em} + \begin{minipage}{0.93\linewidth} + \begin{code} + run f s (i : inps) = o : (run f s' inps) + where + (s', o) = f s i + \end{code} + \end{minipage} + \begin{minipage}{0.07\linewidth} + \begin{example} + \label{lst:code10} + \end{example} + \end{minipage} + + The \hs{(:)} operator is the list concatenation operator, where the + left-hand side is the head of a list and the right-hand side is the + remainder of the list. The \hs{run} function applies the function the + developer wants to simulate, \hs{f}, to the current state, \hs{s}, and the + first input value, \hs{i}. The result is the first output value, \hs{o}, + and the updated state \hs{s'}. The next iteration of the \hs{run} function + is then called with the updated state, \hs{s'}, and the rest of the + inputs, \hs{inps}. For the time being, and in the context of this paper, + it is assumed that there is one input per clock cycle. Also note how the + order of the input, output, and state in the \hs{run} function corresponds + with the order of the input, output and state of the \hs{macS} function + described earlier. + + As the \hs{run} function, the hardware description, and the test + inputs are also valid Haskell, the complete simulation can be compiled to + an executable binary by an optimizing Haskell compiler, or executed in an + Haskell interpreter. Both simulation paths are much faster than first + translating the description to \VHDL\ and then running a \VHDL\ + simulation. + +\section{The \CLaSH\ compiler} +An important aspect in this research is the creation of the prototype +compiler, which allows us to translate descriptions made in the \CLaSH\ +language as described in the previous section to synthesizable \VHDL. +% , allowing a designer to actually run a \CLaSH\ design on an \acro{FPGA}. + +The Glasgow Haskell Compiler (\GHC)~\cite{ghc} is an open-source Haskell +compiler that also provides a high level API to most of its internals. The +availability of this high-level API obviated the need to design many of the +tedious parts of the prototype compiler, such as the parser, semantics +checker, and especially the type-checker. These parts together form the +front-end of the prototype compiler pipeline, as seen in +\Cref{img:compilerpipeline}. + +\begin{figure} +\centerline{\includegraphics{compilerpipeline.svg}} +\caption{\CLaSHtiny\ compiler pipeline} +\label{img:compilerpipeline} +\vspace{-1.5em} +\end{figure} + +The output of the \GHC\ front-end consists of the translation of the original +Haskell description in \emph{Core}~\cite{Sulzmann2007}, which is a smaller, +typed, functional language. This \emph{Core} language is relatively easy to +process compared to the larger Haskell language. A description in \emph{Core} +can still contain elements which have no direct translation to hardware, such +as polymorphic types and function-valued arguments. Such a description needs +to be transformed to a \emph{normal form}, which only contains elements that +have a direct translation. The second stage of the compiler, the +\emph{normalization} phase, exhaustively applies a set of +\emph{meaning-preserving} transformations on the \emph{Core} description until +this description is in a \emph{normal form}. This set of transformations +includes transformations typically found in reduction systems and lambda +calculus~\cite{lambdacalculus}, such as $\beta$-reduction and +$\eta$-expansion. It also includes self-defined transformations that are +responsible for the reduction of higher-order functions to `regular' +first-order functions, and specializing polymorphic types to concrete types. + +The final step in the compiler pipeline is the translation to a \VHDL\ +\emph{netlist}, which is a straightforward process due to resemblance of a +normalized description and a set of concurrent signal assignments. We call the +end-product of the \CLaSH\ compiler a \VHDL\ \emph{netlist} as the resulting +\VHDL\ resembles an actual netlist description and not idiomatic \VHDL. + +\section{Use cases} +\label{sec:usecases} +\subsection{FIR Filter} +As an example of a common hardware design where the use of higher-order +functions leads to a very natural description is a \acro{FIR} filter, which is +basically the dot-product of two vectors: + +\begin{equation} +y_t = \sum\nolimits_{i = 0}^{n - 1} {x_{t - i} \cdot h_i } +\end{equation} + +A \acro{FIR} filter multiplies fixed constants ($h$) with the current +and a few previous input samples ($x$). Each of these multiplications +are summed, to produce the result at time $t$. The equation of a \acro{FIR} +filter is indeed equivalent to the equation of the dot-product, which is +shown below: + +\begin{equation} +\mathbf{a}\bullet\mathbf{b} = \sum\nolimits_{i = 0}^{n - 1} {a_i \cdot b_i } +\end{equation} + +We can easily and directly implement the equation for the dot-product +using higher-order functions: + +\hspace{-1.7em} +\begin{minipage}{0.93\linewidth} +\begin{code} +as *+* bs = foldl1 (+) (zipWith (*) as bs) +\end{code} +\end{minipage} +\begin{minipage}{0.07\linewidth} + \begin{example} + \label{lst:code13} + \end{example} +\end{minipage} + +The \hs{zipWith} function is very similar to the \hs{map} function seen +earlier: It takes a function, two vectors, and then applies the function to +each of the elements in the two vectors pairwise (\emph{e.g.}, \hs{zipWith (*) +[1, 2] [3, 4]} becomes \hs{[1 * 3, 2 * 4]}). + +The \hs{foldl1} function takes a binary function, a single vector, and applies +the function to the first two elements of the vector. It then applies the +function to the result of the first application and the next element in the +vector. This continues until the end of the vector is reached. The result of +the \hs{foldl1} function is the result of the last application. It is obvious +that the \hs{zipWith (*)} function is pairwise multiplication and that the +\hs{foldl1 (+)} function is summation. +% Returning to the actual \acro{FIR} filter, we will slightly change the +% equation describing it, so as to make the translation to code more obvious and +% concise. What we do is change the definition of the vector of input samples +% and delay the computation by one sample. Instead of having the input sample +% received at time $t$ stored in $x_t$, $x_0$ now always stores the newest +% sample, and $x_i$ stores the $ith$ previous sample. This changes the equation +% to the following (note that this is completely equivalent to the original +% equation, just with a different definition of $x$ that will better suit the +% transformation to code): +% +% \begin{equation} +% y_t = \sum\nolimits_{i = 0}^{n - 1} {x_i \cdot h_i } +% \end{equation} +The complete definition of the \acro{FIR} filter in code then becomes: + +\hspace{-1.7em} +\begin{minipage}{0.93\linewidth} +\begin{code} +fir (State (xs,hs)) x = + (State (x >> xs,hs), (x +> xs) *+* hs) +\end{code} +\end{minipage} +\begin{minipage}{0.07\linewidth} + \begin{example} + \label{lst:code14} + \end{example} +\end{minipage} + +Where the vector \hs{xs} contains the previous input samples, the vector +\hs{hs} contains the \acro{FIR} coefficients, and \hs{x} is the current input +sample. The concatenate operator (\hs{+>}) creates a new vector by placing the +current sample (\hs{x}) in front of the previous samples vector (\hs{xs}). The +code for the shift (\hs{>>}) operator, that adds the new input sample (\hs{x}) +to the list of previous input samples (\hs{xs}) and removes the oldest sample, +is shown below: + +\hspace{-1.7em} +\begin{minipage}{0.93\linewidth} +\begin{code} +x >> xs = x +> init xs +\end{code} +\end{minipage} +\begin{minipage}{0.07\linewidth} + \begin{example} + \label{lst:code15} + \end{example} +\end{minipage} + +Where the \hs{init} function returns all but the last element of a vector. +The resulting netlist of a 4-taps \acro{FIR} filter, created by specializing +the vectors of the \acro{FIR} code to a length of 4, is depicted in +\Cref{img:4tapfir}. + +\begin{figure} +\centerline{\includegraphics{4tapfir.svg}} +\caption{4-taps \acrotiny{FIR} Filter} +\label{img:4tapfir} +\vspace{-1.5em} +\end{figure} + +\subsection{Higher-order CPU} +The following simple \acro{CPU} is an example of user-defined higher order +functions and pattern matching. The \acro{CPU} consists of four function +units, of which three have a fixed function and one can perform certain less +common operations. + +The \acro{CPU} contains a number of data sources, represented by the +horizontal wires in \Cref{img:highordcpu}. These data sources offer the +previous outputs of each function units, along with the single data input the +\acro{CPU} has and two fixed initialization values. + +Each of the function units has both its operands connected to all data +sources, and can be programmed to select any data source for either +operand. In addition, the leftmost function unit has an additional +opcode input to select the operation it performs. The output of the rightmost +function unit is also the output of the entire \acro{CPU}. + +Looking at the code, the function unit (\hs{fu}) is the most simple. It +arranges the operand selection for the function unit. Note that it does not +define the actual operation that takes place inside the function unit, +but simply accepts the (higher-order) argument \hs{op} which is a function +of two arguments that defines the operation. + +\hspace{-1.7em} +\begin{minipage}{0.93\linewidth} +\begin{code} +fu op inputs (addr1, addr2) = regIn + where + in1 = inputs!addr1 + in2 = inputs!addr2 + regIn = op in1 in2 +\end{code} +\end{minipage} +\begin{minipage}{0.07\linewidth} + \begin{example} + \label{lst:code16} + \end{example} +\end{minipage} + +The \hs{multiop} function defines the operation that takes place in the +leftmost function unit. It is essentially a simple three operation \acro{ALU} +that makes good use of pattern matching and guards in its description. +The \hs{shift} function used here shifts its first operand by the number +of bits indicated in the second operand, the \hs{xor} function produces +the bitwise xor of its operands. + +\hspace{-1.7em} +\begin{minipage}{0.93\linewidth} +\begin{code} +data Opcode = Shift | Xor | Equal + +multiop :: Opcode -> Word -> Word -> Word +multiop Shift a b = shift a b +multiop Xor a b = xor a b +multiop Equal a b | a == b = 1 + | otherwise = 0 +\end{code} +\end{minipage} +\begin{minipage}{0.07\linewidth} + \begin{example} + \label{lst:code17} + \end{example} +\end{minipage} + +The \acro{CPU} function ties everything together. It applies the \hs{fu} +function four times, to create a different function unit each time. The +first application is interesting, because it does not just pass a +function to \hs{fu}, but a partial application of \hs{multiop}. This +shows how the first function unit effectively gets an extra input, +compared to the others. + +The vector \hs{inputs} is the set of data sources, which is passed to +each function unit as a set of possible operants. The \acro{CPU} also receives +a vector of address pairs, which are used by each function unit to select +their operand. The application of the function units to the \hs{inputs} and +\hs{addrs} arguments seems quite repetitive and could be rewritten to use +a combination of the \hs{map} and \hs{zipwith} functions instead. +However, the prototype compiler does not currently support working with lists +of functions, so a more explicit version of the code is given instead. + +\hspace{-1.7em} +\begin{minipage}{0.93\linewidth} +\begin{code} +type CpuState = State [Word | 4] + +cpu :: CpuState -> Word -> [(Index 6, Index 6) | 4] + -> Opcode -> (CpuState, Word) +cpu (State s) input addrs opc = (State s', out) + where + s' = [ fu (multiop opc) inputs (addrs!0) + , fu add inputs (addrs!1) + , fu sub inputs (addrs!2) + , fu mul inputs (addrs!3) + ] + inputs = 0 +> (1 +> (input +> s)) + out = head s' +\end{code} +\end{minipage} +\begin{minipage}{0.07\linewidth} + \begin{example} + \label{lst:code18} + \end{example} +\end{minipage} + +This is still a simple example, but it could form the basis +of an actual design, in which the same techniques can be reused. \section{Related work} -Many functional hardware description languages have been developed over the -years. Early work includes such languages as $\mu$\acro{FP}~\cite{muFP}, an -extension of Backus' \acro{FP} language to synchronous streams, designed -particularly for describing and reasoning about regular circuits. The -Ruby~\cite{Ruby} language uses relations, instead of functions, to describe -circuits, and has a particular focus on layout. \acro{HML}~\cite{HML2} is a -hardware modeling language based on the strict functional language -\acro{ML}, and has support for polymorphic types and higher-order functions. -Published work suggests that there is no direct simulation support for -\acro{HML}, and that the translation to \VHDL\ is only partial. - -Like this work, many functional hardware description languages have some sort -of foundation in the functional programming language Haskell. -Hawk~\cite{Hawk1} uses Haskell to describe system-level executable -specifications used to model the behavior of superscalar microprocessors. Hawk -specifications can be simulated, but there seems to be no support for -automated circuit synthesis. The ForSyDe~\cite{ForSyDe2} system uses Haskell -to specify abstract system models, which can (manually) be transformed into an -implementation model using semantic preserving transformations. ForSyDe has -several simulation and synthesis backends, though synthesis is restricted to -the synchronous subset of the ForSyDe language. - -Lava~\cite{Lava} is a hardware description language that focuses on the -structural representation of hardware. Besides support for simulation and -circuit synthesis, Lava descriptions can be interfaced with formal method -tools for formal verification. Lava descriptions are actually circuit -generators when viewed from a synthesis viewpoint, in that the language -elements of Haskell, such as choice, can be used to guide the circuit -generation. If a developer wants to insert a choice element inside an actual -circuit he will have to specify this explicitly as a component. In this -respect \CLaSH\ differs from Lava, in that all the choice elements, such as -case-statements and pattern matching, are synthesized to choice elements in the -eventual circuit. As such, richer control structures can both be specified and -synthesized in \CLaSH\ compared to any of the languages mentioned in this -section. - -The merits of polymorphic typing, combined with higher-order functions, are -now also recognized in the `main-stream' hardware description languages, -exemplified by the new \VHDL-2008 standard~\cite{VHDL2008}. \VHDL-2008 has -support to specify types as generics, thus allowing a developer to describe -polymorphic components. Note that those types still require an explicit -generic map, whereas type-inference and type-specialization are implicit in -\CLaSH. +This section describes the features of existing (functional) hardware +description languages and highlights the advantages that this research has +over existing work. + +% Many functional hardware description languages have been developed over the +% years. Early work includes such languages as $\mu$\acro{FP}~\cite{muFP}, an +% extension of Backus' \acro{FP} language to synchronous streams, designed +% particularly for describing and reasoning about regular circuits. The +% Ruby~\cite{Ruby} language uses relations, instead of functions, to describe +% circuits, and has a particular focus on layout. + +\acro{HML}~\cite{HML2} is a hardware modeling language based on the strict +functional language \acro{ML}, and has support for polymorphic types and +higher-order functions. Published work suggests that there is no direct +simulation support for \acro{HML}, but that a description in \acro{HML} has to +be translated to \VHDL\ and that the translated description can then be +simulated in a \VHDL\ simulator. Certain aspects of HML, such as higher-order +functions are however not supported by the \VHDL\ translator~\cite{HML3}. The +\CLaSH\ compiler on the other hand can correctly translate all of the language +constructs mentioned in this paper. % to a netlist format. + +\begin{figure} +\centerline{\includegraphics{highordcpu.svg}} +\caption{CPU with higher-order Function Units} +\label{img:highordcpu} +\vspace{-1.5em} +\end{figure} + +Like the research presented in this paper, many functional hardware +description languages have some sort of foundation in the functional +programming language Haskell. Hawk~\cite{Hawk1} uses Haskell to describe +system-level executable specifications used to model the behavior of +superscalar microprocessors. Hawk specifications can be simulated; to the best +knowledge of the authors there is however no support for automated circuit +synthesis. + +The ForSyDe~\cite{ForSyDe2} system uses Haskell to specify abstract system +models. A designer can model systems using heterogeneous models of +computation, which include continuous time, synchronous and untimed models of +computation. Using so-called domain interfaces a designer can simulate +electronic systems which have both analog as digital parts. ForSyDe has +several backends including simulation and automated synthesis, though +automated synthesis is restricted to the synchronous model of computation. +Though ForSyDe offers higher-order functions and polymorphism, ForSyDe's +choice elements are limited to \hs{if} and \hs{case} expressions. ForSyDe's +explicit conversions, where function have to be wrapped in processes and +processes have to be wrapped in systems, combined with the explicit +instantiations of components, also makes ForSyDe more verbose than \CLaSH. + +Lava~\cite{Lava} is a hardware description language, embedded in Haskell, and +focuses on the structural representation of hardware. Like \CLaSH, Lava has +support for polymorphic types and higher-order functions. Besides support for +simulation and circuit synthesis, Lava descriptions can be interfaced with +formal method tools for formal verification. As discussed in the introduction, +taking the embedded language approach does not allow for Haskell's choice +elements to be captured within the circuit descriptions. In this respect +\CLaSH\ differs from Lava, in that all of Haskell's choice elements, such as +\hs{case}-expressions and pattern matching, are synthesized to choice elements +in the eventual circuit. Consequently, descriptions containing rich control +structures can be specified in a more user-friendly way in \CLaSH\ than possible within Lava, and are hence less error-prone. + +Bluespec~\cite{Bluespec} is a high-level synthesis language that features +guarded atomic transactions and allows for the automated derivation of control +structures based on these atomic transactions. Bluespec, like \CLaSH, supports +polymorphic typing and function-valued arguments. Bluespec's syntax and +language features \emph{had} their basis in Haskell. However, in order to +appeal to the users of the traditional \acrop{HDL}, Bluespec has adapted +imperative features and a syntax that resembles Verilog. As a result, Bluespec +is (unnecessarily) verbose when compared to \CLaSH. + +The merits of polymorphic typing and function-valued arguments are now also +recognized in the traditional \acrop{HDL}, exemplified by the new \VHDL-2008 +standard~\cite{VHDL2008}. \VHDL-2008 support for generics has been extended to +types and subprograms, allowing a designer to describe components with +polymorphic ports and function-valued arguments. Note that the types and +subprograms still require an explicit generic map, whereas types can be +automatically inferred, and function-values can be automatically propagated +by the \CLaSH\ compiler. There are also no (generally available) \VHDL\ +synthesis tools that currently support the \VHDL-2008 standard. % Wired~\cite{Wired},, T-Ruby~\cite{T-Ruby}, Hydra~\cite{Hydra}. % @@ -1167,29 +1627,53 @@ generic map, whereas type-inference and type-specialization are implicit in \section{Conclusion} -The conclusion goes here. - - - +This research demonstrates once more that functional languages are well suited +for hardware descriptions: function applications provide an elegant notation +for component instantiation. Where this research goes beyond the existing +(functional) hardware descriptions languages is the inclusion of various +choice elements, such as pattern matching, that are well suited to describe +the conditional assignments in control-oriented circuits. Besides being able +to translate these basic constructs to synthesizable \VHDL, the prototype +compiler can also correctly translate descriptions that contain both +polymorphic types and function-valued arguments. + +Where recent functional hardware description languages have mostly opted to +embed themselves in an existing functional language, this research features a +`true' compiler. As a result there is a clear distinction between compile-time +and run-time, which allows a myriad of choice constructs to be part of the +actual circuit description; a feature the embedded hardware description +languages do not offer. + +\section{Future Work} +The choice of describing state explicitly as extra arguments and results can +be seen as a mixed blessing. Even though the description that use state are +usually very clear, one finds that dealing with unpacking, passing, receiving +and repacking can become tedious and even error-prone, especially in the case +of sub-states. Removing this boilerplate, or finding a more suitable +abstraction mechanism would make \CLaSH\ easier to use. + +The transformations in normalization phase of the prototype compiler were +developed in an ad-hoc manner, which makes the existence of many desirable +properties unclear. Such properties include whether the complete set of +transformations will always lead to a normal form or if the normalization +process always terminates. Though various use cases suggests that these +properties usually hold, they have not been formally proven. A systematic +approach to defining the set of transformations allows one to proof that the +earlier mentioned properties do indeed exist. % conference papers do not normally have an appendix % use section* for acknowledgement -\section*{Acknowledgment} - - -The authors would like to thank... - - - - +% \section*{Acknowledgment} +% +% The authors would like to thank... % trigger a \newpage just before the given reference % number - used to balance the columns on the last page % adjust value as needed - may need to be readjusted if % the document is modified later -%\IEEEtriggeratref{8} +% \IEEEtriggeratref{14} % The "triggered" command can be changed if desired: %\IEEEtriggercmd{\enlargethispage{-5in}} @@ -1202,7 +1686,7 @@ The authors would like to thank... % http://www.michaelshell.org/tex/ieeetran/bibtex/ \bibliographystyle{IEEEtran} % argument is your BibTeX string definitions and bibliography database(s) -\bibliography{IEEEabrv,clash.bib} +\bibliography{clash} % % manually copy in the resultant .bbl file % set second argument of \begin to the number of references