% 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.
% 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}}
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
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|
\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:
\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
% 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}
\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
\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\
% 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}).
\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:
% 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
% \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
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:
\begin{figure}
\centerline{\includegraphics{compilerpipeline.svg}}
-\caption{\CLaSH\ compiler pipeline}
+\caption{\CLaSHtiny\ compiler pipeline}
\label{img:compilerpipeline}
\end{figure}
\begin{figure}
\centerline{\includegraphics{4tapfir.svg}}
-\caption{4-taps FIR Filter}
+\caption{4-taps \acrotiny{FIR} Filter}
\label{img:4tapfir}
\end{figure}