\section{A Theoretic Machine Model}
\seclabel{part2}
%or some other title

\subsection{Motivation of Model}

A model that takes caching into account is needed because data locality has a significant effect
 on the practical runtime of algorithms.
\paragraph{Poor Matrix Multiplication Algorithm.}
Below is the trivial algorithm for Matrix Multiplication for
the $n$ by $n$ matrices $C = AB$. This algorithm works well on the RAM model, 
where all instructions complete in one timestep, but
works poorly in practice.

\begin{code}
\<  Mult($C$,$A$,$B$) \\
    \For\ $i$ = $1$ \textbf{to} $n$ \textbf{do} \\
\>      \For\ $j$ = $1$ \textbf{to} $n$ \textbf{do} \\
\> \>        $c_{ij} = \sum_{k=1}^n A_{ik}B_{kj}$. \\
\end{code}

This algorithm performs poorly because it lacks data locality hence causing bad cache performance.

\subsection{Memory Heirarchies}
\subsubsection{Multilevel Memory Heirarchy}

A multilevel memory heirarchy has many parameters, making it complicated and difficult to analyze; see \figref{fig:mult_level}.

\begin{figure}[bthp]
\centering
\includegraphics[width=3.0in]{3/figures/scribe2.eps}
\caption{Multievel Memory Hierarchy. Each level has a different size, block size, and number of cache lines. The time for a memory transfer between levels differs.}
\figlabel{fig:mult_level}
\end{figure}

\subsubsection{Two-Level Memory Heirarchy}

The following two-level memory model is a simplification that is easier to analyze; see \figref{fig:two_level}.

\begin{figure}[bthp]
\centering
\includegraphics[width=3.0in]{3/figures/scribe.eps}
\caption{Two-Level Memory Hierarchy with block size $B$, cache size $M$, and $M/B$ lines of cache.}
\figlabel{fig:two_level}
\end{figure}

\paragraph{Description.}

This two-level memory hierachy consists of a CPU, cache, and main memory.
The cache is divided into cache lines, or \defn{blocks} of size $B$. The cache has size $M$ and is 
composed of $M/B$ blocks. The act of moving a block between cache
and main memory is called a \defn{memory transfer}. When a memory transfer
brings a block from main memory into a  ``slot'' in cache,
the memory block that previously occupied that slot is \defn{evicted}.

\paragraph{Objective.}

We want to minimize the
number of memory transfers in an algorithm, because they are the most expensive operations. 

Although referred to as ``cache'' and ``main memory'', these
two levels can represent any two contiguous levels in the memory heirarchy.
For the remainder of these notes, we use the two-level memory model and not the multilevel memory model.

\subsection{Block Replacement Strategies}

One issue is how to select which block to evict during a memory transfer. 
Below we compare ideal solutions to realistic ones.

\subsubsection{Ideal Cache Model vs. Other Replacement Strategies}

\paragraph{Description.}

According to the \defn{ideal cache model} \cite{flpr99},
the best block to replace is the block that is accessed 
farthest in the future [Belady]. We call this model \defn{FIF}, which stands for
``farthest in future''.

\paragraph{Difficulty: Cannot Look into future.}

Although the optimal strategy, FIF is not implementable. One cannot look into the future to select which block to evict.
However, there exists a simulation that avoids this difficulty.


\begin{theorem}
LRU/FIFO with cache of size $M$ $\leq$ 2OPT with cache of size $2M$.
\end{theorem}

For further details see \cite{flpr99}.

\paragraph{Difficulty: Limited Assiciativity.}
The ideal cache model assumes full associativity while actual hardware has limited associativity.
In our ideal cache model, we assume any block of memory can be stored
anywhere in cache (\defn{full associativity}). Realistically, caches 
do not have this property. Caches can be \defn{direct-mapped}, meaning block $i$
can \emph{only} be cached in slot $i\mod (M/B)$. Caches can also be
\defn{2-way set associative}, meaning only two blocks can be stored in each slot
($M/2B$ slots total).

