\documentclass[12pt]{report}

\usepackage{amstext}

%\topmargin=-0.5in
%\oddsidemargin=-0.5in
%\textwidth=6.5in
%\textheight=9in

\begin{document}
\begin{center}
	{\bf CS 222/322 -- Machine Organization}\\
	{\bf Take-Home Midterm Exam, Winter 1998}\\
	Due Wednesday, 18 February, 1:30 PM \\
        7 problems on pages 2--6
\end{center}

\begin{itemize}

\item This is a self-timed exam.  Please limit yourself to 2 working hours
from the time that you open the paper, until you complete the
solutions that you hand in. You may take a break up to 15 minutes
during the exam.

\item You may use the textbook, my class materials, any other published
material, and notes of your own. You definitely need the textbook, and
the chart that I created on the Web showing the DLX pipeline. You
don't need a calculator, but you may use one if you like. Do not
discuss the exam with anyone except me.

\item There are 6 problems for Com Sci 222 and 322. They cover preliminary
material, and the three chapters of the text, with one or two problems
for each of those sections. There is one additional problem for Com
Sci 322 only. Each numbered problem is weighted equally for grading
purposes.

\item The problem statements are a bit wordy, since I will not be nearby to
answer questions. The wordiness does \emph{not} not indicate subtlety.

\item Please deliver your finished exam to me at the beginning of class.

\end{itemize}

\newpage

\section*{Com Sci 222 and 322}

\begin{enumerate}

  \item Some computers have hardware for arithmetic in base 10 to
  support business software. Base 10 is too bulky for an exam, so
  we'll look at base 3. Each base 3 (trinary) digit requires two
  binary bits. A 1-digit base 3 adder has five bits of input: $a_1$,
  $a_0$, $b_1$, $b_0$, and $c_{\text{in}}$, where

    \begin{center}\begin{tabular}{rl}
      $a_1a_0$ & represents one base 3 digit \\
      $b_1b_0$ & represents the other base 3 digit\\
      $c_{\text{in}}$ & is the carry coming in
    \end{tabular}\end{center}

  The base 3 digits are represented as follows

    \begin{center}\begin{tabular}{||c|c||}
      \hline\hline
      digit & binary code \\
      \hline\hline
      0 & 00 \\
      \hline
      1 & 01 \\
      \hline
      2 & 10 \\
      \hline\hline
    \end{tabular}\end{center}

  So, if $a_1=1$, $a_0=0$, $b_1=0$, $b_0=1$, and $c_{\text{in}}=0$,
  then we are adding the trinary digit 2 to the trinary digit 1, with
  no carry coming in. We never have $a_1=a_0=1$, nor $b_1=b_0=1$,
  since those values don't correspond to a trinary digit.

  Write a boolean formula in sum of products form, expressing the
  carry out ($c_{\text{out}}$) in terms of the five input bits. You
  should get a sum of six products, and each product involves two or
  three input bits.

  \item The left column below lists some choices that you might make
  in the design of a computer. The right column lists some types of
  technology whose qualities might lead to those choices. Make a
  one-to-one matching between the columns, showing the most likely
  correspondence of design choices to the types of technology
  affecting them most strongly.

    \begin{center}\begin{tabular}{ll}
      \textbf{Design Choice} & \textbf{Technology} \\
      \hline
      1. bitplane structure in memory, ALU & A. silicon fabrication \\
      2. many general-purpose registers & B. circuit design \\
      3. load/store instruction set & C. non-CPU hardware (bus, RAM, \dots) \\
      4. small CPU chip & D. compilers/software
    \end{tabular}\end{center}

  \item In problem 1.4 in the text, we found that the proposed change
  from a pure load/store instruction set to a machine with some
  register-memory instructions eliminated 10.75 load instructions per
  100 load/store instructions, converting 10.75 old register-register
  ALU instructions to new register-memory ALU instructions, thereby
  saving 10.75 clock cycles. But, it paid 24 extra clock cycles per
  100 load/store instructions because branches take longer, for a net
  increase of 13.25 cycles. Suppose that we find a way to implement
  the new register-memory instructions \emph{without} adding a clock
  cycle to the execution of branch instructions, but instead by
  slowing down all clock cycles from 2 nanoseconds to $2\cdot s$
  nanoseconds, for some $s>1$.

    \begin{enumerate}

      \item For what values of $s$ do the new register-memory
      instructions improve performance?

      \item Suppose that we can \emph{also} add ALU operations that
      combine two values from registers, but store the result in
      memory (e.g., \emph{add R1 and R2, storing at address 1000 in
      memory}), at the cost of slowing down clock cycles by the same
      factor of $s$. The new save-result-to-memory ALU operations
      allow many store instructions to be eliminated, saving one clock
      cycle for each. Which kinds of stores can be eliminated, and
      which cannot? Let $n$ be the fraction of store instructions that
      can be eliminated ($0\leq n\leq 1$). What relationship between
      $s$ and $n$ causes the new design to beat the original
      load/store design? If $n=1$, for what values of $s$ does the new
      design win? In a program that does mainly number crunching, do
      you think $n$ is likely to be nearer to 0 or to 1?

    \end{enumerate}

  \item Explain very briefly why a machine with a better MIPS rating
  may be slower than a machine with a worse MIPS rating. 2 or 3
  sentences should be enough.

