X-Git-Url: https://git.stderr.nl/gitweb?p=matthijs%2Fmaster-project%2Fdsd-paper.git;a=blobdiff_plain;f=c%CE%BBash.lhs;h=886376648304d8550742b94de4148a53399dcbcd;hp=a42abe446f13f7e2caf9d1314162ea6655716c26;hb=d8b9a02732239603a440bf060bdbe6db0522b981;hpb=92f100ec66785792b557fb877a392d2ef8fb4e20 diff --git "a/c\316\273ash.lhs" "b/c\316\273ash.lhs" index a42abe4..8863766 100644 --- "a/c\316\273ash.lhs" +++ "b/c\316\273ash.lhs" @@ -342,9 +342,11 @@ % 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\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. @@ -393,7 +395,7 @@ % 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{Computer Architecture for Embedded Systems (CAES)\\ +\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}} @@ -526,22 +528,23 @@ optimizing Haskell compiler such as the Glasgow Haskell Compiler (\GHC)~\cite{gh 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. The current abstraction of state and time limits the -descriptions to synchronous hardware, there however is room within the -language to eventually add a different abstraction mechanism that will allow -for the modeling of asynchronous systems. 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. +clock cycles. 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. The current abstraction of state and time limits the descriptions to +synchronous hardware, there however is room within the language to eventually +add a different abstraction mechanism that will allow for the modeling of +asynchronous systems. 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, which has the -same name as the language: \CLaSH\footnote{C$\lambda$aSH: 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. +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 FIR filter and the simple CPU shown in \Cref{sec:usecases}, the \CLaSH\ compiler has also been @@ -562,18 +565,19 @@ circuit~\cite{reductioncircuit} for floating point numbers. 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 output port can have a structured type (such as a tuple), so having + just a single output port does not pose any limitation. The 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,% aswell, - creating a hierarchical description of the hardware. This separation in - different components makes the resulting \VHDL\ output easier to read and - debug. + 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. 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| @@ -589,7 +593,7 @@ circuit~\cite{reductioncircuit} for floating point numbers. \label{img:mac-comb} \end{figure} - The result of using a complex input type can be seen in + The result of using a structural 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: @@ -606,7 +610,7 @@ circuit~\cite{reductioncircuit} for floating point numbers. \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} + pattern matching, and guards. The most general 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 @@ -616,17 +620,27 @@ circuit~\cite{reductioncircuit} for floating point numbers. % 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. + using a \hs{case} construct and the other using an \hs{if-then-else} + construct, in the code below. The examples sums two values when they are + equal or non-equal (depending on the given predicate, the \hs{pred} + variable) and returns 0 otherwise. The \hs{pred} variable has the + following, user-defined, enumeration datatype: \begin{code} + data Pred = Equiv | NotEquiv + \end{code} + + The naive netlist corresponding to both versions of the example is + depicted in \Cref{img:choice}. + + \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 + Equiv -> case a == b of + True -> a + b + False -> 0 + NotEquiv -> case a != b of + True -> a + b + False -> 0 \end{code} \begin{code} @@ -642,23 +656,24 @@ circuit~\cite{reductioncircuit} for floating point numbers. \caption{Choice - sumif} \label{img:choice} \end{figure} - - 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}. - A slightly more complex (but very powerful) form of choice is pattern + A user-friendly and also 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 + 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. Like + 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} 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. + 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. \begin{code} sumif Eq a b | a == b = a + b @@ -676,8 +691,8 @@ circuit~\cite{reductioncircuit} for floating point numbers. \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 + therefor 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\ @@ -702,16 +717,16 @@ circuit~\cite{reductioncircuit} for floating point numbers. % 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 direct 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}). @@ -719,7 +734,7 @@ circuit~\cite{reductioncircuit} for floating point numbers. \hs{if-then-else} construct, 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, + these are types to represent integers. A \hs{SizedWord} is unsigned, while a \hs{SizedInt} is signed. Both are parametrizable in their size. % , so you can define an unsigned word of 32 bits wide as follows: @@ -735,7 +750,7 @@ circuit~\cite{reductioncircuit} for floating point numbers. % 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 + 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 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 @@ -755,7 +770,7 @@ circuit~\cite{reductioncircuit} for floating point numbers. % \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 @@ -782,14 +797,14 @@ circuit~\cite{reductioncircuit} for floating point numbers. 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. + existential typing, {\acro{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 + 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 + and type renaming requires 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: @@ -1032,7 +1047,7 @@ hardware. \begin{figure} \centerline{\includegraphics{compilerpipeline.svg}} -\caption{\CLaSH\ compiler pipeline} +\caption{\CLaSHtiny\ compiler pipeline} \label{img:compilerpipeline} \end{figure} @@ -1127,7 +1142,7 @@ is depicted in \Cref{img:4tapfir}. \begin{figure} \centerline{\includegraphics{4tapfir.svg}} -\caption{4-taps FIR Filter} +\caption{4-taps \acrotiny{FIR} Filter} \label{img:4tapfir} \end{figure}