\documentclass[12pt]{article}
\usepackage{fullpage}
\title{CSC 371 homework 1 \\
due 18 Sept, 1995}
\author{Dr. Bloch}

\newenvironment{code}{\setlength{\topsep}{0pt}\texttt\bgroup\begin{tabbing}%
longlabel::\= opcode\= longeroperands\= reallyreallylongcomments\kill}%
{\end{tabbing}\egroup}

\begin{document}
\maketitle
\begin{description}
\item[1.8]
Two instructions are fetched, taking 20 time units. \\
Four operands are loaded, taking 40 time units. \\
Two results are stored, taking 20 time units. \\
Two instructions are decoded, taking 2 time units. \\
Two operations are executed, taking 2 time units.  \\
The program counter is updated before each of the two operations, taking
2 time units. \\
Total: 86 time units.
\item[1.11]
A compiler can be written in machine language, but this is such an
extremely time-consuming and error-prone process that most compilers are
written in high-level languages.  This, however, presents a problem of
infinite regress: where did the compiler for \emph{that} high-level
language come from?

Suppose you want to write a compiler for Machine X.  If another compiler
(presumably for a different high-level language) is already available
for Machine X, you can use that.  If not, find a Machine Y
for which a good compiler is available, and modify that compiler into a
``cross-compiler'' for Machine X: that is, the compiler runs on Machine
Y, but produces executable code for Machine X.  Then you can write your
new compiler, compile it on Machine Y, move the executable code onto
Machine X, and run it.
\item[1.12]
One reason for not delaying the PC update to the end of the
unconditional branch instruction is that it destroys some of the
symmetry of the implementation: in every instruction \emph{except} the
unconditional branch, the PC should be updated to point to the next
instruction.  It turns out often simpler to build hardware that
\emph{always} updates the PC in the same way early on in the
instruction, and updates it again later if necessary.

Another reason has to do with interrupts, exceptions, and error-handling.
When an interrupt or exception occurs during execution of an instruction,
it is handled by a piece of operating system code called a ``trap handler''
which assumes the PC points to the instruction after the one that caused
the error.  If unconditional branch instructions didn't update the PC
until the end, and if an interrupt occurred in the middle of one, the
trap handler might mistakenly think the interrupt had occurred in the
middle of the \emph{previous} instruction.
\item[1.14]
There is no clearly ``right'' answer to this question; all of these
characteristics are considerations in comparing two computers.  If I had
to pick one, however, I would probably choose ``number of instructions
executed per second.''
\begin{itemize}
\item The number of instructions in a computer's instruction set 
indicates how flexible its assembler language is, and how much work can
be done in one instruction.  As such, more instructions are better than
fewer instructions, \emph{unless} implementing the additional
instructions adds significant cost or significantly
decreases the number of instructions executed per second.  The RISC
philosophy holds that a few simple instructions with an inexpensive, fast
implementation are better than a wide variety of powerful instructions
that can only be implemented on an expensive, slow processor.
\item The size of memory determines how big a program and/or data set
the computer can handle at a time.  Many modern computers have virtual
memory, so exceeding this doesn't crash the computer, it merely causes a
degradation in performance.
\item The number of instructions executed per second is a reasonably
good indicator of the speed of the computer, but not entirely a valid
way to compare two computers unless they have the same instruction sets:
a RISC with very fast, but simple, instructions might \emph{or might not}
solve the problem faster than a CISC with slow but powerful
instructions.
\item The size of a particular program affects how much memory you'll
need to run it.  Not terribly important these days, since memory gets
less expensive every year and virtual memory is widespread.
\item The popularity of the computer architecture tells you how many
other people like it, and is therefore an indirect measure of quality.
Unfortunately, it also measures marketing skill and business clout,
neither of which has much bearing on the quality of the computer
itself.  Popularity has another benefit, however: a popular computer
is likely to have a lot of software available to run on it.
\end{itemize}
\item[2.3]
\begin{code}
\> .data \\
z: \> .word \> 15 \> \# or whatever \\
a: \> .word \\
i: \> .word \> \\
sum: \> .word \\
\> .text \\
\> move \> i,2 \\
for: \> bgt \> i,z,endfor \\
\> rem \> a,i,2 \\
\> bnez \> a,incr\_i \\
\> add \> sum,sum,i \\
incr\_i: \> add \> i,i,1 \\
\> b \> for \\
endfor: 
\end{code}
\item[2.10]
As some of you have pointed out, there's a typographical error in the
second code fragment: \texttt{endwhile} should obviously be replaced
by \texttt{continue} (or \emph{vice versa}).  Thus corrected, the number
of instructions executed has the following pattern:

\begin{tabular}{|c|c|c|}
\hline
\texttt{counter} & first method & second method \\
\hline
0 & 3 & 3 \\
1 & 7 & 6 \\
2 & 11 & 9 \\
3 & 15 & 12 \\
\vdots & \vdots & \vdots \\
\hline
\end{tabular}

Thus for all positive values of \texttt{counter}, the second method
executes fewer instructions than the first.  For $\texttt{counter}=0$,
the two methods are tied, and both methods treat negative numbers as 0.
So there is no value of \texttt{counter} for which the second method
executes more instructions than the first.

I believe this is due to another typographical error; I think the authors
intended the following for their second method:
\begin{code}
\> move \> result,1 \\
\> move \> counter,exponent \\
\> b \> continue \\
loop: \> mul \> result,result,base \\
\> sub \> counter,counter,1 \\
continue: \> bgtz \> counter, loop
\end{code}

This would produce the results

\begin{tabular}{|c|c|c|}
\hline
\texttt{counter} & first method & my second method \\
\hline
0 & 3 & 4 \\
1 & 7 & 7 \\
2 & 11 & 10 \\
3 & 15 & 13 \\
\vdots & \vdots & \vdots \\
\hline
\end{tabular}

in which the two algorithms are tied at $\texttt{counter}=1$, not
$\texttt{counter}=0$.  On some machines ``my'' code would be
preferable to the second method as given, because an unconditional
branch is shorter (\emph{i.e.}, takes less memory to represent) than a
conditional branch.  On the MIPS this consideration is less important,
so there is no reason to use ``my'' code fragment.
\item[2.12]
The ``other possible way'' given in the text is one instruction shorter,
both in program size and in number of instructions executed.  There is,
however, one very good reason not to use it: if $A=0$, it causes a
divide-by-zero exception, even though in the Pascal code if $A=0$ no
division is performed at all.  If you can guarantee that $A$ will not be
equal to zero, this alternative code is more efficient.
\end{description}
\end{document}