From dd66303c1c20fa616b7095102f5c7cad7785a1f5 Mon Sep 17 00:00:00 2001
From: Francis Russell <francis@unchartedbackwaters.co.uk>
Date: Tue, 19 Feb 2013 17:42:19 +0000
Subject: [PATCH] Work on improving Scala implementation slides.

---
 presentation.tex | 62 +++++++++++++++++++++++++++++++++++-------------
 1 file changed, 45 insertions(+), 17 deletions(-)

diff --git a/presentation.tex b/presentation.tex
index e5b4927..d924642 100644
--- a/presentation.tex
+++ b/presentation.tex
@@ -254,47 +254,75 @@ Permutation & $T_{perm} = (I \succ I') \cup (I' \succ I)$ \\
 
 \frame{
 
-\frametitle{Our initial implementation}
+\frametitle{Our initial design}
 
 We developed an code generator in Scala that attempted to reason
 about the indices involved in the computation.
 
 \vspace{0.5em}
-\centering
+
+\begin{columns}
+
+\begin{column}{0.4\textwidth}
 \resizebox{!}{0.7\textheight}{
 \begin{tikzpicture}[scale=0.5, minimum size=2em, thick]
 \input{images-dot/index_propagation_dag}
 \end{tikzpicture}
 }
+\end{column}
+
+\begin{column}{0.6\textwidth}
+\footnotesize
+\begin{itemize}
+
+\item Leaf nodes define indices.
+
+\item Indices are related by dependence relationships and describe the space
+  they iterate over.
+
+\item Non-leaf nodes may add and remove indices depending on how they are
+  implemented (e.g. scaling can be applied element-wise, FFTs cannot).
+
+\item Names (e.g. alpha, beta) can be used to bind these exposed indices
+  together, forcing combined iteration.
+
+\item Incompatible dependencies between indices may force intermediate storage
+  to be introduced.
+
+\item Aim is to reduce the amount of intermediate storage required.
+
+\end{itemize}
+\end{column}
+
+\end{columns}
 
 }
 
 \frame{
 
-\frametitle{Our initial implementation}
+\frametitle{Our initial design}
 
-The system was designed to reason about the relationships between indices, and
-generate code subject to the various constraints.
+There are many additional complicating factors:
 
 \begin{itemize}
 
-\item Nodes that could be applied point-wise did not affect any of their indices.
-
-\item Nodes that constructed entirely new fields (e.g. FFTs) removed indices of
-  the operands they used and exposed new indices.
+\item We can define ``derived indices'' - indices that are derived from the
+  index variables of our loop nests that have a physical interpretation.
 
-\item Nodes could be transparent to indices they did not act on, so an FFT node
-  acting on a set of functions would represent the FFT of all of them.
+\item If we bind derived indices together, can we still synthesise an efficient
+  loop nest? We need to think about inverting the mapping from index to derived
+  index.
 
-\item Nodes could require random access to certain indices, forcing the system
-  to introduce temporary storage.
-
-\item The system attempted to synthesise a loop nesting that respected all
-  dependencies whilst minimizing the amout of intermediate storage required to
-  pass data between each node in the graph.
+\item If we synthesise an intermediate buffer, how do we reason about storing
+  its size and location within a simulation cell? We need this to avoid
+  allocating a buffer the size of the entire cell (extremely undesirable).
 
 \end{itemize}
 
+We implemented this design, but never managed to refine it enough for practial
+use. However, we did implement a code generator based on a producer-consumer
+paradigm that embodies some of these concepts.
+
 }
 
 \frame{
-- 
2.47.3