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


% Problem 1
\section*{Problem 1}
\bigskip 
{\bf (a)}
Here's the code to implement \verb3EXCH R2,0(R1)3, where \verb3RT13
and \verb3RT23 are temporary registers:

\begin{verbatim}
        ADD     RT2,R2,R0
LOOP:   ADD     R2,RT2,R0
        LL      RT1,0(R1)
        SC      0(R1),R2
        BEQZ    R2,LOOP
        ADD     R2,RT1,R0
\end{verbatim}

\bigskip\noindent
{\bf (b)}

Only slightly more bandwidth would be needed {\bf per message} when writing to 
memory with a store conditional instead of a typical store word.  Store conditionals, 
like store word operations, require that the target memory be invalidated in all 
other caches.  However, an additional bit needs to be appended to these invalidate
messages, to indicate that the ``store'' was a ``store conditional'', and that 
the link registers of the other processors should be examined and possibly invalidated as 
well.

There may also be a higher traffic level generated by store conditionals:
Ten store words in a row to the same address will only cause (at best) one invalidate
message to be generated on the bus to the other caches (the first time).
However, every time the store conditional is executed, the other link registers must
be invalidated.  This means that every store conditional generates an invalidate request
along the bus, a higher rate (if not so much size) of bus messages.

\bigskip\noindent
{\bf (c)}
Here is the optimized code:

\begin{verbatim}
TRY:    LL      R2,0(R1)
        BNEZ    R2,TRY
        ADDI    R2,R0,#1
        SC      0(R1),R2
        BEQZ    R2,TRY
\end{verbatim}

The major advantage here using \verb3LL/SC3 over \verb3EXCH3 is that
the majority of time we check to see if the mutex is free, we only
do a \verb3LL3.  The \verb3EXCH3 instruction does both a load and a
store which adds more traffic to the bus and increases processor
cycles.  So, with this implementation we save bus cycles and decrease
processor cycles.  

\bigskip\noindent
{\bf (d)}
Suppose that we are executing the lock above in two tasks on the same
processor.  If both tasks get to the \verb3ADDI3 instruction (via
context switching) and then both tasks execute the \verb3SC3 command
then they both will obtain the lock--very bad.  The problem here is
that one task cannot cancel the other task's $R_{link}$ register.  One
fix to this is to have multiple $R_{link}$ registers and a task is
assigned to one of these registers.  Then, when the \verb3SC3
instruction is executed in one task all of the inter and intra
registers are cancelled.  Another option would be to keep a stack that
points to where the contexts are stored in memory (and hence points to
the $R_{link}$ register.

\end{document}