\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}{3-\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{P1}{DUE: 5/8/2002}{Problem Set 6}
{Instructors: Krste Asanovic, Srinivas Devadas}
{Group 18: Timothy Danford, Kilian Pohl, Bryan Russell}


% Problem 3
\section*{Problem 3}
\bigskip 
{\bf (a)}

\begin{center}
\begin{tabular}{|c|c|c|c|c|} \hline
{\bf No.} & {\bf Current State} & {\bf Event Received} & {\bf Next
State} & {\bf Action} \\ \hline
1 & C-invalid & load & C-transient & load-request $\to$ home \\ \hline
2 & C-invalid & store & C-transient & store-request $\to$ home \\
\hline
3 & C-invalid & invalidate-request & C-invalid & invalidate-reply
$\to$ home \\ \hline
4 & C-invalid & shared-copy-request & C-invalid & shared-copy-reply
$\to$ home \\ \hline
5 & C-invalid & exclusive-copy-request & C-invalid &
exclusive-copy-reply $\to$ home \\ \hline
6 & C-shared & load & C-shared & processor reads cache \\ \hline
7 & C-shared & store & C-transient & store-request $\to$ home \\
\hline
8 & C-shared & replace & C-invalid & nothing \\ \hline
9 & C-shared & invalidate-request & C-invalid & invalidate-reply $\to$
home \\ \hline
10 & C-modified & load & C-modified & processor reads cache \\ \hline
11 & C-modified & store & C-modified & processor writes cache \\
\hline
12 & C-modified & replace & C-invalid & write-back $\to$ home \\
\hline
13 & C-modified & shared-copy-request & C-shared & shared-copy-reply
$\to$ home \\ \hline
14 & C-modified & exclusive-copy-request & C-invalid &
exclusive-copy-reply $\to$ home \\ \hline
15 & C-transient & load-reply & C-shared & data $\to$ cache, processor
reads cache \\ \hline
16 & C-transient & store-reply & C-modified & data $\to$ cache,
processor writes cache \\ \hline
17 & C-transient & invalidate-request & C-transient & retry $\to$ home
\\ \hline
18 & C-transient & shared-copy-request & C-transient & retry $\to$
home \\ \hline
19 & C-transient & exclusive-copy-request & C-transient & retry $\to$
home \\ \hline
\end{tabular}
\end{center}

\bigskip\noindent
{\bf (b)}

\begin{center}
\begin{tabular}{|c|c|c|c|c|} \hline
{\bf No.} & {\bf Current State} & {\bf Message Received} & {\bf Next
State} & {\bf Action} \\ \hline
1 & H-uncached & load-request & H-shared[$\{$k$\}$] & load-reply $\to$ k \\
\hline
2 & H-uncached & store-request & H-modified[k] & store-reply $\to$ k
\\ \hline
3 & H-shared[S] & load-request & H-shared[S $\cup$ $\{$k$\}$] & load-reply
$\to$ k \\ \hline
4 & H-shared[S] & store-request & H-transient & invalidate-request
$\to$ S \\ \hline
5 & H-modified[m] & load-request & H-transient & shared-copy-request
$\to$ m \\ \hline
6 & H-modified[m] & store-request & H-transient &
exclusive-copy-request $\to$ m \\ \hline
7 & H-modified[m] & write-back & H-uncached & data $\to$ memory \\
\hline
8 & H-transient & load-request & H-transient & retry $\to$ j \\ \hline
9 & H-transient & store-request & H-transient & retry $\to$ j \\
\hline
10 & H-transient & write-back & H-unchanged & data $\to$ memory \\
\hline
11 & H-transient[count $>$ 1] & invalidate-reply & H-transient[--count]
& nothing \\ \hline
12 & H-transient[count = 1] & invalidate-reply & H-modified[k] &
store-reply $\to$ k \\ \hline
13 & H-transient & shared-copy-reply & H-shared[$\{$m,k$\}$] & data $\to$
memory, \\
 & & & & load-reply $\to$ k \\ \hline
14 & H-transient & exclusive-copy-reply & H-modified[k] & store-reply
$\to$ k \\ \hline
\end{tabular}
\end{center}

\bigskip\noindent
{\bf (c)}
Suppose that as the home site sends the
exclusive-copy-request message to a given site and then site
encounters a replace command.  The replace
command simply results in sending the one-way write-back
message to the home site and changing the state to
C-invalid.  Now, if the site encounters a load
or store command before the original
exclusive-copy-request arrives to the site, the site's
state then changes to C-transient (and a load-request or
store-request is sent to the home site).  This is how the scenario in
line 19 can be reached.

\bigskip\noindent
{\bf (d)}
If the network is non-FIFO, then we can get into an undesired state.
Suppose that a cache $m$ that is in state $C-modified$ wishes to
$write \ back$ (i.e. $replace$) and then $store$ data.  With the FIFO
assumption, the cache switches to the $C-invalid$ state, sends a
$store-request$ to the home site, switches to the $C-transient$ state,
receives a $store-reply$, and then switches to state $C-modified$.
The home site goes from $H-modified[m]$ to $H-uncached$ and then back
to $H-modified[m]$.  Without the FIFO assumption, the $store-request$
can get to the home site before the $write-back$ message.  So, the
home site will then change to $H-transient$ and send an
$exclusive-copy-request$ back to the cache site.  Since the cache site
is in $C-transient$ state (after sending the $store-request$), it is
waiting for a $store-reply$.  However, when the cache site receives
the $exclusive-copy-request$, the cache site returns a $retry$ back to
the home site.  So, the home site will continue to $retry$ the
$exclusive-copy-request$.  Now, when the $write-back$ message arrives
to the home site, the state then changes to $H-uncached$.  So, the end
result is the home site having an incorrect state ($H-uncached$
instead of $H-modified$) and there will be the
$exclusive-copy-request$/$retry$ message bouncing back and forth
between the cache and home sites.  

If, for some reason, there is a modification to the protocol such that, 
when a home directory gets a store-request from a cache that already owns
the data, there is a way to simply pass along a ``permission'' message for
the owning cache to go ahead and write to the address that already belongs 
to it: 

If that addition is made to the protocol, there is still a problem.

Then the cache line can be written to and replaced (generating a write-back)
twice, which would generate two different write-backs with two different 
values in transit to the same directory at the same time.

And because the network isn't FIFO, that would mean that the write-backs 
could appear in the wrong order, causing an incorrect value to be written
in the home directory.

\end{document}



