Add rest of my presentation

diff --git a/Makefile b/Makefile
index b4b9a3f2bdc4130131677bb7f7c95f1b7ab204d9..ddaa3fccc8e4bcd50a80694c0f939e1293a9b01a 100644 (file)
--- a/Makefile
+++ b/Makefile
@@ -9,7 +9,10 @@ LHSRCS = \
        matthijs/introduction.lhs \
        christiaan/introduction.lhs \
        christiaan/fir.lhs \
        matthijs/introduction.lhs \
        christiaan/introduction.lhs \
        christiaan/fir.lhs \

-       christiaan/dotproduct.lhs
+       christiaan/dotproduct.lhs \
+       christiaan/structure.lhs \
+       christiaan/reductioncircuit.lhs \
+       christiaan/recursion.lhs

 
 LHFORMATS = \
        talk.fmt
 
 LHFORMATS = \
        talk.fmt

diff --git a/christiaan/introduction.lhs b/christiaan/introduction.lhs
index e88a32ba16b0788205bc7ec07fde389dc3a05d5d..bb142facd7185a820c9cbbf27205904a9a7aa916 100644 (file)
--- a/christiaan/introduction.lhs
+++ b/christiaan/introduction.lhs
@@ -4,6 +4,13 @@
 \author{Christiaan Baaij}
 \date{December 14, 2009}
 
 \author{Christiaan Baaij}
 \date{December 14, 2009}
 

+\section{Presentation Christiaan}

 \frame{\titlepage \setcounter{framenumber}{1}}
 
 \frame{\titlepage \setcounter{framenumber}{1}}
 

-\input{christiaan/fir}
\ No newline at end of file
+\input{christiaan/fir}
+\input{christiaan/structure}
+\input{christiaan/reductioncircuit}
+\input{christiaan/recursion}
+
+\section{Questions}
+\frame{\vspace{2cm}\centerline{\Huge{Questions?}}}
\ No newline at end of file

diff --git a/christiaan/recursion.lhs b/christiaan/recursion.lhs
new file mode 100644 (file)
index 0000000..c388355
--- /dev/null
+++ b/christiaan/recursion.lhs
@@ -0,0 +1,63 @@
+\section{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}
+}
+
+\subsection{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}
+
+\subsection{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

diff --git a/christiaan/reductioncircuit.lhs b/christiaan/reductioncircuit.lhs
new file mode 100644 (file)
index 0000000..a4f55f6
--- /dev/null
+++ b/christiaan/reductioncircuit.lhs
@@ -0,0 +1,106 @@
+\section{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}
+}
+
+\section{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

diff --git a/christiaan/structure.lhs b/christiaan/structure.lhs
new file mode 100644 (file)
index 0000000..2c81397
--- /dev/null
+++ b/christiaan/structure.lhs
@@ -0,0 +1,164 @@
+\section{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}
+}
+
+\subsection{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}
+}
+
+\subsection{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

diff --git a/treeadder.pdf b/treeadder.pdf
new file mode 100644 (file)
index 0000000..f547b57
Binary files /dev/null and b/treeadder.pdf differ