% should be used if it is desired that the figures are to be displayed in
% draft mode.
%
+
\documentclass[conference,pdf,a4paper,10pt,final,twoside,twocolumn]{IEEEtran}
% Add the compsoc option for Computer Society conferences.
%
-
-
-
% *** CITATION PACKAGES ***
%
\usepackage{cite}
\usepackage{xcolor}
\def\comment#1{{\color[rgb]{1.0,0.0,0.0}{#1}}}
+\usepackage{cleveref}
+\crefname{figure}{figure}{figures}
+\newcommand{\fref}[1]{\cref{#1}}
+\newcommand{\Fref}[1]{\Cref{#1}}
+
+
%include polycode.fmt
%include clash.fmt
\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\\
P.O. Box 217, 7500 AE, Enschede, The Netherlands\\
-c.p.r.baaij@@utwente.nl, matthijs@@stdin.nl}}
+c.p.r.baaij@@utwente.nl, matthijs@@stdin.nl, j.kuper@@utwente.nl}}
% \and
% \IEEEauthorblockN{Homer Simpson}
% \IEEEauthorblockA{Twentieth Century Fox\\
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 an optimizing \VHDL\ synthesis tools.
+by an optimizing \VHDL\ synthesis tool.
\section{Hardware description in Haskell}
\subsection{Function application}
The basic syntactic elements of a functional program are functions
- and function application. These have a single obvious \VHDL\
- translation: each top level function becomes a hardware component,
- where each argument is an input port and the result value is the
- (single) output port. This output port can have a complex type (such
- as a tuple), so having just a single output port does not create a
- limitation.
-
- Each function application in turn becomes a component instantiation.
- Here, the result of each argument expression is assigned to a
- signal, which is mapped to the corresponding input port. The output
- port of the function is also mapped to a signal, which is used as
- the result of the application itself.
+ and function application. These have a single obvious translation to a
+ netlist: every function becomes a component, every function argument is an
+ input port and the result value is of a function is an output port. This
+ output port can have a complex type (such as a tuple), so having just a
+ single output port does not create a limitation. Each function application
+ in turn becomes a component instantiation. Here, the result of each
+ argument expression is assigned to a signal, which is mapped to the
+ corresponding input port. 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 \VHDL\
- output as well, creating a hierarchical \VHDL\ description of the
- hardware. This separation in different components makes the
- resulting \VHDL\ output easier to read and debug.
-
- Example that defines the \texttt{mac} function by applying the
- \texttt{add} and \texttt{mul} functions to calculate $a * b + c$:
-
-\begin{code}
-mac a b c = add (mul a b) c
-\end{code}
-
-\begin{figure}
-\centerline{\includegraphics{mac}}
-\caption{Combinatorial Multiply-Accumulate (curried)}
-\label{img:mac-comb}
-\end{figure}
-
-\begin{figure}
-\centerline{\includegraphics{mac-nocurry}}
-\caption{Combinatorial Multiply-Accumulate (uncurried)}
-\label{img:mac-comb-nocurry}
-\end{figure}
-
- \subsection{Choices}
- Although describing components and connections allows describing a
- lot of hardware designs already, there is an obvious thing missing:
- choice. We need some way to be able to choose between values based
- on another value. In Haskell, choice is achieved by \hs{case}
- expressions, \hs{if} expressions, pattern matching and guards.
-
- The easiest of these are of course case expressions (and \hs{if}
- expressions, which can be very directly translated to \hs{case}
- expressions). 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.
-
- 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.
-
- A pattern match (with optional guards) can also be implemented using
- conditional assignments in \VHDL, where the condition is the logical
- and of comparison results of each part of the pattern as well as the
- guard.
-
- Contrived example that sums two values when they are equal or
- non-equal (depending on the predicate given) and returns 0
- otherwise. This shows three implementations, one using and if
- expression, one using only case expressions and one using pattern
- matching and guards.
-
+ 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$:
+
+ \begin{code}
+ mac a b c = add (mul a b) c
+ \end{code}
+
+ \begin{figure}
+ \centerline{\includegraphics{mac}}
+ \caption{Combinatorial Multiply-Accumulate}
+ \label{img:mac-comb}
+ \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:
+
+ \begin{code}
+ mac (a, b, c) = add (mul a b) c
+ \end{code}
+
+ \begin{figure}
+ \centerline{\includegraphics{mac-nocurry}}
+ \caption{Combinatorial Multiply-Accumulate (complex input)}
+ \label{img:mac-comb-nocurry}
+ \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 (and \hs{if} expressions, which can be very directly translated
+ to \hs{case} expressions). 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, 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.
+
\begin{code}
- sumif pred a b = if pred == Eq && a == b ||
- pred == Neq && a != b
- then a + b
- else 0
-
sumif pred a b = case pred of
Eq -> case a == b of
True -> a + b
Neq -> case a != b of
True -> a + b
False -> 0
+ \end{code}
+ \begin{code}
+ sumif pred a b =
+ if pred == Eq then
+ if a == b then a + b else 0
+ else
+ if a != b then a + b else 0
+ \end{code}
+
+ Both versions of the example correspond to the same netlist, which is
+ depicted in \Cref{img:choice}.
+
+ \begin{figure}
+ \centerline{\includegraphics{choice-case}}
+ \caption{Choice - sumif}
+ \label{img:choice}
+ \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. A
+ pattern match (with optional guards) can be to a conditional assignments
+ in \VHDL, where the conditions are an equality test of the argument and
+ one of the patterns (combined with the guard if was present). A third
+ version of the earlier example, using both pattern matching and guards,
+ can be seen below:
+
+ \begin{code}
sumif Eq a b | a == b = a + b
sumif Neq a b | a != b = a + b
sumif _ _ _ = 0
\end{code}
+
+ The version using pattern matching and guards has the same netlist
+ representation (\Cref{img:choice}) as the earlier two versions of the
+ example.
- \comment{TODO: Pretty picture}
+ % \begin{figure}
+ % \centerline{\includegraphics{choice-ifthenelse}}
+ % \caption{Choice - \emph{if-then-else}}
+ % \label{img:choice}
+ % \end{figure}
\subsection{Types}
- Translation of two most basic functional concepts has been
- discussed: function application and choice. Before looking further
- into less obvious concepts like higher-order expressions and
- polymorphism, the possible types that can be used in hardware
- descriptions will be discussed.
-
- Some way is needed to translate every value used to its hardware
- equivalents. In particular, this means a hardware equivalent for
- every \emph{type} used in a hardware description is needed.
-
- The following types are \emph{built-in}, meaning that their hardware
- translation is fixed into the \CLaSH\ compiler. A designer can also
- define his own types, which will be translated into hardware types
- using translation rules that are discussed later on.
-
- \subsection{Built-in types}
+ Haskell is a strongly-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 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.
+
+ % Translation of two most basic functional concepts has been
+ % discussed: function application and choice. Before looking further
+ % into less obvious concepts like higher-order expressions and
+ % polymorphism, the possible types that can be used in hardware
+ % descriptions will be discussed.
+ %
+ % Some way is needed to translate every value used to its hardware
+ % equivalents. In particular, this means a hardware equivalent for
+ % every \emph{type} used in a hardware description is needed.
+ %
+ % The following types are \emph{built-in}, meaning that their hardware
+ % translation is fixed into the \CLaSH\ compiler. A designer can also
+ % define his own types, which will be translated into hardware types
+ % using translation rules that are discussed later on.
+
+ \subsubsection{Built-in types}
\begin{xlist}
- \item[\hs{Bit}]
+ \item[\bf{Bit}]
This is the most basic type available. It can have two values:
- \hs{Low} and \hs{High}. It is mapped directly onto the
- \texttt{std\_logic} \VHDL\ type.
- \item[\hs{Bool}]
+ \hs{Low} and \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}. 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
- particularly useful to support \hs{if ... then ... else ...}
- expressions, which always have a \hs{Bool} value for the
- condition.
- \item[\hs{SizedWord}, \hs{SizedInt}]
+ and \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
+ the condition.
+ \item[\bf{SizedWord}, \bf{SizedInt}]
These are types to represent integers. A \hs{SizedWord} is unsigned,
- while a \hs{SizedInt} is signed. These types are parametrized by a
- length type, so you can define an unsigned word of 32 bits wide as
- follows:
-
- \begin{code}
- type Word32 = SizedWord D32
- \end{code}
-
- Here, a type synonym \hs{Word32} is defined that is equal to the
- \hs{SizedWord} type constructor applied to the type \hs{D32}. \hs{D32}
- is the \emph{type level representation} of the decimal number 32,
- making the \hs{Word32} type a 32-bit unsigned word. These types are
- translated to the \VHDL\ \texttt{unsigned} and \texttt{signed}
- respectively.
- \item[\hs{Vector}]
- This is a vector type, that can contain elements of any other type and
+ 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:
+
+ % \begin{code}
+ % type Word32 = SizedWord D32
+ % \end{code}
+
+ % Here, a type synonym \hs{Word32} is defined that is equal to the
+ % \hs{SizedWord} type constructor applied to the type \hs{D32}.
+ % \hs{D32} is the \emph{type level representation} of the decimal
+ % number 32, making the \hs{Word32} type a 32-bit unsigned word. These
+ % 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
arguments: the length of the vector and the type of the elements
- contained in it. The state type of an 8 element register bank would
- then for example be:
-
- \begin{code}
- type RegisterState = Vector D8 Word32
- \end{code}
-
- Here, a type synonym \hs{RegisterState} is defined that is equal to
- the \hs{Vector} type constructor applied to the types \hs{D8} (The
- type level representation of the decimal number 8) and \hs{Word32}
- (The 32 bit word type as defined above). In other words, the
- \hs{RegisterState} type is a vector of 8 32-bit words. A fixed size
- vector is translated to a \VHDL\ array type.
- \item[\hs{RangedWord}]
+ contained in it.
+ % The state type of an 8 element register bank would then for example
+ % be:
+
+ % \begin{code}
+ % type RegisterState = Vector D8 Word32
+ % \end{code}
+
+ % Here, a type synonym \hs{RegisterState} is defined that is equal to
+ % the \hs{Vector} type constructor applied to the types \hs{D8} (The
+ % type level representation of the decimal number 8) and \hs{Word32}
+ % (The 32 bit word type as defined above). In other words, the
+ % \hs{RegisterState} type is a vector of 8 32-bit words. A fixed size
+ % vector is translated to a \VHDL\ array type.
+ \item[\bf{RangedWord}]
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.
implicitly zero. The main purpose of the \hs{RangedWord} type is to be
used as an index to a \hs{Vector}.
- \comment{TODO: Perhaps remove this example?} To define an index for
- the 8 element vector above, we would do:
+ % \comment{TODO: Perhaps remove this example?} To define an index for
+ % the 8 element vector above, we would do:
- \begin{code}
- type RegisterIndex = RangedWord D7
- \end{code}
+ % \begin{code}
+ % type RegisterIndex = RangedWord D7
+ % \end{code}
- Here, a type synonym \hs{RegisterIndex} is defined that is equal to
- the \hs{RangedWord} type constructor applied to the type \hs{D7}. In
- other words, this defines an unsigned word with values from
- 0 to 7 (inclusive). This word can be be used to index the
- 8 element vector \hs{RegisterState} above. This type is translated to
- the \texttt{unsigned} \VHDL type.
+ % Here, a type synonym \hs{RegisterIndex} is defined that is equal to
+ % the \hs{RangedWord} type constructor applied to the type \hs{D7}. In
+ % other words, this defines an unsigned word with values from
+ % 0 to 7 (inclusive). This word can be be used to index the
+ % 8 element vector \hs{RegisterState} above. This type is translated
+ % to the \texttt{unsigned} \VHDL type.
\end{xlist}
- \subsection{User-defined types}
+ \subsubsection{User-defined types}
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 type renamings with the \hs{newtype} keyword. \GHC\
+ keyword and datatype renamings 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. These are not currently supported.
Only an algebraic datatype declaration actually introduces a
completely new type, for which we provide the \VHDL\ translation
below. Type synonyms and renamings only define new names for
- existing types (where synonyms are completely interchangeable and
- renamings need explicit conversion). Therefore, these do not need
+ existing types, where synonyms are completely interchangeable and
+ renamings need explicit conversiona. Therefore, these do not need
any particular \VHDL\ translation, a synonym or renamed type will
just use the same representation as the original type. The
distinction between a renaming and a synonym does no longer matter
- in hardware and can be disregarded in the generated \VHDL.
-
- For algebraic types, we can make the following distinction:
+ in hardware and can be disregarded in the generated \VHDL. For algebraic
+ types, we can make the following distinction:
\begin{xlist}
\item[\bf{Single constructor}]
record-like structure. An example of such a type is the following pair
of integers:
-\begin{code}
-data IntPair = IntPair Int Int
-\end{code}
+ \begin{code}
+ data IntPair = IntPair Int Int
+ \end{code}
Haskell's builtin tuple types are also defined as single
constructor algebraic types and are translated according to this
As an example of a polymorphic function, consider the following
\hs{append} function's type:
- TODO: Use vectors instead of lists?
+ \comment{TODO: Use vectors instead of lists?}
\begin{code}
append :: [a] -> a -> [a]
how long it is. Polymorphism also plays an important role in most
higher order functions, as we will see in the next section.
- The previous example showed unconstrained polymorphism (TODO: How is
- this really called?): \hs{a} can have \emph{any} type. Furthermore,
- Haskell supports limiting the types of a type parameter to specific
- class of types. An example of such a type class is the \hs{Num}
- class, which contains all of Haskell's numerical types.
+ The previous example showed unconstrained polymorphism \comment{(TODO: How
+ is this really called?)}: \hs{a} can have \emph{any} type.
+ Furthermore,Haskell supports limiting the types of a type parameter to
+ specific class of types. An example of such a type class is the
+ \hs{Num} class, which contains all of Haskell's numerical types.
Now, take the addition operator, which has the following type:
In \CLaSH, unconstrained 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
+ 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 (since it is 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
+ \CLaSH\ does not support user-defined type classes, but does use some
of the builtin ones for its builtin functions (like \hs{Num} and
\hs{Eq}).
\end{code}
Finally, higher order arguments are not limited to just builtin
- functions, but any function defined in \CLaSH can have function
+ 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.
- TODO: Describe ALU example (no code)
+ \comment{TODO: Describe ALU example (no code)}
\subsection{State}
A very important concept in hardware it the concept of state. In a
A simple example is the description of an accumulator circuit:
\begin{code}
- acc :: Word -> State Word -> (State Word, Word)
- acc inp (State s) = (State s', outp)
+ macS a b (State c) = (State c', outp)
where
- outp = s + inp
- s' = outp
+ outp = mac a b c
+ c' = outp
\end{code}
+ \begin{figure}
+ \centerline{\includegraphics{mac-state}}
+ \caption{Stateful Multiply-Accumulate}
+ \label{img:mac-state}
+ \end{figure}
This approach makes the state of a function 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
projects / matthijs / master-project / dsd-paper.git / blobdiff