X-Git-Url: https://git.stderr.nl/gitweb?p=matthijs%2Fmaster-project%2Fdsd-paper.git;a=blobdiff_plain;f=c%CE%BBash.lhs;h=a0ccb8e02769951d18c1ca59f3069a8938c65dcf;hp=25ec7a281aed0e120a9d7c3d6feb90a62a4b6cb7;hb=432416d4f3cb67cdb0ae332d01a78dae6328d0f5;hpb=659a450d0ca1f164379f7cf851bcc5a04b31740f diff --git "a/c\316\273ash.lhs" "b/c\316\273ash.lhs" index 25ec7a2..a0ccb8e 100644 --- "a/c\316\273ash.lhs" +++ "b/c\316\273ash.lhs" @@ -63,6 +63,7 @@ % 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. % @@ -93,9 +94,6 @@ - - - % *** CITATION PACKAGES *** % \usepackage{cite} @@ -122,7 +120,7 @@ % *** GRAPHICS RELATED PACKAGES *** % \ifCLASSINFOpdf - % \usepackage[pdftex]{graphicx} + \usepackage[pdftex]{graphicx} % declare the path(s) where your graphic files are % \graphicspath{{../pdf/}{../jpeg/}} % and their extensions so you won't have to specify these with @@ -371,6 +369,12 @@ \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 @@ -465,82 +469,105 @@ The abstract goes here. \section{Introduction} Hardware description languages has allowed the productivity of hardware engineers to keep pace with the development of chip technology. Standard -Hardware description languages, like \VHDL\ and Verilog, allowed an engineer -to describe circuits using a programming language. These standard languages -are very good at describing detailed hardware properties such as timing -behavior, but are generally cumbersome in expressing higher-level -abstractions. These languages also tend to have a complex syntax and a lack of -formal semantics. To overcome these complexities, and raise the abstraction -level, a great number of approaches based on functional languages has been -proposed \cite{T-Ruby,Hydra,HML2,Hawk1,Lava,ForSyDe1,Wired,reFLect}. The idea -of using functional languages started in the early 1980s \cite{Cardelli1981, -muFP,DAISY,FHDL}, a time which also saw the birth of the currently popular -hardware description languages such as \VHDL. What gives functional languages -as hardware description languages their merits is the fact that basic -combinatorial circuits are equivalent to mathematical function, and that -functional languages lend themselves very well to describe and compose these -mathematical functions. +Hardware description languages, like \VHDL~\cite{VHDL2008} and +Verilog~\cite{Verilog}, allowed an engineer to describe circuits using a +programming language. These standard languages are very good at describing +detailed hardware properties such as timing behavior, but are generally +cumbersome in expressing higher-level abstractions. In an attempt to raise the +abstraction level of the descriptions, a great number of approaches based on +functional languages has been proposed \cite{T-Ruby,Hydra,HML2,Hawk1,Lava, +ForSyDe1,Wired,reFLect}. The idea of using functional languages for hardware +descriptions started in the early 1980s \cite{Cardelli1981, muFP,DAISY,FHDL}, +a time which also saw the birth of the currently popular hardware description +languages such as \VHDL. The merit of using a functional language to describe +hardware comes from the fact that basic combinatorial circuits are equivalent +to mathematical functions and that functional languages are very good at +describing and composing mathematical functions. In an attempt to decrease the amount of work involved with creating all the required tooling, such as parsers and type-checkers, many functional hardware description languages are embedded as a domain specific language inside the -functional language Haskell \cite{Hydra,Hawk1,Lava,ForSyDe1,Wired}. What this -means is that a developer is given a library of Haskell functions and types -that together form the language primitives of the domain specific language. -Using these functions, the designer does not only describes a circuit, but -actually builds a large domain-specific datatype which can be further -processed by an embedded compiler. This compiler actually runs in the same -environment as the description; as a result compile-time and run-time become -hard to define, as the embedded compiler is usually compiled by the same -Haskell compiler as the circuit description itself. +functional language Haskell \cite{Hydra,Hawk1,Lava,ForSyDe1,Wired}. This +means that a developer is given a library of Haskell~\cite{Haskell} functions +and types that together form the language primitives of the domain specific +language. As a result of how the signals are modeled and abstracted, the +functions used to describe a circuit also build a large domain-specific +datatype (hidden from the designer) which can be further processed by an +embedded compiler. This compiler actually runs in the same environment as the +description; as a result compile-time and run-time become hard to define, as +the embedded compiler is usually compiled by the same Haskell compiler as the +circuit description itself. The approach taken in this research is not to make another domain specific -language embedded in Haskell, but to use (a subset) of the Haskell language -itself to be used as hardware description language. By taking this approach, -we can capture certain language constructs, such as Haskell's choice elements -(if-statement, case-statment, etc.), which are not available in the functional -hardware description languages that are embedded in Haskell. As far as the -authors know, such extensive support for choice-elements is new in the domain -of functional hardware description language. As the hardware descriptions are -plain Haskell functions, these descriptions can be compiled for simulation -using using the optimizing Haskell compiler \GHC. +language embedded in Haskell, but to use (a subset of) the Haskell language +itself for the purpose of describing hardware. By taking this approach, we can +capture certain language constructs, such as Haskell's choice elements +(if-constructs, case-constructs, pattern matching, etc.), which are not +available in the functional hardware description languages that are embedded +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 language. As the hardware descriptions are plain Haskell +functions, these descriptions can be compiled for simulation using using the +optimizing Haskell compiler \GHC. + +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. The functions describe the behavior of the hardware between +clock cycles, as such, only synchronous systems can be described. Many +functional hardware description models 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. Like the standard hardware description languages, descriptions made in a -functional hardware description languages must eventually be converted into a -netlist. This research also features an a prototype translater 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 optimizing \VHDL\ synthesis tools. +functional hardware description language must eventually be converted into a +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. \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 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 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} - -\comment{TODO: Pretty picture} + 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{Choices} Although describing components and connections allows describing a @@ -591,7 +618,17 @@ mac a b c = add (mul a b) c sumif _ _ _ = 0 \end{code} - \comment{TODO: Pretty picture} + \begin{figure} + \centerline{\includegraphics{choice-ifthenelse}} + \caption{Choice - \emph{if-then-else}} + \label{img:choice} + \end{figure} + + \begin{figure} + \centerline{\includegraphics{choice-case}} + \caption{Choice - \emph{case-statement / pattern matching}} + \label{img:choice} + \end{figure} \subsection{Types} Translation of two most basic functional concepts has been @@ -605,7 +642,7 @@ mac a b c = add (mul a b) c 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 + 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. @@ -712,7 +749,7 @@ data IntPair = IntPair Int Int Haskell's builtin tuple types are also defined as single constructor algebraic types and are translated according to this - rule by the \CLaSH compiler. These types are translated to \VHDL\ + rule by the \CLaSH\ compiler. These types are translated to \VHDL\ record types, with one field for every field in the constructor. \item[\bf{No fields}] Algebraic datatypes with multiple constructors, but without any @@ -811,7 +848,7 @@ section. 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 has +exemplified by the new \VHDL-2008 standard~\cite{VHDL2008}. \VHDL-2008 has support to specify types as generics, thus allowing a developer to describe polymorphic components. Note that those types still require an explicit generic map, whereas type-inference and type-specialization are implicit in