FILE = clash-haskell09
-LHS2TEX = lhs2TeX -v --poly
+LHS2TEX = lhs2TeX -v --tt
LATEXMK = latexmk -pdf
RM = rm -f
RSVG = rsvg-convert --format=pdf
LHSRCS = \
introduction.lhs \
matthijs/introduction.lhs \
- christiaan/introduction.lhs
+ christiaan/introduction.lhs \
+ christiaan/fir.lhs \
+ christiaan/dotproduct.lhs \
+ christiaan/structure.lhs \
+ christiaan/reductioncircuit.lhs \
+ christiaan/recursion.lhs
LHFORMATS = \
talk.fmt
--- /dev/null
+%include talk.fmt
+\subsubsection{Dot Product}
+\begin{frame}
+ \frametitle{Dot Product}
+ \[
+ y = \overrightarrow x \bullet \overrightarrow h
+ \]
+\end{frame}
+
+\begin{frame}
+ \frametitle{Dot Product}
+ \[
+ y = \overrightarrow x \bullet \overrightarrow h
+ \]
+ \[
+ \overrightarrow x \bullet \overrightarrow h = \sum\nolimits_{i = 1}^n {a_1 \cdot b_1 + a_2 \cdot b_2 + \ldots + a_n \cdot b_n }
+ \]
+\end{frame}
+
+\begin{frame}
+ \frametitle{Dot Product}
+ \begin{itemize}
+ \item Two steps to define: \\
+ \[
+ \overrightarrow x \bullet \overrightarrow h = \sum\nolimits_{i = 1}^n {a_1 \cdot b_1 + a_2 \cdot b_2 + \ldots + a_n \cdot b_n }
+ \]
+ \begin{itemize}
+ \item \emph{Pairwise Multiplication}: \\
+ \begin{verbatim}
+ zipwith (*) xs hs =
+ < x0*h0, x1*h1, x(n-1)*h(n-1)>
+ \end{verbatim}
+ \item \emph{Summation}: \\
+ \begin{verbatim}
+ foldl (+) 0 zs =
+ (..((0+z0)+z1)+..+z(n-1))
+ \end{verbatim}
+ \end{itemize}
+ \end{itemize}
+\end{frame}
+
+\begin{frame}
+ \frametitle{Dot Product}
+ \begin{itemize}
+ \item Two steps to define: \\
+ \[
+ \overrightarrow x \bullet \overrightarrow h = \sum\nolimits_{i = 1}^n {a_1 \cdot b_1 + a_2 \cdot b_2 + \ldots + a_n \cdot b_n }
+ \]
+ \begin{itemize}
+ \item \emph{Combine the two}: \\
+ \begin{verbatim}
+ xs ** hs = foldl (+) 0 (zipWith (*) xs hs)
+ \end{verbatim}
+ \end{itemize}
+ \end{itemize}
+\end{frame}
\ No newline at end of file
--- /dev/null
+%include talk.fmt
+\subsection{FIR Filter}
+
+\begin{frame}
+ \frametitle{Example: FIR Filter}
+ \begin{itemize}
+ \item FIR Filters, and digital filters in general are essential components in radio's, receivers, and cellphones.
+ \item Equation for a FIR Filter: \\
+ \[
+ y_t = \sum\nolimits_{i = 0}^{n - 1} {x_{t - i} \cdot h_i }
+ \]
+ \end{itemize}
+\end{frame}
+
+\begin{frame}
+ \frametitle{FIR Filter}
+ \[
+ y_t = \sum\nolimits_{i = 0}^{n - 1} {x_{t - i} \cdot h_i }
+ \]
+\end{frame}
+
+\input{christiaan/dotproduct}
+
+\begin{frame}
+ \frametitle{FIR Filter}
+ \[
+ y_t = \sum\nolimits_{i = 0}^{n - 1} {x_{t - i} \cdot h_i }
+ \] \\
+ \begin{verbatim}
+ fir (State pxs) x = (pxs**hs, State (pxs<++x))
+ where hs = $(vectorTH [2::Int16,3,-2,4])
+ \end{verbatim}
+ \centerline{\begin{tabular}{rl}
+ |pxs| & Previous x's (state)\\
+ |x| & New input value\\
+ |pxs <++ x| & Remember new |x|, remove oldest\\
+ |pxs ** hs| & Output
+ \end{tabular}}
+
+\end{frame}
+
+\begin{frame}
+ \frametitle{FIR Filter}
+ \centerline{\Huge{Demo}}
+\end{frame}
+
+\begin{frame}
+ \frametitle{Synthesized Output}
+ \vspace{-0.8em}
+ \begin{figure}
+ \centerline{\includegraphics[width=\paperwidth,trim=9mm 4cm 14mm 4cm, clip=true]{fir0.png}}
+ \end{figure}
+\end{frame}
+
+\begin{frame}
+ \frametitle{Synthesized Output}
+ \vspace{-0.8em}
+ \begin{figure}
+ \centerline{\includegraphics[width=\paperwidth,trim=9mm 4cm 16.5cm 4cm, clip=true]{fir1.png}}
+ \end{figure}
+\end{frame}
+
+\begin{frame}
+ \frametitle{Synthesized Output}
+ \vspace{-0.8em}
+ \begin{figure}
+ \centerline{\includegraphics[width=\paperwidth,trim=3cm 4cm 4cm 4cm, clip=true]{fir2.png}}
+ \end{figure}
+\end{frame}
\ No newline at end of file
\author{Christiaan Baaij}
\date{December 14, 2009}
-\frame{\titlepage \setcounter{framenumber}{1}}
\ No newline at end of file
+\section{Presentation Christiaan}
+\frame{\titlepage \setcounter{framenumber}{1}}
+
+\input{christiaan/fir}
+\input{christiaan/structure}
+\input{christiaan/reductioncircuit}
+\input{christiaan/recursion}
+
+\subsection{Questions}
+\frame{\vspace{2cm}\centerline{\Huge{Questions?}}}
\ No newline at end of file
--- /dev/null
+\subsection{Recursion}
+%include talk.fmt
+\frame{
+\frametitle{Future Work: Recursion}
+\begin{itemize}
+ \item The most pressing future work is to support recursive functions.
+ \item Partially explored solution: static loop unrolling
+ \item Unexplored solution: Haskell language extensions, new source language
+\end{itemize}
+}
+
+\subsubsection{Static loop unrolling}
+\frame{
+\frametitle{Static loop unrolling}
+\begin{itemize}
+ \item Unroll, and simplify recursive definitions at compile time.
+ \item Explored solution: Unrolling number-guided recursive functions using Template Haskell
+\end{itemize}
+}
+
+\frame{
+\frametitle{Template Haskell}
+\begin{itemize}
+ \item Template Haskell allows for compile-time inspection, construction, and manipulation of Haskell code.
+ \item All these functions are expressible in normal Haskell
+\end{itemize}
+}
+
+\frame{
+\frametitle{Tree Adder}
+\begin{verbatim}
+$(do
+ [typ, _] <- [d|{
+treeSum :: Vector D8 (SizedWord D8) -> SizedWord D8;
+treeSum xs = undefined
+ }|]
+ [func] <- [d|{
+treeSum i xs | i < 1 = head xs
+ | otherwise = let (a,b) = split xs
+ in (treeSum (i-1) a) +
+ (treeSum (i-1) b)
+ }|]
+ let func' = unroll Nothing 0 (IntegerL 3) funct
+ return [typ,func']
+)
+\end{verbatim}
+}
+
+\begin{frame}
+ \frametitle{Unrolled tree adder}
+ \begin{figure}
+ \includegraphics[height=5cm]{treeadder}
+ \end{figure}
+\end{frame}
+
+\subsubsection{Input Language}
+\frame{
+\frametitle{Input Language}
+\begin{itemize}
+ \item New source language: One of the problems is that Haskell does not properly support dependent types. Investigate languages with dependent type systems.
+ \item Haskell extentions: Invariant descriptions at the type-level.
+\end{itemize}
+}
\ No newline at end of file
--- /dev/null
+\subsection{Restrictions}
+%include talk.fmt
+\frame{
+\frametitle{Too Restrictive?}
+\begin{itemize}
+ \item Is CλasH too restrictive given the fact that a designer can currently not define his own vector transformations, or recursive functions for that matter?
+\end{itemize}
+}
+
+\frame{
+\frametitle{Too Restrictive?}
+\begin{itemize}
+ \item There is certainly room to increase expressivity. But we can already describe non-trivial design in CλasH.
+ \item Example: Reduction circuit
+\end{itemize}
+}
+
+\subsection{Reduction circuit}
+
+\frame{
+\frametitle{Reduction Circuit}
+\begin{columns}[l]
+\column{0.5\textwidth}
+\begin{figure}
+\includegraphics[height=6.5cm]{reducer}
+\end{figure}
+\column{0.5\textwidth}
+\begin{itemize}
+ \item Reduction circuit sums the floating-point values of each row in a matrix.
+ \item Non-trivial due to pipe-lined floating-point adder.
+ \item Largest restrictions are the fixed-size vectors.
+\end{itemize}
+\end{columns}
+}
+
+\begin{frame}
+ \begin{figure}
+ \includegraphics[height=9cm]{reducerschematic}
+ \end{figure}
+\end{frame}
+
+
+\begin{frame}
+\frametitle{FIFO Buffer}
+\begin{itemize}
+ \item Wish:
+\begin{verbatim}
+fifo :: (State mem) (input, shift) =
+ (State mem', out1, out2)
+ where
+ out1 | length mem == 0 = NotValid
+ | otherwise = head mem
+ out2 | length mem < 2 = NotValid
+ | otherwise = head (tail mem)
+ mem' = drop shift mem ++ [input]
+\end{verbatim}
+\end{itemize}
+\end{frame}
+
+\begin{frame}
+\frametitle{FIFO Buffer}
+\begin{itemize}
+ \item Reality:
+\begin{verbatim}
+fifo :: (State (Fifo {..})) (inp, shift) =
+ ( State (Fifo { mem = mem'
+ , ptr = ptr'
+ })
+ , out1, out2
+ )
+ where
+ ptr' = ptr - shift + 1
+ mem'' = replace mem ptr (Valid inp)
+ mem' | shift == 0 = mem''
+ | shift == 1 = (tail mem'') <+ NotValid
+ | otherwise = ((tail (tail mem'')
+ <+ NotValid) <+ NotValid)
+ out1 = head mem
+ out2 = head (tail mem)
+\end{verbatim}
+\end{itemize}
+\end{frame}
+
+\frame{
+\frametitle{FIFO Buffer}
+\begin{itemize}
+ \item Wish: Dynamically sized vectors
+ \item Reality: Statically sized vectors
+\end{itemize}
+}
+
+\frame{
+\frametitle{Dynamically Sized Vectors}
+\begin{itemize}
+ \item Map all vectors to RAMs:
+ \begin{itemize}
+ \item Store length separately, extra logic
+ \item What happens if size exceeds size of 1 blockRAM?
+ \end{itemize}
+ \item Translate to (shift/circular) Buffers
+ \begin{itemize}
+ \item Requires analysis of data-access
+ \item How do we determine maximum size?
+ \end{itemize}
+\end{itemize}
+}
\ No newline at end of file
--- /dev/null
+\subsection{Structure}
+%include talk.fmt
+\frame{
+\frametitle{Structure}
+\begin{verbatim}
+fir (State pxs) x = (pxs**hs, State (pxs<++x))
+ where hs = $(vectorTH [2::Int16,3,-2,4])
+\end{verbatim}
+\begin{itemize}
+ \item How did we know how big the circuit would have to be? e.g. How many multipliers?
+ \item The size of the circuit is determined by the size of the vectors!
+\end{itemize}
+}
+
+\frame{
+\frametitle{Structure}
+\begin{itemize}
+ \item The size of the vectors determines the size of the circuit.
+ \item How do we know the size of the vectors?
+ \begin{itemize}
+ \item We infer the size
+ \item We specify the size
+ \end{itemize}
+\end{itemize}
+}
+
+\subsubsection{Size Inference}
+\frame{
+\frametitle{Infer Size}
+\begin{itemize}
+ \item Determine the size by counting the elements inside, at compile-time.
+ \item Base size of new vectors based on size of other vectors of which you already know the size.
+ \item Requires a lot of bookkeeping.
+\end{itemize}
+}
+
+\frame{
+\frametitle{Infer Size}
+\begin{itemize}
+ \item Might not be possible in the general case?
+ \item What is the size of the combinatorial circuit seen below? Infinite? Zero?
+\end{itemize}
+\begin{verbatim}
+ xs ** hs = foldl (+) 0 (zipWith (*) xs hs)
+\end{verbatim}
+}
+
+\subsubsection{Size Specification}
+\frame{
+\frametitle{Specify Size}
+\begin{itemize}
+ \item Have the designer specify the size of a vector.
+ \item Two ways to specify
+ \begin{itemize}
+ \item As part of each specific instance / term
+ \item As part of the type
+ \end{itemize}
+\end{itemize}
+}
+
+\frame{
+\frametitle{Some basic concepts}
+\begin{itemize}
+ \item Programming languages express computations
+ \item Computations manipulate values
+ \item Types = Set of values
+ \item Computations can be assigned types to indicate what kind of values to produce or manipulate
+\end{itemize}
+}
+
+\frame{
+\frametitle{Specify Size (term-level)}
+\begin{itemize}
+ \item Size specification at the instance / term level suffers from the same problems as size inference:
+ \begin{itemize}
+ \item Extensive bookkeeping
+ \item Compile Time-Evaluation
+ \item Generality of the solution
+ \end{itemize}
+\end{itemize}
+}
+
+\frame{
+\frametitle{Specify Size (type-level)}
+\begin{itemize}
+ \item The size of the vector becomes part of the type:
+ \begin{itemize}
+ \item Unconstrained Vectors:
+ \begin{verbatim}
+Nat n => Vector n a
+ \end{verbatim}
+ \item Constrained Vectors:
+ \begin{verbatim}
+Vector 4 a
+ \end{verbatim}
+ \end{itemize}
+\end{itemize}
+}
+
+\frame{
+\frametitle{Specify Size (type-level)}
+\begin{itemize}
+ \item Not only do we want to indicate the size of vectors
+ \item We also want to manipulate or query the size of a vector
+\end{itemize}
+}
+
+\frame{
+\frametitle{Size Query}
+\begin{itemize}
+ \item Sometimes we want to know something about the size of the vector
+ \item Get the first element of the vector
+ \begin{verbatim}
+first :: Positive n => Vector n a -> a
+ \end{verbatim}
+ \item Only works for vectors that are not empty
+\end{itemize}
+}
+
+\frame{
+\frametitle{Size Manipulation}
+\begin{itemize}
+ \item Sometimes we want to relate the size of one or more vectors to the size of one or more other vectors
+ \item Combine 2 vectors into 1 large vector
+ \begin{verbatim}
+combine :: Vector n1 a -> Vector n2 a ->
+ Vector (n1 + n2) a
+ \end{verbatim}
+\end{itemize}
+}
+
+\frame{
+\frametitle{Type-level numbers}
+\begin{itemize}
+ \item Number literals, e.g. 1, 4 , 17, etc. are not allowed in the type signature.
+ \item We must resort to so-called type-level numbers
+ \item When dealing with type-level number,s each instance is a type in it’s own right! e.g. the type-level equivalent of 3 is D3.
+\end{itemize}
+}
+
+\frame{
+\frametitle{Type-level problems}
+\begin{itemize}
+ \item Type systems demand proofs! Otherwise they are of no use to us!
+ \item When dealing with type-level numbers we suddenly have to proof invariants that we normally take for granted.
+ \item For example, commutativity of addition:\\ a + b = b + a
+\end{itemize}
+}
+
+\frame{
+\frametitle{Consequences}
+\begin{itemize}
+ \item Currently such proofs have to specified as part of the programs, and in a very cumbersome way!
+ \item We chose not to expose this need for proofs to the developer.
+ \item Result: a (limited) set of vector transformations is exposed to a developer.
+\end{itemize}
+}
+
+\frame{
+\frametitle{Consequences}
+\begin{itemize}
+ \item The largest consequence of not allowing any type of vector transforming functions is that a developer can no longer specify recursive functions!
+\end{itemize}
+}
\ No newline at end of file
\frametitle{Hardware}
\begin{figure}
\centerline{
-\includegraphics<1>[height=6cm]{figures/cpus/pmiphone_boardtopbig}
-\includegraphics<2>[height=6cm]{figures/cpus/Intel_core_i7}
-\includegraphics<3>[height=6cm]{figures/cpus/6600GT_GPU}
-\includegraphics<4>[height=6cm]{figures/cpus/Altera_StratixIV}
+\includegraphics<1>[height=8cm]{figures/cpus/pmiphone_boardtopbig}
+\includegraphics<2>[height=8cm]{figures/cpus/Intel_core_i7}
+\includegraphics<3>[height=8cm]{figures/cpus/6600GT_GPU}
+\includegraphics<4>[height=8cm]{figures/cpus/Altera_StratixIV}
}
\label{img:chips}
\end{figure}
\frametitle{Designing Hardware}
\centerline{Design with 4 transistors}
\begin{columns}[c]
-\column{0.5\textwidth}
+\column{0.6\textwidth}
\vspace{-0.5cm}
\begin{figure}
-\centerline{\includegraphics[height=5cm, trim = 0 0 0 2.5cm, clip]{figures/schakelingen/NAND}}
+\centerline{\includegraphics[height=6cm, trim = 0 0 0 2.5cm, clip]{figures/schakelingen/NAND}}
\end{figure}
-\column{0.5\textwidth}
+\column{0.4\textwidth}
\begin{figure}
-\centerline{\includegraphics[height=5cm, trim = 0 4.5cm 0 0, clip]{figures/schakelingen/CMOS_NAND_Layout}}
+\centerline{\includegraphics[height=6cm, trim = 0 4.5cm 0 0, clip]{figures/schakelingen/CMOS_NAND_Layout}}
\end{figure}
\end{columns}
}
\frame
{
-\frametitle{Transistors}
+\frametitle{Transistor}
\begin{figure}
\centerline{
-\includegraphics<1>[height=6cm]{figures/transistor/hr-1sttransistor}
-\includegraphics<2>[height=6cm]{figures/transistor/worldsfastes}
-\includegraphics<3>[height=6cm]{figures/transistor/nehalem_432x315}
+\includegraphics<1>[height=8cm]{figures/transistor/hr-1sttransistor}
+\includegraphics<2>[height=8cm]{figures/transistor/worldsfastes}
+\includegraphics<3>[height=8cm]{figures/transistor/nehalem_432x315}
}
\label{img:chips}
\end{figure}
\vspace{0.5cm}
\centerline{\Large This won't work for 730 million transistors!}
\begin{figure}
-\centerline{\includegraphics[height=4cm]{figures/transistor/nehalem-core}}
+\centerline{\includegraphics[height=7cm]{figures/transistor/nehalem-core}}
\end{figure}
}
%include talk.fmt
+\section{Presentation Matthijs}
\title{Haskell as a higher order structural hardware description language}
\author{Matthijs Kooijman}
\date{December 14, 2009}
%format QUd(x) = "[d|" x "\rrbracket "
%format QUt(x) = "[t|" x "\rrbracket "
%format ^^ = "\; "
-%format ** = "\ \mathit{**}\ "
%endif
\ No newline at end of file
projects / matthijs / master-project / final-presentation.git / commitdiff