%
\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,
\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}}
+c.p.r.baaij@@utwente.nl, matthijs@@stdin.nl, j.kuper@@utwente.nl}
+% \thanks{Supported through FP7 project: S(o)OS (248465)}
+}
% \and
% \IEEEauthorblockN{Homer Simpson}
% \IEEEauthorblockA{Twentieth Century Fox\\
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
-shown to work for non-trivial descriptions. \CLaSH\ has been able to
+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 shown to work for non-trivial descriptions. \CLaSH\ has been able to
successfully translate the functional description of a streaming reduction
circuit~\cite{reductioncircuit} for floating point numbers.
compiler. The \CLaSH\ compiler has generic translation rules to
translated the user-defined types described below.
- The \CLaSH compiler is able to infer unspecified types,
+ The \CLaSH\ compiler is able to infer unspecified types,
meaning that a developer does not have to annotate every function with a
- type signature (though it is good practice to do so anyway).
+ type signature (even if it is good practice to do so).
% Translation of two most basic functional concepts has been
% discussed: function application and choice. Before looking further
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. Note that this is
a notation used in this paper only, vectors are slightly more
- elaborate in real \CLaSH programs.
+ verbose in real \CLaSH\ descriptions.
% The state type of an 8 element register bank would then for example
% be:
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 properties that have a direct
-translation. The second stage of the compiler, the \emph{normalization} phase
+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
\VHDL\ resembles an actual netlist description and not idiomatic \VHDL.
\section{Use cases}
-
-\subsection{FIR Filter}
\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:
\end{code}
Where the vector \hs{hs} contains the \acro{FIR} coefficients and the vector
-\hs{xs} contains the latest input sample in front and older samples behind.
-The code for the shift (\hs{>>}) operator that adds the new input sample
+\hs{xs} contains the previous input sample in front and older samples behind.
+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:
+oldest sample, is shown below:
\begin{code}
x >> xs = x +> init xs
\subsection{Higher order CPU}
\begin{code}
-fu :: (a -> a -> a)
- -> [a | n]
- -> (Index (n - 1), Index (n - 1))
- -> a
- -> (a, a)
-fu op inputs (addr1, addr2) (State out) =
- (State out', out)
+fu op inputs (addr1, addr2) = regIn
where
- in1 = inputs!addr1
- in2 = inputs!addr2
- out' = op in1 in2
+ in1 = inputs!addr1
+ in2 = inputs!addr2
+ regIn = op in1 in2
\end{code}
\begin{code}
-type CpuState = State [Word | 4]
-
-cpu :: Word
- -> [(Index 6, Index 6) | 4]
- -> CpuState
- -> (CpuState, Word)
-cpu input addrs (State fuss) = (State fuss', out)
+cpu :: State [Word | 4] -> Word
+ -> [(Index 6, Index 6) | 4]
+ -> (State [Word | 4], Word)
+cpu (State regsOut) input addrs = (State regsIn, out)
where
- fures = [ fu const inputs (addrs!0) (fuss!0)
- , fu (+) inputs (addrs!1) (fuss!1)
- , fu (-) inputs (addrs!2) (fuss!2)
- , fu (*) inputs (addrs!3) (fuss!3)
- ]
- (fuss', outputs) = unzip fures
- inputs = 0 +> (1 +> (input +> outputs))
- out = head outputs
+ regsIn = [ fu const inputs (addrs!0)
+ , fu (+) inputs (addrs!1)
+ , fu (-) inputs (addrs!2)
+ , fu (*) inputs (addrs!3)
+ ]
+ inputs = 0 +> (1 +> (input +> regsOut))
+ out = head regsOut
\end{code}
\section{Related work}
+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
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
+be translated to \VHDL\ and that the translated description can then 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
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 support for generics has been extended to types, allowing a developer to describe
-polymorphic components. Note that those types still require an explicit
-generic map, whereas types can be automatically inferred in \CLaSH.
+exemplified by the new \VHDL-2008 standard~\cite{VHDL2008}. \VHDL-2008 support
+for generics has been extended to types and subprograms, allowing a developer 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, and thus the synthesis of polymorphic types and function-valued arguments.
% Wired~\cite{Wired},, T-Ruby~\cite{T-Ruby}, Hydra~\cite{Hydra}.
%
\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 that are well suited to describe the conditional assignments in control-oriented hardware. 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 an actual circuit description; a feature the embedded languages do not offer.
+\section{Future Work}
% 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
projects / matthijs / master-project / dsd-paper.git / blobdiff