\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 1
\section*{Problem 1}
\bigskip 
{\bf (a)}
We need to fetch $3+10*4=43$ instructions.  In bytes, $6+10*8=86$
bytes.  We need to fetch $10*4=40$ bytes of data memory and do not
have to store anything.

\bigskip\noindent
{\bf (b)}
Assume R1: N, R2: a, R3: I, R4: sum, R5: condition register, R6:
temporary register.

\begin{verbatim}
        xorl    %eax,%eax               XOR     R3,R3,R3
        cmpl    %ebx,%eax               SUB     R6,R3,R1
        jge     .L4                     SLTI    R5,R6,#1
                                        BNEZ    R5, .L4
        addl    (%ecx,%eax,4),%edx      SLLI    R6,R3,#2
                                        ADD     R6,R6,R2
                                        LW      R6,0(R6)
                                        ADD     R4,R4,R6
        cmpl    %ebx,%eax               SUB     R6,R3,R1
        jl      .L6                     SGTI    R5,R6,#0 
                                        BNEZ    R5,.L6
\end{verbatim}

\bigskip\noindent
{\bf (c)}
If every DLX instruction uses 4 bytes then we will have to fetch
$(4+10*8)*4=256$ bytes.  We need to fetch the same amount of data
memory, 40 bytes and store 0 bytes.  We see that problem {\bf 1.A} is
more efficient because we only have 1/3 bytes of instructions.  

\bigskip\noindent
{\bf (d)}
Assume: R1: N, R2: a, R3: I, R4: sum, R5: Conditional register, R6: temp

\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:
        LW      R6,0(R2)        # sum += a[I]
        ADD     R4,R4,R6
        ADDI    R2,R2,#4        # a += 4
        SLT     R5,R2,R1
        BNEZ    R5,.L6
.L4:
\end{verbatim}

Therefore we would have $(5+10*4)*4=216$ bytes of instructions to
fetch and we need to fetch $10*4=40$ bytes of data memory and do not
have to store anything.  Therefore we do a lot better then in problem
{\bf 1.B} but still worse than in problem {\bf 1.A}. On the other hand
we do not have so many micro instructions.  

\end{document}