As described in Section 1, actual hardware has limited associativity and
also has a simpler replacement policy.

\begin{theorem}\cite{flpr99}
  Auto-replacement, fully associative LRU/FIFO cache can be simulated using a
manual replacement, direct mapped cache in $O(1)$ expected time
\end{theorem}

For further details see \cite{flpr99}.

\subsection{Cache-Aware v. Cache-Oblivious}

Sections 2.1 - 2.3 give a well defined computational model involving caching. We define two different types of algorithms:

\paragraph{Cache-Oblivious Algorithms.}

A cache-oblivious algorithm does not use the variables $B$ and $M$, but its performance
still depends on $B$ and $M$. The cache-oblivious model enables us to
reason about a simple two-level memory model but prove results about an unknown
multilevel memory model. Cache-oblivious algorithms perform an \emph{asymptotically optimal}
number of memory transfers for \emph{any} memory heirarchy at \emph{all levels} of the
hierarchy. The number of memory transfers between any two levels is within a constant
factor of optimal. Any linear combination of the transfer counts is optimized.

\paragraph{Cache-Aware Algorithms.}

A cache-aware algorithm is an optimal algorithm that is aware of and uses the variables $M$ and $B$.

\section{Analysis of Several Algorithms}
\seclabel{part3}
\subsection{Method of Asymptotic Analysis}

The goal is to use algorithms with a 
solid foundation to predict performance. Thus, we present in Section 2 a
simple algorithmic model that gives more accurate running time than the standard
RAM model. 

\paragraph{Defining Cost.}

We define the \defn{cost} of an algorithm as 
the number of memory transfers. Note we do 
not take into account the time to transfer memory from the cache
to the CPU or operations on data in cache, because the time needed to perform these operations is much
less than the time needed to perform a memory transfer between cache and main memory.

\subsection{Example 1: Array-scanning}

Consider array-scanning. The goal is to read
in order the elements in an array $A[1...n]$.

\begin{verbatim}
  for i = 1 to n
    sum += A[i].
\end{verbatim}

\paragraph{Cost.}

We see:

\begin{eqnarray*}
\mbox{Cost} \leq \ceil {\frac{N}{B}} + 1. 
\end{eqnarray*}

An example is in \figref{fig:n_b}.

\begin{figure}[bthp]
\centering
\includegraphics[width=5in]{3/figures/n_b.eps}
\caption{Array spread across blocks. The clear rectangles are blocks in cache. The shaded region is the location of the array in cache.}
\figlabel{fig:n_b}
\end{figure}

\paragraph{Analysis.}

At worst, this algorithm is optimal to within 1 memory transfer.

\subsection{Example 2: Binary Search}

Consider performing a binary search on an array using the traditional algorithm. 

\paragraph{Cost.}

The total number of memory transfers is 
\begin{align}
\mbox{cost} &= \lg \frac{N}{B} \\
&= \lg N - \lg B .
\end{align}

\paragraph{Analysis.}

This cost is \emph{not} optimal. The optimal cost is $\log_B N$. We achieve this performance bound using B-trees (which are out of the scope of this lecture).

\subsection{Example 3: Recursive Matrix Multiplication}

Consider the recursive algorithm where $C = AB$.
The recursive method, breaks each matrix into four parts as such:

\begin{eqnarray*}
\begin{pmatrix} C_{11} & C_{12} \\ C_{21} & C_{22} \end{pmatrix}
&=&
\begin{pmatrix} A_{11} & A_{12} \\ A_{21} & A_{22} \end{pmatrix}
\begin{pmatrix} B_{11} & B_{12} \\ B_{21} & B_{22} \end{pmatrix}
\\
&=&
\begin{pmatrix} A_{11}B_{11}+A_{12}B_{21} & A_{11}B_{12}+A_{12}B_{22} \\ A_{21}B_{11}+A_{22}B_{21} & A_{21}B_{12}+A_{22}B_{22} \end{pmatrix}
.
\end{eqnarray*}

