\section{High Performance Serial Programming}
\seclabel{part1}
\subsection{Computer Hardware}
High performance programming is impossible without knowledge of the
hardware in the host computer.  This section discusses one of the most
important elements of the hardware: the memory hierarchy.
\figref{fig:hierarchy} sketches the memory structures in
computer.   Each level of the
memory hierarchy is larger and slower than the one that preceded it.  Closest to the processor is a small, fast register file.
Data words (e.g., 64 bits) are brought to the register file from the cache.  A
cache contains a subset of the words in main memory and deals with
\defn{lines} (e.g., 128 bytes) rather than individual words.   \tabref{stats} shows the sizes and speeds of memory hierarchies for two
recent computer systems.
\begin{figure}[bthp]
\centering
\includegraphics[width=5in]{3/figures/hierarchy.eps}
\caption{Memory hierarchy.}
\figlabel{fig:hierarchy}
\end{figure}


\begin{table}[htb]
\centering
\small
\begin{tabular}{|l|l|l|}\hline
& ygg: Origin 2000 w/R10000 & Pentium 4 \\ \hline 
Processor speed & 195 MHz & 2500 MHz \\
Registers & 64 & 8 \\
L1 Cache size  & 32KB & 8KB  \\
L1 Cache access time (ns) & 10 & 1 \\

L1 Cache line size & 128B & 64B \\
L1 Associativity & 2-way & 4-way \\
L1 Cache lines & 256 & 64 \\


L2 Cache size  & 4MB  & 512KB \\
L2 Cache access time (ns) ns & 62 & 8 \\

L2 Cache line size & 128B & 128B \\
L2 Associativity & 2 & 8-way \\
L2 Cache lines & 32K & 4K \\

Memory access time (ns) & 484 & 150 \\





 \hline
\end{tabular}
\caption{System parameters}
\tablabel{stats}
\end{table}

Caches are small, fast subsets of main memory.  Since they are smaller
than main memory, words necessarily map to more than one location
in the cache.  Therefore, the address of the data (the tag) is part of
the information that is stored alongside the data itself.  To reduce
miss-rates, associative caches, in which a word may be found in several
locations, are more popular than direct-mapped caches (which we did not
discuss).  There are two types of associativity:
\begin{description}
\item[Fully associative] Any word of memory can be stored in any cache
  line.
\item[Set associative] Words of memory can be placed in restricted set
  of places in the cache.  A word is mapped onto a set and can be placed
  anywhere in that set.  If there are $n$ words in a set, the cache is
  $n$-way set associative.
\end{description}
For example, a 512 Kilobyte (KB), 4-way set associative cache with 128 byte lines would
contain 1024 sets.  Memory locations that are 128KB apart in memory are in
the same set and compete for space in that set.  If the replacement
policy and data access pattern are compatible, the
four ways permit four such addresses to coexist in the cache without
evicting each other. 

\subsection{Compilers}
\begin{figure}[b]
\centering
\includegraphics[width=5in]{3/figures/compilation.eps}
\caption{Compilation process}
\figlabel{fig:compilation}
\end{figure}
Compilers translate high-level language to assembly
language.\footnote{Usually, the compiler will invoke an assembler to
  translate the assembly language to machine code}  The handout
\cite{handout3} shows
what this assembly language looks like.  Note that instructions are
simple (usually one or two operands, one result).  
To produce the best set of simple assembly instructions, you must use a
``good compiler.''  Though SGI \texttt{cc} has a good reputation,
\texttt{gcc}  can outperform it occasionally.  Here are some more explicit tricks and tools.

\begin{itemize}
\item Profile your code so that you know where to focus your
  optimization effort.  Use the \texttt{-pg} option to gcc or the
  \texttt{-p} to \texttt{cc}.  Then run \texttt{gprof} or \texttt{prof}, respectively.  Profiling uses
  statistical sampling (e.g., every 1ms it asks: what function is
  currently executing?). This is the ``real-life'' way
  to do what we did in last lecture with theory (that is, attack the $\bigO(n)$
  merge).
\item Debug your code.  \texttt{-g} inserts debugging symbols for gdb.
  Caveat: we don't appear to have a working debugger on \texttt{ygg}.
\item Enable compiler optimization with \texttt{-O2}; usually gets a
  dramatic speedup.
