X-Git-Url: https://git.stderr.nl/gitweb?p=matthijs%2Fmaster-project%2Fdsd-paper.git;a=blobdiff_plain;f=c%CE%BBash.lhs;h=447e3ac171045a47d42c71f5f61853a4d6f07e18;hp=9fb964773a948b737ee7055d4e86500b3202a3c5;hb=c8e108df889f5926bb6d5aa2e9a506a24df752b6;hpb=8cf5b5c041beee1dd39678bc70b7ec934ecc4d98 diff --git "a/c\316\273ash.lhs" "b/c\316\273ash.lhs" index 9fb9647..447e3ac 100644 --- "a/c\316\273ash.lhs" +++ "b/c\316\273ash.lhs" @@ -65,6 +65,7 @@ % \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, @@ -398,7 +399,9 @@ \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 the FP7 project: S(o)OS (248465)} +} % \and % \IEEEauthorblockN{Homer Simpson} % \IEEEauthorblockA{Twentieth Century Fox\\ @@ -449,14 +452,21 @@ c.p.r.baaij@@utwente.nl, matthijs@@stdin.nl, j.kuper@@utwente.nl}} \begin{abstract} %\boldmath \CLaSH\ is a functional hardware description language that borrows both its -syntax and semantics from the functional programming language Haskell. Circuit -descriptions can be translated to synthesizable VHDL using the prototype -\CLaSH\ compiler. As the circuit descriptions are made in plain Haskell, -simulations can also be compiled by a Haskell compiler. - -The use of polymorphism and higher-order functions allow a circuit designer to -describe more abstract and general specifications than are possible in the -traditional hardware description languages. +syntax and semantics from the functional programming language Haskell. Due to +the abstraction and generality offered by polymorphism and higher-order +functions, a circuit designer can describe circuits in a more natural way than +he could in the traditional hardware description languages. + +Circuit descriptions can be translated to synthesizable VHDL using the +prototype \CLaSH\ compiler. As the circuit descriptions, simulation code, and +test input are plain Haskell, complete simulations can be compiled to an +executable binary by a Haskell compiler allowing high-speed simulation and +analysis. + +Stateful descriptions are supported by explicitly making the current state an +argument of the function, and the updated state part of the result. In this +sense, the descriptions made in \CLaSH\ are the combinational parts of a mealy +machine. \end{abstract} % IEEEtran.cls defaults to using nonbold math in the Abstract. % This preserves the distinction between vectors and scalars. However, @@ -1190,6 +1200,27 @@ the vectors of the \acro{FIR} code to a length of 4, is depicted in \end{figure} \subsection{Higher order CPU} +The following simple CPU is an example of user-defined higher order +functions and pattern matching. The CPU consists of four function units, +of which three have a fixed function and one can perform some less +common operations. + +The CPU contains a number of data sources, represented by the horizontal +lines in figure TODO:REF. These data sources offer the previous outputs +of each function units, along with the single data input the cpu has and +two fixed intialization values. + +Each of the function units has both its operands connected to all data +sources, and can be programmed to select any data source for either +operand. In addition, the leftmost function unit has an additional +opcode input to select the operation it performs. Its output is also the +output of the entire cpu. + +Looking at the code, the function unit is the most simple. It arranges +the operand selection for the function unit. Note that it does not +define the actual operation that takes place inside the function unit, +but simply accepts the (higher order) argument "op" which is a function +of two arguments that defines the operation. \begin{code} fu op inputs (addr1, addr2) = regIn @@ -1199,20 +1230,59 @@ fu op inputs (addr1, addr2) = regIn regIn = op in1 in2 \end{code} +The multiop function defines the operation that takes place in the +leftmost function unit. It is essentially a simple three operation alu +that makes good use of pattern matching and guards in its description. +The \hs{shift} function used here shifts its first operand by the number +of bits indicated in the second operand, the \hs{xor} function produces +the bitwise xor of its operands. + +\begin{code} +data Opcode = Shift | Xor | Equal + +multiop :: Opcode -> Word -> Word -> Word +multiop opc a b = case opc of + Shift -> shift a b + Xor -> xor a b + Equal | a == b -> 1 + | otherwise -> 0 +\end{code} + +The cpu function ties everything together. It applies the \hs{fu} +function four times, to create a different function unit each time. The +first application is interesting, because it does not just pass a +function to \hs{fu}, but a partial application of \hs{multiop}. This +shows how the first funcition unit effectively gets an extra input, +compared to the others. + +The vector \hs{inputs} is the set of data sources, which is passed to +each function unit for operand selection. The cpu also receives a vector +of address pairs, which are used by each function unit to select their +operand. The application of the function units to the \hs{inputs} and +\hs{addrs} arguments seems quite repetive and could be rewritten to use +a combination of the \hs{map} and \hs{zipwith} functions instead. +However, the prototype does not currently support working with lists of +functions, so the more explicit version of the code is given instead). + \begin{code} -cpu :: Word -> [(Index 6, Index 6) | 4] - -> State [Word | 4] -> (State [Word | 4], Word) -cpu input addrs (State fuss) = (State fuss', out) +type CpuState = State [Word | 4] + +cpu :: CpuState -> Word -> [(Index 6, Index 6) | 4] + -> Opcode -> (CpuState, Word) +cpu (State s) input addrs opc = (State s', out) where - fuss' = [ 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) + s' = [ fu (multiop opc) inputs (addrs!0) + , fu add inputs (addrs!1) + , fu sub inputs (addrs!2) + , fu mul inputs (addrs!3) ] - inputs = 0 +> (1 +> (input +> fuss)) - out = head fuss + inputs = 0 +> (1 +> (input +> s)) + out = head s' \end{code} +Of course, this is still a simple example, but it could form the basis +of an actual design, in which the same techniques can be reused. + \section{Related work} This section describes the features of existing (functional) hardware description languages and highlights the advantages that this research has @@ -1272,11 +1342,7 @@ mentioned in this 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 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. There are -also no (generally available) \VHDL\ synthesis tools that currently support -the \VHDL-2008 standard, and thus the synthesis of polymorphic types. +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}. % @@ -1369,10 +1435,39 @@ the \VHDL-2008 standard, and thus the synthesis of polymorphic types. \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, such as patter matching, 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 the +actual circuit description; a feature the embedded hardware description +languages do not offer. + +\section{Future Work} +The choice of describing state explicitly as extra arguments and results can +be seen as a mixed blessing. Even though the description that use state are +usually very clear, one finds that dealing with unpacking, passing, receiving +and repacking can become tedious and even error-prone, especially in the case +of sub-states. Removing this boilerplate, or finding a more suitable +abstraction mechanism would make \CLaSH\ easier to use. + +The transformations in normalization phase of the prototype compiler were +developed in an ad-hoc manner, which makes the existence of many desirable +properties unclear. Such properties include whether the complete set of +transformations will always lead to a normal form or if the normalization +process always terminates. Though various use cases suggests that these +properties usually hold, they have not been formally proven. A systematic +approach to defining the set of transformations allows one to proof that the +earlier mentioned properties do indeed exist. % conference papers do not normally have an appendix @@ -1386,7 +1481,7 @@ The conclusion goes here. % number - used to balance the columns on the last page % adjust value as needed - may need to be readjusted if % the document is modified later -%\IEEEtriggeratref{8} +\IEEEtriggeratref{14} % The "triggered" command can be changed if desired: %\IEEEtriggercmd{\enlargethispage{-5in}}