\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}