X-Git-Url: https://git.stderr.nl/gitweb?p=matthijs%2Fmaster-project%2Freport.git;a=blobdiff_plain;f=Chapters%2FHardwareDescription.tex;h=479dd400640b5dfa38de5a2c929d41ef79f75a54;hp=eab0a49bc0a0f2c26b75b559dec755b27b8c9356;hb=d196e984e8b30373485e136ac763b669d21c4751;hpb=ecb1b7d79982a225260129766fb3c97a62bd22e1 diff --git a/Chapters/HardwareDescription.tex b/Chapters/HardwareDescription.tex index eab0a49..479dd40 100644 --- a/Chapters/HardwareDescription.tex +++ b/Chapters/HardwareDescription.tex @@ -5,8 +5,6 @@ the implementation. The prototype implementation will be discussed in \in{chapter}[chap:prototype]. - \todo{Shortshort introduction to Cλash (Bit, Word, and, not, etc.)} - To translate Haskell to hardware, every Haskell construct needs a translation to \VHDL. There are often multiple valid translations possible. When faced with choices, the most obvious choice has been @@ -17,38 +15,33 @@ possible. \placeintermezzo{}{ - \defref{top level binder} - \defref{top level function} - \startframedtext[width=8cm,background=box,frame=no] + \defref{reading examples} + \startframedtext[width=9cm,background=box,frame=no] \startalignment[center] - {\tfa Top level binders and functions} + {\tfa Reading the examples} \stopalignment \blank[medium] - A top level binder is any binder (variable) that is declared in - the \quote{global} scope of a Haskell program (as opposed to a - binder that is bound inside a function. - - In Haskell, there is no sharp distinction between a variable and a - function: a function is just a variable (binder) with a function - type. This means that a top level function is just any top level - binder with a function type. - - As an example, consider the following Haskell snippet: - - \starthaskell - foo :: Int -> Int - foo x = inc x - where - inc = \y -> y + 1 - \stophaskell - - Here, \hs{foo} is a top level binder, whereas \hs{inc} is a - function (since it is bound to a lambda extraction, indicated by - the backslash) but is not a top level binder or function. Since - the type of \hs{foo} is a function type, namely \hs{Int -> Int}, - it is also a top level function. + In this thesis, a lot of functional code will be presented. Part of this + will be valid Cλash code, but others will just be small Haskell or Core + snippets to illustrate a concept. + + In these examples, some functions and types will be used, without + properly defining every one of them. These functions (like \hs{and}, + \hs{not}, \hs{add}, \hs{+}, etc.) and types (like \hs{Bit}, \hs{Word}, + \hs{Bool}, etc.) are usually pretty self-explanatory. + + The special type \hs{[t]} means \quote{list of \hs{t}'s}, where \hs{t} + can be any other type. + + Of particular note is the use of the \hs{::} operator. It is used in + Haskell to explicitly declare the type of function or let binding. In + these examples and the text, we will occasionally use this operator to + show the type of arbitrary expressions, even where this would not + normally be valid. Just reading the \hs{::} operator as \quote{and also + note that \emph{this} expression has \emph{this} type} should work out. \stopframedtext } + In this chapter we describe how to interpret a Haskell program from a hardware perspective. We provide a description of each Haskell language element that needs translation, to provide a clear picture of what is @@ -78,8 +71,8 @@ application and the corresponding architecture. \startbuffer[And3] --- | A simple function that returns --- conjunction of three bits +-- A simple function that returns +-- conjunction of three bits and3 :: Bit -> Bit -> Bit -> Bit and3 a b c = and (and a b) c \stopbuffer @@ -115,12 +108,68 @@ and3 a b c = and (and a b) c ncline(andb)(out); \stopuseMPgraphic - \placeexample[here][ex:And3]{Simple three input and gate.} + \startbuffer[And3VHDL] + entity and3Component_0 is + port (\azMyG2\ : in std_logic; + \bzMyI2\ : in std_logic; + \czMyK2\ : in std_logic; + \foozMySzMyS2\ : out std_logic; + clock : in std_logic; + resetn : in std_logic); + end entity and3Component_0; + + + architecture structural of and3Component_0 is + signal \argzMyMzMyM2\ : std_logic; + begin + \argzMyMzMyM2\ <= \azMyG2\ and \bzMyI2\; + + \foozMySzMyS2\ <= \argzMyMzMyM2\ and \czMyK2\; + end architecture structural; + \stopbuffer + + \placeexample[][ex:And3]{Simple three input and gate.} \startcombination[2*1] {\typebufferhs{And3}}{Haskell description using function applications.} {\boxedgraphic{And3}}{The architecture described by the Haskell description.} \stopcombination + \placeexample[][ex:And3VHDL]{\VHDL\ generated for \hs{and3} from \in{example}[ex:And3]} + {\typebuffervhdl{And3VHDL}} + + \placeintermezzo{}{ + \defref{top level binder} + \defref{top level function} + \startframedtext[width=8cm,background=box,frame=no] + \startalignment[center] + {\tfa Top level binders and functions} + \stopalignment + \blank[medium] + A top level binder is any binder (variable) that is declared in + the \quote{global} scope of a Haskell program (as opposed to a + binder that is bound inside a function. + + In Haskell, there is no sharp distinction between a variable and a + function: a function is just a variable (binder) with a function + type. This means that a top level function is just any top level + binder with a function type. + + As an example, consider the following Haskell snippet: + + \starthaskell + foo :: Int -> Int + foo x = inc x + where + inc = \y -> y + 1 + \stophaskell + + Here, \hs{foo} is a top level binder, whereas \hs{inc} is a + function (since it is bound to a lambda extraction, indicated by + the backslash) but is not a top level binder or function. Since + the type of \hs{foo} is a function type, namely \hs{Int -> Int}, + it is also a top level function. + \stopframedtext + } \section{Choice} Although describing components and connections allows us to describe a lot of hardware designs already, there is an obvious thing missing: choice. We @@ -144,8 +193,22 @@ and3 a b c = and (and a b) c simply be translated to a conditional assignment, where the conditions use equality comparisons against the constructors in the \hs{case} expressions. + In \in{example}[ex:CaseInv] a simple \hs{case} expression is shown, + scrutinizing a boolean value. The corresponding architecture has a + comparator to determine which of the constructors is on the \hs{in} + input. There is a multiplexer to select the output signal. The two options + for the output signals are just constants, but these could have been more + complex expressions (in which case also both of them would be working in + parallel, regardless of which output would be chosen eventually). + + If we would translate a Boolean to a bit value, we could of course remove + the comparator and directly feed 'in' into the multiplexer (or even use an + inverter instead of a multiplexer). However, we will try to make a + general translation, which works for all possible \hs{case} expressions. + Optimizations such as these are left for the \VHDL\ synthesizer, which + handles them very well. + \placeintermezzo{}{ - \defref{substitution notation} \startframedtext[width=8cm,background=box,frame=no] \startalignment[center] {\tfa Arguments / results vs. inputs / outputs} @@ -165,20 +228,23 @@ and3 a b c = and (and a b) c \stopframedtext } - In \in{example}[ex:CaseInv] a simple \hs{case} expression is shown, - scrutinizing a boolean value. The corresponding architecture has a - comparator to determine which of the constructors is on the \hs{in} - input. There is a multiplexer to select the output signal. The two options - for the output signals are just constants, but these could have been more - complex expressions (in which case also both of them would be working in - parallel, regardless of which output would be chosen eventually). - - If we would translate a Boolean to a bit value, we could of course remove - the comparator and directly feed 'in' into the multiplexer (or even use an - inverter instead of a multiplexer). However, we will try to make a - general translation, which works for all possible \hs{case} expressions. - Optimizations such as these are left for the \VHDL\ synthesizer, which - handles them very well. + 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. + + The architecture described by \in{example}[ex:PatternInv] is of course the + same one as the one in \in{example}[ex:CaseInv]. The general interpretation + of pattern matching is also similar to that of \hs{case} expressions: generate + hardware for each of the clauses (like each of the clauses of a \hs{case} + expression) and connect them to the function output through (a number of + nested) multiplexers. These multiplexers are driven by comparators and + other logic, that check each pattern in turn. + + In these examples we have seen only binary case expressions and pattern + matches (\ie, with two alternatives). In practice, case expressions can + choose between more than two values, resulting in a number of nested + multiplexers. \startbuffer[CaseInv] inv :: Bool -> Bool @@ -220,17 +286,32 @@ and3 a b c = and (and a b) c ncline(trueout)(mux) "posB(inpb)"; ncline(mux)(out) "posA(out)"; \stopuseMPgraphic + + \startbuffer[CaseInvVHDL] + entity invComponent_0 is + port (\xzAMo2\ : in boolean; + \reszAMuzAMu2\ : out boolean; + clock : in std_logic; + resetn : in std_logic); + end entity invComponent_0; + + + architecture structural of invComponent_0 is + begin + \reszAMuzAMu2\ <= false when \xzAMo2\ = true else + true; + end architecture structural; + \stopbuffer - \placeexample[here][ex:CaseInv]{Simple inverter.} + \placeexample[][ex:CaseInv]{Simple inverter.} \startcombination[2*1] {\typebufferhs{CaseInv}}{Haskell description using a Case expression.} {\boxedgraphic{CaseInv}}{The architecture described by the Haskell description.} \stopcombination - 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. + \placeexample[][ex:CaseInvVHDL]{\VHDL\ generated for \hs{inv} from + \in{example}[ex:CaseInv] and \in{example}[ex:PatternInv]} + {\typebuffervhdl{CaseInvVHDL}} \startbuffer[PatternInv] inv :: Bool -> Bool @@ -238,23 +319,10 @@ and3 a b c = and (and a b) c inv False = True \stopbuffer - \placeexample[here][ex:PatternInv]{Simple inverter using pattern matching. + \placeexample[][ex:PatternInv]{Simple inverter using pattern matching. Describes the same architecture as \in{example}[ex:CaseInv].} {\typebufferhs{PatternInv}} - The architecture described by \in{example}[ex:PatternInv] is of course the - same one as the one in \in{example}[ex:CaseInv]. The general interpretation - of pattern matching is also similar to that of \hs{case} expressions: generate - hardware for each of the clauses (like each of the clauses of a \hs{case} - expression) and connect them to the function output through (a number of - nested) multiplexers. These multiplexers are driven by comparators and - other logic, that check each pattern in turn. - - In these examples we have seen only binary case expressions and pattern - matches (\ie, with two alternatives). In practice, case expressions can - choose between more than two values, resulting in a number of nested - multiplexers. - \section{Types} Translation of two most basic functional concepts has been discussed: function application and choice. Before looking further @@ -514,7 +582,7 @@ and3 a b c = and (and a b) c and the corresponding architecture. \startbuffer[Quadruple] --- | Multiply the input word by four. +-- Multiply the input word by four. quadruple :: Word -> Word quadruple n = mul (mul n) where @@ -549,7 +617,7 @@ quadruple n = mul (mul n) ncline(mulb)(out); \stopuseMPgraphic - \placeexample[here][ex:Quadruple]{Simple three port and.} + \placeexample[][ex:Quadruple]{Simple three port and.} \startcombination[2*1] {\typebufferhs{Quadruple}}{Haskell description using function applications.} {\boxedgraphic{Quadruple}}{The architecture described by the Haskell description.} @@ -852,7 +920,7 @@ acc in = out \stopuseMPgraphic - \placeexample[here][ex:DelayAcc]{Simple accumulator architecture.} + \placeexample[][ex:DelayAcc]{Simple accumulator architecture.} \startcombination[2*1] {\typebufferhs{DelayAcc}}{Haskell description using streams.} {\boxedgraphic{DelayAcc}}{The architecture described by the Haskell description.} @@ -887,7 +955,7 @@ acc in s = (s', out) s' = out \stopbuffer - \placeexample[here][ex:ExplicitAcc]{Simple accumulator architecture.} + \placeexample[][ex:ExplicitAcc]{Simple accumulator architecture.} \startcombination[2*1] {\typebufferhs{ExplicitAcc}}{Haskell description using explicit state arguments.} % Picture is identical to the one we had just now. @@ -1045,6 +1113,23 @@ acc in s = (s', out) cycle (at best, we could generate hardware that needs an infinite number of cycles to complete). + \placeintermezzo{}{ + \startframedtext[width=8cm,background=box,frame=no] + \startalignment[center] + {\tfa \hs{null}, \hs{head} and \hs{tail}} + \stopalignment + \blank[medium] + The functions \hs{null}, \hs{head} and \hs{tail} are common list + functions in Haskell. The \hs{null} function simply checks if a list is + empty. The \hs{head} function returns the first element of a list. The + \hs{tail} function returns containing everything \emph{except} the first + element of a list. + + In Cλash, there are vector versions of these functions, which do exactly + the same. + \stopframedtext + } + However, most recursive definitions will describe finite recursion. This is because the recursive call is done conditionally. There is usually a \hs{case} expression where at least one alternative does not contain