\paragraph{Layout of Matrix in Memory.}
We first consider how to lay the matrix out in memory. For the bad serial algorithm 
presented above, $A$ being stored as row-major and $B$ being stored as column-major
would be good. 

For the recursive algorithm, however, a better layout exists in \figref{fig:matrix}.

\begin{figure}[bthp]
\centering
\includegraphics[width=5in]{3/figures/scribe4.eps}
\caption{Representation of Matrix in memory.}
\figlabel{fig:matrix}
\end{figure}

The above representation has been referred to as \defn{Mortan Order}, and is similar to a
\textit{space-filling curve} or a \textit{Hilbert curve}.

\paragraph{Cost.}
\subparagraph{Derivation of Recurrence Equation.}

We express this algorithm by the recurrence:
\begin{eqnarray*}
T(N) = 8T\left(\frac{N}{2}\right) + O \left(\ceil{\frac{N^2}{B}}\right).
\end{eqnarray*}

The second term of the recurrence represents the number of memory transfers needed to perform the addition, as presented in Lecture 2.
Adding $N^2$ elements in order causes $\ceil{{N^2}/B}$ memory transfers, thus it is $\bigO \left(\ceil{{N^2}/B}\right)$.

\subparagraph{Base Cases.}

We analyze the two base cases.

The first base case is,
\begin{eqnarray*}
T(\sqrt{B}) = O(1).
\end{eqnarray*}
In this case, the entire matrix fits within
one cache block.

The second base case is,
\begin{eqnarray*}
T(c \sqrt{M}) = O \left(\frac{M}{B}\right),
\end{eqnarray*}
for a sufficiently small $c$ such that all 3 matrices fit in cache.
The result is $O(M/B)$ because
the data is brought into memory. All other computation is performed in cache.

\subparagraph{Solving the Recurrence Equation.}

We solve this recurrence using a tree instead of the Master Theorem. A sketch
is in \figref{fig:tree}.
\begin{figure}[bthp]
\centering
\includegraphics[width=5in]{3/figures/scribe3.eps}
\caption{Recursion Tree Sketch. $h =\lg\left(\frac{N}{\sqrt{M}}\right)$}
\figlabel{fig:tree}
\end{figure}

The cost of the root is $O\left(\ceil{N^2/B}\right)$. We traverse the tree until we reach
problems of size $O(\sqrt{M})$. The height of this tree is :

\begin{eqnarray*}
h = \lg \left(\frac{N}{O(\sqrt{M})}\right).
\end{eqnarray*}

Thus, the number of leaves $\ell$ is:
\begin{align}
\ell &= 8^{\lg \left(\frac{N}{O(\sqrt{M})}\right)} \\
&= O \left(\left(\frac{N}{\sqrt{M}}\right)^3\right).
\end{align}

The cost per leaf = $\Theta (M/B)$, thus the cost of all leaves is:
\begin{align}
\mbox{cost of all leaves} &= \Theta \left(\frac{M}{B}\frac{N^3}{M^{\frac{3}{2}}}\right) \\
&= \Theta \left(\frac{N^3}{B \sqrt{M}}\right). \\
\end{align}
Thus, the cost of the root is,
\begin{align}
\mbox{cost of root} &= \Theta \left(\ceil{\frac{N^2}{B}} \right).
\end{align}

Asymptotically, the leaves dominate the cost. Thus:
\begin{eqnarray*}
\mbox{Total cost} = \Theta \left(\frac{N^3}{B \sqrt{M}}\right).
\end{eqnarray*}

\paragraph{Analysis.}

The cost of this cache-oblivious algorithm is optimal. It can be proved using pebble games, but the proof is out
of the scope of the lecture.
