\documentstyle[12pt]{article}
% \pagestyle{empty}

%set dimensions of columns, gap between columns, and space between paragraphs
\setlength{\textheight}{8.75in}
\setlength{\columnsep}{2.0pc}
\setlength{\textwidth}{6.8in}
\setlength{\footheight}{0.0in}
\setlength{\topmargin}{0.0in}
\setlength{\headheight}{0.0in}
\setlength{\headsep}{0.0in}
\setlength{\oddsidemargin}{-.19in}
\setlength{\evensidemargin}{-.19in}
\setlength{\parindent}{1pc}

% \setlength{\textwidth}{480pt}
% \setlength{\oddsidemargin}{-15pt}
% \setlength{\evensidemargin}{-15pt}
% \setlength{\topmargin}{0pt}
% \setlength{\textheight}{640pt}
% \setlength{\footskip}{15pt}
% \setlength{\footheight}{15pt}

% \newenvironment{proof}%
% {\relax{\noindent\sc Proof.\ \ }}%
% {\ifhmode\nobreak\qed\par\fi\medskip}

% \newcommand{\forprelim}[1]{#1}
% \newcommand{\forfinal}[1]{\mbox{}}

\def\Mbase/{{\sl Mbase}}
\def\Mopt/{{\sl Mopt}}
\def\Mcomp/{{\sl Mcomp}}
\def\Mboth/{{\sl Mboth}}
\def\CPI/{\mbox{ CPI}}
\def\MIPS/{\mbox{ MIPS}}
\def\speedup/{\mbox{ speedup}}
\def\time/{\mbox{ time}}
\def\MHz/{\mbox{ MHz}}

\newcommand{\Hz}{\mbox{ cycles/second}}
\newcommand{\cpi}{\mbox{ cycles/instruction}}
\newcommand{\ic}{\mbox{ instruction count}}
\newcommand{\ct}{\mbox{ cycle time}}

\newcommand{\bea}{\begin{eqnarray*}}
\newcommand{\eea}{\end{eqnarray*}}

\begin{document}

\title{Computer Science 371 \\
Homework 1 solutions}

\author{Dr. Stephen Bloch}

\maketitle

Assignment: problems 2.14--2.20, 2.32,2.33.

For problems 2.14--2.20, notice that the data are given to two
significant figures, so it makes no sense to report answers to greater
accuracy than that.  However, I'll keep intermediate results of calculations
to a few places more.

\begin{enumerate}
\item[2.14]
\bea
\Mbase/ \CPI/ & = & (2 \cdot 0.4) + (3 \cdot 0.25) + (3\cdot 0.25)+(5\cdot 0.1) \\*
& = & 2.8 \CPI/ \\*
\Mopt/ \CPI/ & = & (2\cdot 0.4)+(2\cdot 0.25)+(3\cdot 0.25)+(4\cdot 0.1) \\*
& = & 2.45 \CPI/
\eea

\item[2.15]
\bea
\Mbase/ \MIPS/ & = & \frac{50 \cdot 10^6 \Hz} {2.8 \cpi \cdot 10^6} \\*
& \approx & 17.8571 \mbox{ \MIPS/ for further computations, or} \\*
& \approx & 18 \mbox{ \MIPS/, reporting to two significant figures.} \\*
\Mopt/ \MIPS/ & = & \frac{60 \cdot 10^6 \Hz}{2.45 \cpi \cdot 10^6} \\*
& \approx & 24.4897 \mbox{ \MIPS/ for further computations, or} \\*
& \approx & 24 \mbox{ \MIPS/, to two significant figures.}
\eea

\item[2.16]
\bea \Mopt/ \speedup/ & = & \frac{\Mbase/ \time/}{\Mopt/ \time/} \\*
& = & \frac{\ic / \Mbase/ \MIPS/}{\ic / \Mopt/ \MIPS/} \\*
& = & \frac{\Mopt/ \MIPS/}{\Mbase/ \MIPS/} \\*
& \approx & 24.4897 / 17.8571 \\*
& \approx & 1.3714 \mbox{ times faster, or} \\*
& \approx & 1.4 \mbox{ times faster to two significant figures.}
\eea

A slightly different approach is the following:

\bea \Mopt/ \speedup/ & = & \frac{\Mbase/ \time/}{\Mopt/ \time/} \\*
& = & \frac{\ic \cdot \Mbase/ \CPI/ \cdot \Mbase/ \ct}
           {\ic \cdot \Mopt/ \CPI/ \cdot \Mopt/ \ct} \\*
& = & \frac{2.8 \cdot 60 \MHz/}{2.45 \cdot 50 \MHz/} \\*
& \approx & 1.3714 \mbox{ times faster, or} \\*
& \approx & 1.4 \mbox{ times faster to two significant figures.}
\eea

\item[2.17]
You can do this in at least two different ways.  Suppose a program takes
$IC$ instructions on \Mbase/.  First, you can compute the instruction mix
(analogous to the table in 2.14.a) for \Mcomp/, and
then compute \CPI/ as you did for \Mcomp/.  Alternatively, you can compute
how many cycles the whole program takes on \Mcomp/, and divide by how many
instructions it takes on \Mcomp/.

\begin{tabular}{|c|r|}
\hline
Instruction class & number of instructions \\*
\hline
A & $0.9\cdot 0.4 IC = 0.36 IC$ \\*
B & $0.9\cdot 0.25 IC = 0.225 IC$ \\*
C & $0.85\cdot 0.25 IC = 0.2125 IC$ \\*
D & $0.95\cdot 0.1 IC = 0.095 IC$ \\*
\hline
Total & $0.8925 IC$ \\*
\hline
\end{tabular}

First approach:

\begin{tabular}{|c|c|r|r|}
\hline
Instruction class & CPI & Frequency & Weighted Contribution \\*
\hline
A & 2 & $\frac{0.36 IC}{0.8925 IC} = 0.4033$ & 0.8066 \\*
B & 3 & $\frac{0.225 IC}{0.8925 IC} = 0.2521$ & 0.7563 \\*
C & 3 & $\frac{0.2125 IC}{0.8925 IC} = 0.2380$ & 0.7140 \\*
D & 5 & $\frac{0.095 IC}{0.8925 IC} = 0.1064$ & 0.5320 \\*
\hline
Total & & 0.9998 & 2.8089 \\*
\hline
\end{tabular}

The third column really {\em should} add up to exactly 1, but it doesn't
due to rounding errors.  On the assumption that the rounding errors
affected the fourth column the same way, we'll report that \Mcomp/ has
an average $\frac{2.8089}{0.9998} \approx 2.8094$ \CPI/,
which (reporting to two significant figures) is 2.8.

Second approach:

\begin{tabular}{|c|c|c|c|}
\hline
Instruction class & CPI & number of instructions & number of cycles \\*
\hline
A & 2 & 0.36 IC & $2\cdot 0.36 IC = 0.72 IC$ \\*
B & 3 & 0.225 IC & $3\cdot 0.225 IC = 0.675 IC$ \\*
C & 3 & 0.2125 IC & $3\cdot 0.2125 IC = 0.6375 IC$ \\*
D & 5 & 0.095 IC & $5\cdot 0.095 IC = 0.475 IC$ \\*
\hline
total & & 0.8925 IC & 2.5075 IC \\*
\hline
\end{tabular}

\bea
\Mcomp/ \CPI/ & \approx & \frac{2.5075 IC \mbox{ cycles}}{0.8925 IC \mbox{
instructions}} \\*
& \approx & 2.8095 \mbox{ \CPI/, or} \\*
& \approx & 2.8 \mbox{ \CPI/ to two significant figures.}
\eea

The discrepancy between 2.8094 and 2.8095 is due to rounding errors.
Since the second approach takes slightly fewer arithmetic operations,
we'll assume it's more likely correct.

\item[2.18]
\bea
\Mcomp/ \speedup/ & = & \frac{\Mbase/ \time/}{\Mcomp/ \time/} \\*
& = & \frac{\Mbase/ \ic \cdot \Mbase/ \CPI/ \cdot \ct}
           {\Mcomp/ \ic \cdot \Mcomp/ \CPI/ \cdot \ct} \\*
& \approx & \frac{IC \cdot 2.8}{0.8925 IC \cdot 2.8095} \\*
& \approx & 1.1166 \mbox{ times faster, or} \\*
& \approx & 1.1 \mbox{ times faster to two significant places.}
\eea

\item[2.19]
First we need to compute the \CPI/ for \Mboth/, the machine with both
enhancements.  We can still use the first table in problem 2.17, and
we'll use the second approach of problem 2.17.

\begin{tabular}{|c|c|c|c|}
\hline
Instruction class & CPI & number of instructions & number of cycles \\*
\hline
A & 2 & 0.36 IC & $2\cdot 0.36 IC = 0.72 IC$ \\*
B & 2 & 0.225 IC & $2\cdot 0.225 IC = 0.450 IC$ \\*
C & 3 & 0.2125 IC & $3\cdot 0.2125 IC = 0.6375 IC$ \\*
D & 4 & 0.095 IC & $4\cdot 0.095 IC = 0.380 IC$ \\*
\hline
total & & 0.8925 IC & 2.1875 IC \\*
\hline
\end{tabular}

\bea
\Mcomp/ \CPI/ & \approx & \frac{2.1875 IC \mbox{ cycles}}{0.8925 IC
\mbox{ instructions}} \\*
& \approx & 2.4509 \CPI/
\eea

Now, to compute how much faster \Mboth/ is than \Mbase/,

\bea
\Mboth/ \speedup/ & = & \frac{\Mbase/ \time/}{\Mboth/ \time/} \\*
& = & \frac{\Mbase/ \ic \cdot \Mbase/ \CPI/ \cdot \Mbase/ \ct}
           {\Mboth/ \ic \cdot \Mboth/ \CPI/ \cdot \Mboth/ \ct} \\*
& \approx & \frac{IC \cdot 2.8 / 50 \MHz/}
           {.8925 IC \cdot 2.4509 / 60 \MHz/} \\*
& \approx & \frac{2.8 \cdot 60}{.8925 \cdot 2.4509 \cdot 50} \\*
& \approx & 1.5360, \mbox{ or} \\*
& \approx & 1.5 \mbox{ times faster, to two significant places.}
\eea

\item[2.20]
We need to decide which optimization(s) will give us the best edge on
the competition, {\em i.e.}, the best ratio between our performance and
what they've presumably got by the same time.

\begin{tabular}{|c|c|c|c|c|}
\hline
Machine & Time to implement & Speedup & Competition's speedup &
Edge \\*
\hline
\Mbase/ & 0 months & 1.0000 & 1.000 & 1.000 \\*
\Mopt/ & 6 months & 1.3714 & $(1.034)^6 \approx 1.2221$ & 1.1221 \\*
\Mcomp/ & 6 months & 1.1168 & $(1.034)^6 \approx 1.2221$ & 0.9138 \\*
\Mboth/ & 8 months & 1.5360 & $(1.034)^8 \approx 1.3066$ & 1.1755 \\*
\hline
\end{tabular}

Implementing both looks the best, followed by implementing only the
hardware improvements.  Implementing only the compiler improvements
would actually {\em lose} competitive edge in this case.

\item[2.32]  If half of the 10 seconds are spent on floating point
operations, then we're currently spending 5 seconds on floating point
and 5 seconds on other stuff.  The floating point enhancement will
reduce the former to 1 second, but not affect the latter, so after the
enhancement the benchmark will take 6 seconds.  

To look at it another way,

\bea
\mbox{time after improvement} & = &
\frac{\mbox{time affected}}{\mbox{amount of improvement}} +
\mbox{time unaffected} \\*
& = & \frac{5 \mbox{ sec}}{5} + 5 \mbox{ sec}\\*
& = & 6 \mbox{ sec}
\eea

The speedup is $\frac{10}{6} \approx 1.7$.

\item[2.33]
\bea
3 & = & \mbox{speedup} \\*
& = & \frac{\mbox{time before improvement}}{\mbox{time after improvement}} \\*
& = & \frac{100}{\mbox{time after improvement}} \\*
33 \; 1/3 & = & \mbox{time after improvement}
\eea
so the benchmark had better run in about 33 1/3 seconds after the
improvement.

\bea
33 \; 1/3 & = & \mbox{time after improvement} \\*
& = & \frac{\mbox{time affected}}{\mbox{amount of improvement}} +
		\mbox{time unaffected} \\*
& = & \frac{\mbox{time affected}}{5} + \mbox{time unaffected} \\*
166 \; 2/3 & = & \mbox{time affected} + 5\cdot \mbox{time unaffected} \\*
& = & \mbox{time affected} + 5\cdot (100-\mbox{time affected}) \\*
& = & 500 - 4\cdot\mbox{time affected} \\*
333 \; 1/3 & = & 4 \cdot \mbox{time affected} \\*
83 \; 1/3 & = & \mbox{time affected}
\eea
so if we want to show a factor of 3 speedup, we need to use a benchmark
that's about 83\% floating point.

\end{enumerate}

\end{document}
