\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: 2/27/2002, EXTENSION: 3/4/2002}{Problem Set 1}
{Instructors: Krste Asanovic, Srinivas Devadas}
{Timothy Danford, Killian Pohl, Bryan Russell}


% Problem 4
\section*{Problem 4}
\bigskip\noindent
{\bf (a)}
From problem {\bf 1.D}, only 1 temporary register is required (namely
$R6$).  For $n=10$, there are $5*10+4=54$ dynamic instructions
(instructions executed at run-time).

\bigskip\noindent
{\bf (b)}
Using the indirect addressing-mode for arithmetic instructions, we get
the following code sequence:

\begin{verbatim}
        SLLI    R1,R1,#2        # Get 4*N...
        ADD     R1,R1,R2        # ...to set N = a + 4*N
        SLT     R5,R2,R1
        BEQZ    R5,.L4
.L6:
        ADD     R4,(R2)         # sum += *(a)
        ADDI    R2,R2,#4        # a += 4
        SLT     R5,R2,R1
        BNEZ    R5,.L6
.L4:
\end{verbatim}

Now, we do not use any temporary registers (we only use $R1-R4$ and
the condition register $R5$).  We now have $4*10+4=44$ dynamic
instructions for this code sequence.

\bigskip\noindent
{\bf (c)}
Using the auto-increment addressing-mode for arithmetic instructions,
we get the following code sequence:

\begin{verbatim}
        SLLI    R1,R1,#2        # Get 4*N...
        ADD     R1,R1,R2        # ...to set N = a + 4*N
        SLT     R5,R2,R1
        BEQZ    R5,.L4
.L6:
        ADD     R4,(R2)+        # sum += *(a); a += d;
        SLT     R5,R2,R1
        BNEZ    R5,.L6
.L4:
\end{verbatim}

Again, we do not use any temporary registers.  We now have $3*10+4=33$
dynamic instructions for this code sequence.

\bigskip\noindent
{\bf (d)}
To add indirect addressing, we need to add a datapath from the ``A''
register in the Execution (EX) stage to the registers between the
Execution and Memory access (MEM) stages and add an ALU in the MEM
stage.  The input to be added ALU in the MEM stage would be the
forwarded ``A'' register and the output from the Data Memory.  The
result would then be written back to the Register (``A'') in the Write
Back (WB) pipe stage.

To add auto-increment addressing, we would need the above plus an
additional ALU in the MEM pipe stage (2 ALUs in total in the MEM pipe
stage).  The second ALU would take the register holding the address
and add the constant ``d'' to it.  Then the output from both ALUs
would then be written to the Registers in the WB pipe stage.

For both cases, we might encounter timing issues.  By adding the ALU
operation after the data memory read, we increase the amount of time
that needs to be spent in the MEM pipe stage.  To fix this, we may
have to change the clock speed which will cause the overall pipeline
to slow down.

\end{document}