\item \texttt{-S} produces assembly listings so you can examine the
  results of compilation textually.
\item Become familiar with all of the other switches available to you by
  reading the manual:
\begin{verbatim}
ygg\% man cc
ygg\% info gcc
\end{verbatim}
\end{itemize}
\subsection{High-level optimizations}
Ideally the compiler would perform all high-level optimizations for you, but in practice
reorganizing/optimizing your code manually is necessary to help produce
a fast implementation.

A good reference is AMD's Software Optimization Guide \cite{amd}.
Though written with the AMD64 instruction set and microarchitecture in mind, many
of the techniques can be applied broadly.  Other vendors have similar
guides which may have useful machine-specific tricks.  The remainder of
this section contains the high-level optimizations discussed in class.
\subsubsection{Exploit registers}
Registers are the fastest storage elements at our disposal, so structure
your code to do as much work as possible with data in registers before
that data is pushed further down the memory hierarchy.  For example, a
2x2 matrix is small enough to allow all operands and results to fit in
registers.  Since each operand is used several times, it is best to
leave them in registers for the duration of the computation.
\subsubsection{Exploit fast memory}
Carrying the above idea further, we would prefer to work on data in L1 cache
to L2 cache, and we'd prefer L2 to main memory.  Size your problems
appropriately; use cache-conscious
data layout; or use optimal, cache-oblivous algorithms (see \secref{part2}).
\subsubsection{Move computations out of loops}
This loop initializes the array with $\sin x$ which is effectively a
  constant, but the compiler does not know this and will make 1000 calls
  to the $\sin$ library function.  If you were doing \texttt{a[i]=x+y}, the compiler
  might be able to tell and remove the add from the loop, but it doesn't know that sin() is different (here) than an arbitrary function call.
\begin{verbatim}
for(i=0; i<1000; i++){
  a[i]=sin(x);
}
\end{verbatim}

\subsubsection{Strength reduction}
Reduce complex operations to simpler forms (e.g., exponentiation into
a multiply or multiply into an add).  The examples from lecture:
\begin{verbatim}
for(i=0; i<1000; i++){ 
  a[i]=pow(S,i);  
}
\end{verbatim}
becomes
\begin{verbatim}
tmp=1;
for(i=0; i<1000; i++){
  a[i]=tmp; 
  tmp*=S;
}

\end{verbatim}

\subsubsection{Unroll loops}
To eliminate the overhead associated with looping, try unrolling your
loops to some degree.
\begin{verbatim}
for(i=0; i<N; i++)
  f(i); 
\end{verbatim}
becomes
\begin{verbatim}
for(i=0; i+1<N; i+=2){ 
  f(i); 
  f(i+1);
}
for(; i<N; i++)         //clean up last case
  f(i);                 
\end{verbatim}
This effectively changes $r += a(i)*b(i)$ to $r += a(i)*b(i) + a(i+1)*b(i+1)$
Sometimes the compiler can do this for you, sometimes it cannot.

\subsubsection{Remove control dependencies}
In deeply pipelined machines, a mispredicted branch can require tens of
cycles to repair, squashing hundreds of instructions.  Sometimes you can
replace a hard-to-predict branch with a predicated instruction such as
MIPS's conditional move:
\begin{verbatim}
movz Ri, Rj, Rn       #if(Rn==0) Ri=Rj
\end{verbatim}
Here a control dependence has become a data dependence.... 

\subsection{Example: isort vs. sort5 \cite{handout3}}
Recall that despite its \bigO$(n^3)$ running time, insertion sort needs
few steps to complete for for small values of $n$.  Despite a
larger number of operations, the \texttt{sort5} code is measureably
faster when sorting five elements.  Why?  The \texttt{isort} code is slowed down by unpredictable branches and more
memory references.  To demonstrate, \tabref{sort} shows the time taken by each routine
with varying compiler and machine combinations.
\begin{table}[htb]
\centering
\begin{tabular}{|l|l|l|l|}\hline
& gcc & cc & gcc (Pentium)\\ \hline \hline
isort & 599ns & 580ns & 88ns \\  
sort5 & 275ns & 112ns & 34ns \\
\hline
\end{tabular}
\caption{Sort timing}
\tablabel{sort}
\end{table}