\newpage

  \item This is a variation on problem 2.3 in the text, comparing a
  memory-memory instruction set to a load/store instruction set for
  total bytes of memory traffic.

    \begin{enumerate}

      \item Write a program fragment consisting of a sequence of
      assignments in a high-level language that performs 5 integer
      operations. (That is, give a slightly larger example similar to
      the one in the statement of problem 2.3). You may use any number
      of variables, and you may write 5 assignments with 1 operation
      each, 1 assignment with 5 operations, or anything in
      between. Make the memory-memory instruction set beat the
      load/store instruction set by the largest factor that you can
      manage, counting total code and data. Report the total number of
      code bytes and date bytes transmitted for each instruction
      set. You do \emph{not} have to write out the assembly code.

      \item Write another program fragment with the same restrictions
      as in part a, but this time make the load/store instruction set
      win by the largest factor that you can manage. Report the total
      number of code bytes and data bytes transmitted for each
      instruction set.

      \item Clearly, the relative efficiency of memory-memory vs.\
      load/store depends on the program. Do loops in programs tend to
      tip the efficiency balance toward memory-memory, or toward
      load/store? Explain briefly (3 sentences can be enough).

    \end{enumerate}

\newpage

  \item Look at the table describing the DLX pipeline that I provided
  on the Web. Compare a nonpipelined implementation of DLX with a
  pipelined version based on this table. Assume that each stage takes
  one clock cycle in the pipelined version, and that each nonpipelined
  load, store, ALU, and branch instruction takes a number of clock
  cycles equal to the nonidle stages in the pipelined implementation.
  Assume that the clock cycle is 10 nanoseconds unpipelined and 11
  nanoseconds pipelined. For hazards:
    \begin{itemize}

      \item All data hazards stall until the write is finished (no
        forwarding of any sort).

      \item For branches and jumps, predict they are not taken. Cancel
      the 3 instructions in the pipeline behind a branch that is
      taken.

    \end{itemize}

    I tried to produce bad pipeline behavior. The following
    loop decrements R1 from 1000 to 0.
%
    \begin{center}\begin{tabular}{rll}
            & ADDI & R1, R0, \#1000\\
      loop: & SUBI & R1, R1, \#1 \\
            & BNEZ & R1, loop \\
    \end{tabular}\end{center}
%
  There are plenty of instructions after the loop, but we don't care
  what they are.

    \begin{enumerate}

      \item Compute and compare the running time for this loop in the
      pipelined and unpipelined machines. The pipeline loses the race
      by a very small margin.

      \item Point out where data and control values already computed
      in the simple DLX pipeline could be forwarded to speed up the
      pipeline on this program, and compute the improved running time.

    \end{enumerate}

\end{enumerate}

\newpage

\section*{Com Sci 322 only}

\begin{enumerate}
\setcounter{enumi}{6}

  \item Figures 3.22 and 3.23 on pages 163--164 show how to use an
  adder in the ID stage to reduce stalls due to branches.
    \begin{enumerate}

       \item How does the resolution of branches in the ID stage
       change the pipeline performance in Problem 6?

       \item For a very short loop, every instruction may be in the
       pipeline simultaneously. Propose a forwarding of information
       that takes advantage of the presence of both loop instructions
       in the pipeline to save one more machine cycle in the loop
       above. Be precise about which stage provides the forwarded
       information and which stage uses it. How long could a loop be
       and still have a reasonable chance to benefit from this trick?

    \end{enumerate}

\end{enumerate}

\end{document}
