e1add22cc3c0aa6be5413f56c3aca5f3111ed606
[matthijs/master-project/final-presentation.git] / christiaan / reductioncircuit.lhs
1 \subsection{Restrictions}
2 %include talk.fmt
3 \frame{
4 \frametitle{Too Restrictive?}
5 \begin{itemize}
6   \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?
7 \end{itemize}
8 }
9
10 \frame{
11 \frametitle{Too Restrictive?}
12 \begin{itemize}
13   \item There is certainly room to increase expressivity. But we can already describe non-trivial design in CλasH.
14   \item Example: Reduction circuit
15 \end{itemize}
16 }
17
18 \subsection{Reduction circuit}
19
20 \frame{
21 \frametitle{Reduction Circuit}
22 \begin{columns}[l]
23 \column{0.5\textwidth}
24 \begin{figure}
25 \includegraphics[height=6.5cm]{reducer}
26 \end{figure}
27 \column{0.5\textwidth}
28 \begin{itemize}
29   \item Reduction circuit sums the floating-point values of each row in a matrix.
30   \item Non-trivial due to pipe-lined floating-point adder.
31   \item Largest restrictions are the fixed-size vectors.
32 \end{itemize}
33 \end{columns}
34 }
35
36 \begin{frame}
37    \begin{figure} 
38       \includegraphics[height=9cm]{reducerschematic} 
39     \end{figure}
40 \end{frame}
41
42
43 \begin{frame}
44 \frametitle{FIFO Buffer}
45 \begin{itemize}
46   \item Wish:
47 \begin{verbatim} 
48 fifo :: (State mem) (input, shift) = 
49   (State mem', out1, out2)
50   where
51     out1 | length mem == 0 = NotValid
52          | otherwise       = head mem
53     out2 | length mem < 2  = NotValid
54          | otherwise       = head (tail mem)
55     mem' = drop shift mem ++ [input]
56 \end{verbatim}
57 \end{itemize}
58 \end{frame}
59
60 \begin{frame}
61 \frametitle{FIFO Buffer}
62 \begin{itemize}
63   \item Reality:
64 \begin{verbatim} 
65 fifo :: (State (Fifo {..})) (inp, shift) = 
66   ( State (Fifo { mem = mem'
67                 , ptr = ptr'     
68                 })
69   , out1, out2
70   )
71   where
72     ptr'  = ptr - shift + 1
73     mem'' = replace mem ptr (Valid inp)
74     mem'  | shift == 0 = mem''
75           | shift == 1 = (tail mem'') <+ NotValid
76           | otherwise  = ((tail (tail mem'') 
77                           <+ NotValid) <+ NotValid)
78     out1  = head mem
79     out2  = head (tail mem) 
80 \end{verbatim}
81 \end{itemize}
82 \end{frame}
83
84 \frame{
85 \frametitle{FIFO Buffer}
86 \begin{itemize}
87   \item Wish: Dynamically sized vectors
88   \item Reality: Statically sized vectors
89 \end{itemize}
90 }
91
92 \frame{
93 \frametitle{Dynamically Sized Vectors}
94 \begin{itemize}
95   \item Map all vectors to RAMs:
96   \begin{itemize}
97     \item Store length separately, extra logic
98     \item What happens if size of the vector exceeds size of the size of the RAM?
99   \end{itemize}
100   \item Translate to (shift/circular) Buffers
101   \begin{itemize}
102   \item Requires analysis of data-access
103   \item How do we determine maximum size?
104   \end{itemize}
105 \end{itemize}
106 }