X-Git-Url: https://git.stderr.nl/gitweb?p=matthijs%2Fmaster-project%2Fdsd-paper.git;a=blobdiff_plain;f=c%CE%BBash.lhs;h=362fe5831c8679cd38292a76c03381bbf84456b6;hp=1dd21ce530709fccda16e1fc74af67c2d0ccf7fc;hb=f513b84e02a6bd0215334379dda9b74a19d178ab;hpb=6835a7a214399baa57eec06aa5698932c4184d42 diff --git "a/c\316\273ash.lhs" "b/c\316\273ash.lhs" index 1dd21ce..362fe58 100644 --- "a/c\316\273ash.lhs" +++ "b/c\316\273ash.lhs" @@ -375,6 +375,9 @@ \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 @@ -442,7 +445,15 @@ c.p.r.baaij@@utwente.nl, matthijs@@stdin.nl, j.kuper@@utwente.nl}} \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. Circuit +descriptions can be translated to synthesizable VHDL using the prototype +\CLaSH\ compiler. As the circuit descriptions are made in plain Haskell, +simulations can also be compiled by a Haskell compiler. + +The use of polymorphism and higher-order functions allow a circuit designer to +describe more abstract and general specifications than are possible in the +traditional hardware description languages. \end{abstract} % IEEEtran.cls defaults to using nonbold math in the Abstract. % This preserves the distinction between vectors and scalars. However, @@ -509,7 +520,7 @@ 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). +optimizing Haskell compiler such as the Glasgow Haskell Compiler (\GHC)~\cite{ghc}. Where descriptions in a conventional hardware description language have an explicit clock for the purpose state and synchronicity, the clock is implied @@ -562,7 +573,7 @@ by an (optimizing) \VHDL\ synthesis tool. \end{code} \begin{figure} - \centerline{\includegraphics{mac}} + \centerline{\includegraphics{mac.svg}} \caption{Combinatorial Multiply-Accumulate} \label{img:mac-comb} \end{figure} @@ -576,7 +587,7 @@ by an (optimizing) \VHDL\ synthesis tool. \end{code} \begin{figure} - \centerline{\includegraphics{mac-nocurry}} + \centerline{\includegraphics{mac-nocurry.svg}} \caption{Combinatorial Multiply-Accumulate (complex input)} \label{img:mac-comb-nocurry} \end{figure} @@ -619,7 +630,7 @@ by an (optimizing) \VHDL\ synthesis tool. \end{code} \begin{figure} - \centerline{\includegraphics{choice-case}} + \centerline{\includegraphics{choice-case.svg}} \caption{Choice - sumif} \label{img:choice} \end{figure} @@ -865,7 +876,7 @@ by an (optimizing) \VHDL\ synthesis tool. for numerical operations, \hs{Eq} for the equality operators, and \hs{Ord} for the comparison/order operators. - \subsection{Higher-order functions} + \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 @@ -896,58 +907,8 @@ by an (optimizing) \VHDL\ synthesis tool. \begin{code} map :: (a -> b) -> [a|n] -> [b|n] \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. - \begin{code} - fir {-"$\ldots$"-} = foldl1 (+) (zipwith (*) xs hs) - \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 @@ -961,17 +922,15 @@ by an (optimizing) \VHDL\ synthesis tool. 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: + adds one to its 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: \begin{code} map (\x -> x + 1) xs \end{code} - Finally, higher order arguments are not limited to just builtin + Finally, higher order arguments are not limited to just built-in 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 @@ -995,41 +954,162 @@ by an (optimizing) \VHDL\ synthesis tool. \item when the function is called, it should not have 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 + % 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 or 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 + function; the updated state becomes part of the result. In this sense the + descriptions made in \CLaSH are the describing the combinatorial 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}: \begin{code} - macS a b (State c) = (State c', outp) + macS (State c) a b = (State c', outp) where outp = mac a b c c' = outp \end{code} \begin{figure} - \centerline{\includegraphics{mac-state}} + \centerline{\includegraphics{mac-state.svg}} \caption{Stateful Multiply-Accumulate} \label{img:mac-state} \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. + 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 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 constructs, as state values are just normal values. We can simulate + stateful descriptions using the recursive \hs{run} function: + + \begin{code} + run f s (i:inps) = o : (run f s' inps) + where + (s', o) = f s i + \end{code} + + The \hs{run} function maps a list of inputs over the function that a + developer wants to simulate, passing the state to each new iteration. Each + value in the input list corresponds to exactly one cycle of the (implicit) + clock. The result of the simulation is a list of outputs for every clock + cycle. As both the \hs{run} function and the hardware description are + plain hardware, the complete simulation can be compiled by an optimizing + Haskell compiler. + \section{\CLaSH\ prototype} -foo\par bar +The \CLaSH language as presented above can be translated to \VHDL using +the prototype \CLaSH compiler. This compiler allows experimentation with +the \CLaSH language and allows for running \CLaSH designs on actual FPGA +hardware. + +\comment{Add clash pipeline image} +The prototype heavily uses \GHC, the Glasgow Haskell Compiler. Figure +TODO shows the \CLaSH compiler pipeline. As you can see, the frontend +is completely reused from \GHC, which allows the \CLaSH prototype to +support most of the Haskell Language. The \GHC frontend produces the +program in the \emph{Core} format, which is a very small, functional, +typed language which is relatively easy to process. + +The second step in the compilation process is \emph{normalization}. This +step runs a number of \emph{meaning preserving} transformations on the +Core program, to bring it into a \emph{normal form}. This normal form +has a number of restrictions that make the program similar to hardware. +In particular, a program in normal form no longer has any polymorphism +or higher order functions. + +The final step is a simple translation to \VHDL. + +\section{Use cases} +As an example of a common hardware design where the use of higher-order +functions leads to a very natural description is a 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 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 FIR +filter is indeed equivalent to the equation of the dot-product, which is +shown below: + +\begin{equation} +\mathbf{x}\bullet\mathbf{y} = \sum\nolimits_{i = 0}^{n - 1} {x_i \cdot y_i } +\end{equation} + +We can easily and directly implement the equation for the dot-product +using higher-order functions: + +\begin{code} +xs *+* ys = foldl1 (+) (zipWith (*) xs hs) +\end{code} + +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]} $\equiv$ \hs{[3,8]}). + +The \hs{foldl1} function takes a 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 from +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. +As you can see, the \hs{zipWith (*)} function is just pairwise +multiplication and the \hs{foldl1 (+)} function is just summation. + +Returning to the actual FIR filter, we will slightly change the +equation belong to it, so as to make the translation to code more obvious. +What we will do is change the definition of the vector of input samples. +So, instead of having the input sample received at time +$t$ stored 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 will better suit +the transformation to code): + +\begin{equation} +y_t = \sum\nolimits_{i = 0}^{n - 1} {x_i \cdot h_i } +\end{equation} + +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. The function that shifts the input samples is shown below: + +\begin{code} +x >> xs = x +> tail xs +\end{code} + +Where the \hs{tail} function returns all but the first element of a +vector, and the concatenate operator ($\succ$) adds a new element to the +left of a vector. The complete definition of the FIR filter then becomes: + +\begin{code} +fir (State (xs,hs)) x = (State (x >> xs,hs), xs *+* hs) +\end{code} + +The resulting netlist of a 4-taps FIR filter based on the above definition +is depicted in \Cref{img:4tapfir}. + +\begin{figure} +\centerline{\includegraphics{4tapfir.svg}} +\caption{4-taps FIR Filter} +\label{img:4tapfir} +\end{figure} \section{Related work} Many functional hardware description languages have been developed over the @@ -1037,22 +1117,34 @@ 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. +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 than be +simulated in a \VHDL\ simulator. Also not all of the mentioned language +features of \acro{HML} could be translated to hardware. The \CLaSH\ compiler +on the other hand can correctly translate all of the language constructs +mentioned in this paper to a netlist format. 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. +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. 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 simulation and synthesis backends, +though synthesis is restricted to the synchronous subset of the ForSyDe +language. Unlike \CLaSH\ there is no support for the automated synthesis of description that contain polymorphism or higher-order functions. Lava~\cite{Lava} is a hardware description language that focuses on the structural representation of hardware. Besides support for simulation and @@ -1061,12 +1153,13 @@ 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. +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,