\iffalse

INSTRUCTIONS: (if this is not ps1, use the right file name)

  Clip out the ********* INSERT HERE ********* bits below and insert
appropriate TeX code.  Once you are done with your file, run

  ``latex template.tex''

from the Athena shell.  If your TeX code is clean, the latex will exit
back to a prompt.  Once this is done, run

  ``dvips template.dvi -o template.ps''

which should print your file to the nearest printer.  There will be
residual files called ps1.log, ps1.aux, and ps1.dvi.  All these can be
deleted, but do not delete ps1.tex.

\fi
\documentclass[11pt]{article}
\usepackage{amsfonts}
\usepackage{latexsym}
\setlength{\oddsidemargin}{.25in}
\setlength{\evensidemargin}{.25in}
\setlength{\textwidth}{6in}
\setlength{\topmargin}{-0.4in}
\setlength{\textheight}{8.5in}

\newcommand{\handout}[5]{
   \renewcommand{\thepage}{#1-\arabic{page}}
   \noindent
   \begin{center}
   \framebox{
      \vbox{
    \hbox to 5.78in { {\bf 6.823 Computer Architecture} \hfill #2 }
       \vspace{4mm}
       \hbox to 5.78in { {\Large \hfill #5  \hfill} }
       \vspace{2mm}
       \hbox to 5.78in { {\it #3 \hfill #4} }
      }
   }
   \end{center}
   \vspace*{4mm}
}

\newcommand{\ho}[5]{\handout{#1}{#2}{Instructor:
#3}{Teaching Assistant: #4}{Handout #1: #5}}
\newcommand{\al}{\alpha}
\newcommand{\Z}{\mathbb Z}

\begin{document}
\handout{PS3-1}{DUE: 3/13/2002}{Problem Set 3}
{Instructors: Krste Asanovic, Srinivas Devadas}
{Timothy Danford, Kilian Pohl, Bryan Russell}

\section{Problem 1}
{\bf a}
\bigskip

Loop A incurs a cache miss approximately $\frac{1}{4}$ of its memory
accesses.  Loop B never hits the contents of the cache.  This translates
into 256 cache misses in Loop A and 1024 cache misses in Loop B.  The
reason is the combination of the row-major ordering of the matrix $A$
and the direct-mapped nature of the cache.  Each row of the matrix
contains $4$ cache lines worth of data ($4$ consecutive lines).  When
loop B sums the matrix, it sums down the columns.  Therefore, as each
entry in the matrix is touched, cache lines are loaded at positions in
the cache that are multiples of $4$.  After every $16$ rows of the
matrix, loop B starts loading new cache lines in the place of the ones
currently in place.  In other words, loop B uses only $\frac{1}{4}$ of
the lines available in the cache.  Loop A, on the other hand, loads the
cache lines sequentially and accesses all four words within a line
before accessing the next line.  Only $1$ in $4$ memory accesses are
misses when the length of a cache line is exceeded.

{\bf b}
\bigskip

\begin{tabular}{|c|c|c|c|c|c|c|c|c|c|c|} \hline
  & \multicolumn{10}{|c|}{1B Table 1-1: Matrix Multiply Without Blocking} \\ \cline{2-11}
  & \multicolumn{2}{|l}{Line 0} & \multicolumn{2}{|l}{Line 1} &
  \multicolumn{2}{|l}{Line 2} & \multicolumn{2}{|l}{Line 3} &
  \multicolumn{2}{|l|}{Line 4} \\ \hline
  0 & Invalid & Invalid & Invalid & Invalid & Invalid & Invalid &
  Invalid & Invalid & Invalid & Invalid \\ \hline
  1 & $Y[0][0]$ & $Y[0][1]$ &&&&&&&& \\ \hline
  2 & && $Z[0][0]$ & $Z[0][1]$ &&&&&& \\ \hline
  3 & & HIT & &&&&&&& \\ \hline
  4 & &&&& $Z[1][0]$ & $Z[1][1]$ &&&& \\ \hline
  5 & &&&&&& $Y[0][2]$ & $Y[0][3]$ && \\ \hline
  6 & &&&&&&&& $Z[2][0]$ & $Z[2][1]$ \\ \hline
  7 & &&&&&&& HIT && \\ \hline
  8 & && $Z[3][0]$ & $Z[3][1]$ &&&&&& \\ \hline
  9 & $X[0][0]$ & $X[0][1]$ &&&&&&&& \\ \hline
  10 & &&&& $Y[0][0]$ & $Y[0][1]$ &&&& \\ \hline
  11 & &&&&&&&& $Z[0][0]$ & $Z[0][1]$ \\ \hline
  12 & &&&&& HIT &&&& \\ \hline
  13 & &&&&&& $Z[1][0]$ & $Z[1][1]$ && \\ \hline
  14 & && $Y[0][2]$ & $Y[0][3]$ &&&&&& \\ \hline
  15 & $Z[2][0]$ & $Z[2][1]$ &&&&&&&& \\ \hline
  16 & &&& HIT &&&&&& \\ \hline
  17 & &&&&&&&& $Z[3][0]$ & $Z[3][1]$ \\ \hline
  18 & &&&& $X[0][0]$ & $X[0][1]$ &&&& \\ \hline
\end{tabular}

$14$ misses from $18$ memory accesses means that the matrix multiply
without blocking suffers from a $\frac{14}{18} = 77.78\%$ miss rate.

\begin{tabular}{|c|c|c|c|c|c|c|c|c|c|c|} \hline
  & \multicolumn{10}{|c|}{1B Table 1-2: Matrix Multiply With Blocking} \\ \cline{2-11}
  & \multicolumn{2}{|l}{Line 0} & \multicolumn{2}{|l}{Line 1} & \multicolumn{2}{|l}{Line 2} & \multicolumn{2}{|l}{Line 3} & \multicolumn{2}{|l|}{Line 4} \\ \hline
  0 & Invalid & Invalid & Invalid & Invalid & Invalid & Invalid &
  Invalid & Invalid & Invalid & Invalid \\ \hline
  1 & $Y[0][0]$ & $Y[0][1]$ &&&&&&&& \\ \hline
  2 & && $Z[0][0]$ & $Z[0][1]$ &&&&&& \\ \hline
  3 & & HIT &&&&&&&& \\ \hline
  4 & &&&& $Z[1][0]$ & $Z[1][1]$ &&&& \\ \hline
  5 & &&&&&& $X[0][0]$ & $X[0][1]$ && \\ \hline
  6 & HIT &&&&&&&&& \\ \hline
  7 & &&& HIT &&&&&& \\ \hline
  8 & & HIT &&&&&&&& \\ \hline
  9 & &&&&& HIT &&&& \\ \hline
  10 & &&&&&&& HIT && \\ \hline
  11 & &&&&&&&& $Y[1][0]$ & $Y[1][1]$ \\ \hline
  12 & && HIT &&&&&&& \\ \hline
  13 & &&&&&&&&& HIT \\ \hline
  14 & &&&& HIT &&&&& \\ \hline
  15 & $X[1][0]$ & $X[1][1]$ &&&&&&&& \\ \hline
  16 & &&&&&&&& HIT & \\ \hline
  17 & &&& HIT &&&&&& \\ \hline
  18 & &&&&&&&&& HIT \\ \hline
  19 & &&&&& HIT &&&& \\ \hline
  20 & & HIT &&&&&&&& \\ \hline
\end{tabular}

Although the table extends to length $20$, we will calculate the miss
rate with respect to the first $18$ accesses to memory.  There are $6$
of the first $18$ accesses that are misses, for a miss ratio of
$\frac{6}{18} = 33.33\%$ miss rate.

{\bf c}
\bigskip

If we want the inner two loops of our matrix multiply code to run without cache misses (except for compulsory misses), we need to make sure there is enough space to hold the complete $BxB$ block in $Z$, and the $B$-length rows in $X$ and $Y$.  

In other words, the data cache must be large enough to hold $B^2 + 2B$ matrix elements simultaneously to avoid (capacity) cache misses.  Assuming Ben Bitdiddle has a 16 kB data cache and that matrix elements are 1 word each, Ben's maximum blocking factor is $63$.  

When Ben notices the poor performance of his code on the UltraSPARC-I
with a TLB, his matrices are stored in row-major order within his
virtual address space.  However, due to the size of the matrix
($3000 * 4 \textrm{bytes} = 12000 \textrm{bytes per matrix row}$,
which is greater than the page size of 8 KB) each row starts on a
different page.  For that matter, any element of any of the matrices
is on a different page from the corresponding element (same column) in
the previous and subsequent rows of the same matrix.  In Ben's code
(and using the maximum blocking factor from above), when the innermost
loop is reached and executed it touches (in the best case for Ben) 63
separate pages from the data of $Z$ and 1 page (at best) for the data
from $Y$.  At this point the TBL is full, containing 64 VPN-to-PPN
mappings in its 64 lines.  However, Ben's code then accesses and sets
an entry of $X$.  Since the TBL is governed by an LRU replacement
policy, this causes the table entry correpsonding to $Z[kk,j]$ (the oldest $Z$ page) to be
removed from the TBL. In other words, the TBL is one line too short;
every time Ben's code enters the innermost loop, it must reload
\textbf{all} of the VPN-to-PPN mappings corresponding to $Z$ and $X$ into the TBL from
memory. Therefore the hit rate is below 50\% for the TLB. Thus the
overhead connected to the TLB outweighs the benefit in this
case. Consequently it leads to a slow down in performance. 

{\bf d}
\bigskip

The optimized \verb+BlockMove+ routine incorporates two main ideas:
\begin{enumerate}
  \item The first was illustrated in the blocked code for the matrix
    multiplication in 1B: blocking to maximize the use of the cache in
    the reading of the matrix that's being copied.
  \item The second and more important technique is the use of
    \verb+dcbz+ to avoid the penalty associated with the Macintosh's
    write-allocate cache behavior.  If we weren't using the \verb+dcbz+
    instruction, then every time we wrote to a new block of the
    destination memory array, we would incur a cache miss and a read
    from memory into cache that would be both costly and pointless
    (since the existing data is about to be written over anyway).
    Normally, the only way to bring something into the cache is to read
    it (the appropriate line) from memory.  The \verb+dcbz+ instruction
    allows us to specify that a line is loaded in the cache without
    actually going through the hassle of reading the contents from
    memory, when we don't care about the contents.  Reading the source
    array requires a cache load, as will writing the modified (copied)
    cache contents back out to memory when the program is finished with
    each cache line: those are costs that cannot be avoided.  However,
    before writing to any memory location, the memory location is
    ``read'' into the cache through the use of the lightweight (1 cycle)
    \verb+dcbz+, and {\bf only then} is written to.  We could think of
    \verb+dcbz+ as a data prefetch operation, although it ignores the
    values of the (destination) array that's being read.  
\end{enumerate}

In other words, the optimized \verb+BlockMove+ routine will access avoid
spurious loads into the cache with \verb+dcbz+, and use blocking so that
all work on a cache line can be completed in a single pass once that
cache line is loaded into the cache -- there's no need for any flushed
cache line to ever return to the cache.  
\end{document}



