\documentclass[a4paper,11pt]{article}

\usepackage[brazil]{babel}
\usepackage[latin1]{inputenc}
\usepackage[T1]{fontenc}
\usepackage{amsmath}


\begin{document}

\begin{enumerate}

\item[1.1] In this exercise, assume that we are considering enhancing a machine
  by adding a vector mode to it. When a computation is run in vector mode it is
  20 times faster than the normal mode of execution. We call the percentage of
  time that could be spent using vector mode the \emph{percentage of
  vectorization}. Vectors are discussed in Appendix B, but you don't need to
  know anything about how they work to answer this question!

  \begin{enumerate}

  \item Draw a graph that plots the speedup as a percentage of the computation
    performed in vector mode. Label the $y$ axis ``Net speedup'' and label the
    $x$ axis ``Percent vectorization''.


  \item What percentage of vectorization is needed to achieve a speedup of 2?


  \item What percentage of vectorization is needed to achieve one-half the
    maximum speedup attainable from using vector mode?


  \item Suppose you have measured the percentage of vectorization for programs
    to be 70\%. The hardware design group says they can double the speed of the
    vector rate with a significant additional engineering investment. You
    wonder whether the compiler crew could increase the use of vector mode as
    another approach to increasing performance. How much of an increase in the
    percentage of vectorization (relative to current usage) would you need to
    obtain the same performance gain? Which investment would you recommend?


  \end{enumerate}


\item[1.2] Assume --- as in the Amdahl's Law Example on page 30 --- that we
  make an enhancement to a computer that improves some mode of execution by a
  factor of 10. Enhanced mode is used 50\% of the time, measured as a
  percentage of the execution time \emph{when the enhanced mode is in use}.
  Recall that Amdahl's Law depends on the fraction of the original,
  \emph{unenhanced} execution time that could make use of enhanced mode. Thus,
  we cannot directly use this 50\% measurement to compute speedup with Amdahl's
  Law.

  \begin{enumerate}

  \item What is the speedup we have obtained from fast mode?


  \item What percentage of the original execution time has been converted to
    fast mode?


  \end{enumerate}


\item[1.5] Assume that we have a machine that with a perfect cache behaves as
  given in Table~\ref{tab:1.5}.

  \begin{table}[t]
    \centering
    \begin{tabular}{lcc}
      \hline
      \emph{Instruction type} & \emph{Frequency} & \emph{Clock cycle count} \\
      \hline
      ALU ops  & 43\% & 1 \\
      Loads    & 21\% & 2 \\
      Stores   & 12\% & 2 \\
      Branches & 24\% & 2 \\
      \hline
    \end{tabular}
    \caption{\textbf{Measurements of the load-store machine.}}
    \label{tab:1.5}
  \end{table}

  With a cache, we have measured that instructions have a miss rate of 5\%,
  data references have a miss rate of 10\%, and the miss penalty is 40 cycles.
  Find the CPI for each instruction type with cache misses and determine how
  much faster the machine is with no cache misses versus with cache misses.


\item[1.8] This exercise estimates the complete packaged cost of a
  microprocessor using the die cost equation and adding in packaging and
  testing costs. We begin with a short description of testing cost and follow
  with a discussion of packaging issues.

  Testing is the second term of the chip cost equation:
  %
  \begin{equation*}
    \text{Cost of integrated circuit} = \frac{\text{Cost of die} +
    \text{Cost of testing die} + \text{Cost of packaging}}
    {\text{Final test yield}}
  \end{equation*}

  Testing costs are determined by three components:
  %
  \begin{equation*}
    \text{Cost of testing die} = \frac{\text{Cost of testing per hour} \times
    \text{Average die test time}}{\text{Die yield}}
  \end{equation*}

  Since bad dies are discarded, die yield is in the denominator in the equation
  --- the good must shoulder the costs of testing those that fail. (In
  practice, a bad die may take less time to test, but this effect is small,
  since moving the probes on the die is a mechanical process that takes a large
  fraction of the time.) Testing costs about \$50 to \$500 per hour, depending
  on the tester needed. High-end designs with many high-speed pins require the
  more expensive testers. For higher-end microprocessors test time would run
  \$300 to \$500 per hour. Die tests take about 5 to 90 seconds on average,
  depending on the simplicity of the die and the provisions to reduce testing
  time included in the chip.

  The cost of a package depends on the material used, the number of pins, and
  the die area. The cost of the material used in the package is in part
  determined by the ability to dissipate power generated by the die. For
  example, a \emph{plastic quad flat pack} (PQFP) dissipating less than 1 watt,
  with 208 or fewer pins, and containing a die up to 1 cm on a side costs \$2
  in 1995. A ceramic \emph{pin grid array} (PGA) can handle 300 to 600 pins and
  a larger die with more power, but it costs \$20 to \$60. In addition to the
  cost of the package itself is the cost of the labor to place a die in the
  package and then bond the pads to the pins, which adds from a few cents to a
  dollar or two to the cost. Some good dies are typically lost in the assembly
  process, thereby further reducing yield. For simplicity we assume the final
  test yield is 1.0; in practice it is at least 0.95. We also ignore the cost
  of the final packaged test. This exercise requires the information provided
  in Table~\ref{tab:1.8a}.

  \begin{table}[t]
    \centering\small
    \begin{tabular}{lcclcl}
      \hline
      & \emph{Die area} & & & \emph{Estimated} \\
      \emph{Microprocessor} & \emph{(mm$²$)} & \emph{Pins} & \emph{Technology}
      & \emph{wafer cost (\$)} & \emph{Package} \\
      \hline
      MIPS 4600      & 77  & 208 & CMOS, 0.6$\mu$, 3M     & 3200 & PQFP \\
      PowerPC 603    & 85  & 240 & CMOS, 0.6$\mu$, 4M     & 3400 & PQFP \\
      HP 71x0        & 196 & 504 & CMOS, 0.8$\mu$, 3M     & 2800 & Ceramic PGA \\
      Digital 21064A & 166 & 431 & CMOS, 0.5$\mu$, 4.5M   & 4000 & Ceramic PGA \\
      SuperSPARC/60  & 256 & 293 & BiCMOS, 0.6$\mu$, 3.5M & 4000 & Ceramic PGA \\
      \hline
    \end{tabular}
    \caption{\textbf{Characteristics of microprocessors.} The technology entry
    is the process type, line width, and number of interconnect levels.}
    \label{tab:1.8a}
  \end{table}

  \begin{enumerate}

  \item For each of the microprocessors in Table~\ref{tab:1.8a}, compute the
    number of good chips you would get per 20-cm wafer using the model on page
    12. Assume a defect density of one defect per cm$²$, a wafer yield of
    95\%, and assume $\alpha = 3$.


  \item For each microprocessor in Table~\ref{tab:1.8a}, compute the cost per
    projected good die before packaging and testing. Use the number of good
    dies per wafer from part (a) of this exercise and the wafer cost from
    Table~\ref{tab:1.8a}.


  \item Both package cost and test cost are proportional to pin count. Using
    the additional assumption shown in Table~\ref{tab:1.8b}, compute the cost
    per good, tested, and packaged part using the costs per good die from part
    (b) of this exercise.

    \begin{table}[t]
      \centering
      \begin{tabular}{lcccc}
        \hline
        & & \emph{Package} & \emph{Test time} & \emph{Test per} \\
        \emph{Package type} & \emph{Pin count} & \emph{cost (\$)} & \emph{(secs)} &
        \emph{hour (\$)} \\
        \hline
        PQFP & <220 & 12 & 10 & 300 \\
        PQFP & <300 & 20 & 10 & 320 \\
        Ceramic PGA & <300 & 30 & 10 & 320 \\
        Ceramic PGA & <400 & 40 & 12 & 340 \\
        Ceramic PGA & <450 & 50 & 13 & 360 \\
        Ceramic PGA & <500 & 60 & 14 & 380 \\
        Ceramic PGA & >500 & 70 & 15 & 400 \\
        \hline
      \end{tabular}
      \caption{\textbf{Package and test characteristics.}}
      \label{tab:1.8b}
    \end{table}


  \item There are wide differences in defect densities between semiconductor
    manufacturers. Find the costs for the largest processor in
    Table~\ref{tab:1.8a} (total cost including packaging), assuming defect
    densities are 0.6 per cm$²$ and assuming that defect densities are 1.2
    per cm$²$.


  \item The parameter $\alpha$ depends on the complexity of the process.
    Additional metal levels result in increased complexity. For example,
    $\alpha$ might be approximated by the number of interconnect levels. For
    the Digital 21064a with 4.5 levels of interconnect, estimate the cost of
    working, packaged, and tested die if $\alpha = 3$ and if $\alpha = 4.5$.
    Assume a defect density of 0.8 defects per cm$²$.


  \end{enumerate}


\item[1.13] Your company has a benchmark that is considered representative of
  your typical applications. One of the older-model workstations does not have
  a floating-point unit and must emulate each floating-point instruction by a
  sequence of integer instructions. This older-model workstation is rated at
  120 MIPS on this benchmark. A third-party vendor offers an attached processor
  that is intended to give a ``mid-life kicker'' to your workstation. That
  attached processor executes each floating-point instruction on a dedicated
  processor (i.e., no emulation is necessary). The workstation/attached
  processor rates 80 MIPS on the same benchmark. The following symbols are used
  to answer parts (a)--(e) of this exercise.

  $I$ --- Number of integer instructions executed on the benchmark.

  $F$ --- Number of floating-point instructions executed on the benchmark.

  $Y$ --- Number of integer instructions to emulate a floating-point
  instruction.

  $W$ --- Time to execute the benchmark on the workstation alone.

  $B$ --- Time to execute the benchmark on the workstation/attached processor
  combination.

  \begin{enumerate}

  \item Write an equation for the MIPS rating of each configuration using the
    symbols above. Document your equation.


  \item For the configuration without the coprocessor, we measure that $F = 8
    \times 10^6$, $Y = 50$, and $W = 4$. Find $I$.


  \item What is the value of $B$?


  \item What is the MFLOPS rating of the system with the attached processor
    board?


  \item Your colleague wants to purchase the attached processor board even
    though the MIPS rating for the configuration using the board is less than
    that of the workstation alone. Is your colleague's evaluation correct?
    Defend your answer.


  \end{enumerate}


\item[1.15] One problem cited with MFLOPS as a measure is that not all FLOPS
  are created equal. To overcome this problem, normalized or weighted MFLOPS
  measures were developed. Table~\ref{tab:1.15a} shows how the authors of the
  ``Livermore Loops'' benchmark calculate the number of normalized
  floating-point operations per program according to the operations actually
  found in the source code. Thus, the \emph{native MFLOPS} rating is not the
  same as the \emph{normalized MFLOPS} rating reported in the supercomputer
  literature, which has come as a surprise to a few computer designers.

  \begin{table}[t]
    \centering
    \begin{tabular}{lc}
      \hline
      \emph{Real FP operations} & \emph{Normalized FP operations} \\
      \hline
      Add, Subtract, Compare, Multiply & 1 \\
      Divide, Square root & 4 \\
      Functions (Expo, Sin,...) & 8 \\
      \hline
    \end{tabular}
    \caption{\textbf{Real versus normalized floating-point operations.} The
    number of normalized floating-point operations per real operation in a
    program used by the authors of the Livermore FORTRAN Kernels, or
    ``Livermore Loops'', to calculate MFLOPS. A kernel with one Add, one
    Divide, and one Sin would be credited with 13 normalized floating-point
    operations. Native MFLOPS won't give the results reported for other
    machines on that benchmark.}
    \label{tab:1.15a}
  \end{table}

  Let's examine the effects of this weighted MFLOPS measure. The spice program
  runs on the DECstation 3100 in 94 seconds. The number of floating-point
  operations executed in that program are listed in Table~\ref{tab:1.15b}.

  \begin{table}[t]
    \centering
    \begin{tabular}{lr}
      \hline
      \emph{Floating-point operation} & \emph{Times executed} \\
      \hline
      \texttt{addD} & 25,999,440 \\
      \texttt{subD} & 18,266,439 \\
      \texttt{mulD} & 33,880,810 \\
      \texttt{divD} & 15,682,333 \\
      \texttt{compareD} & 9,745,930 \\
      \texttt{negD} & 2,617,846 \\
      \texttt{absD} & 2,195,930 \\
      \texttt{convertD} & 1,581,450 \\
      \hline
      \emph{Total} & 109,970,178 \\
      \hline
    \end{tabular}
    \caption{\textbf{Floating-point operations in spice.}}
    \label{tab:1.15b}
  \end{table}

  \begin{enumerate}

  \item What is the native MFLOPS for spice on a DECstation 3100?


  \item Using the conversions in Table~\ref{tab:1.15a}, what is the normalized
    MFLOPS?


  \end{enumerate}

% -----------------------------------------------------------------------------

\item[2.1] We are designing instruction set formats for a load-store
  architecture and are trying to decide whether it is worthwhile to have
  multiple offset lengths for branches and memory references. We have decided
  that both branch and memory references can have only 0-, 8-, and 16-bit
  offsets. The length of an instruction would be equal to 16 bits + offset
  length in bits. ALU instructions will be 16 bits. Figure 2.42 contains the
  data in cumulative form. Assume an additional bit is needed for the sign on
  the offset. For instruction set frequencies, use the data for MIPS from the
  average of the five benchmarks for the load-store computer in
  Table~\ref{tab:2.1}. Assume that the miscellaneous instructions are all ALU
  instructions that use only registers.

  \begin{table}[t]
    \centering
    \begin{tabular}{lcc}
      \hline
      \emph{Offset bits} & \emph{Cumulative data references} & \emph{Cumulative
      branches} \\
      \hline
      0  & 30\%  & 0\%   \\
      1  & 34\%  & 3\%   \\
      2  & 35\%  & 11\%  \\
      3  & 40\%  & 23\%  \\
      4  & 47\%  & 37\%  \\
      5  & 54\%  & 57\%  \\
      6  & 60\%  & 72\%  \\
      7  & 67\%  & 85\%  \\
      8  & 72\%  & 91\%  \\
      9  & 73\%  & 93\%  \\
      10 & 74\%  & 95\%  \\
      11 & 75\%  & 96\%  \\
      12 & 77\%  & 97\%  \\
      13 & 88\%  & 98\%  \\
      14 & 92\%  & 99\%  \\
      15 & 100\% & 100\% \\
      \hline
    \end{tabular}
    \caption{The second and third columns contain the cumulative percentage of
    the data references and branches, respectively, that can be accommodated
    with the corresponding number of bits of magnitude in the displacement.
    These are the average distances of all programs in Figure 2.8.}
    \label{tab:2.1}
  \end{table}

  \begin{enumerate}

  \item Suppose offsets were permitted to be 0, 8, or 16 bits in length,
    including the sign bit. What is the average length of an executed
    instruction?


  \item Suppose we wanted a fixed-length instruction and we chose a 24-bit
    instruction length (for everything, including ALU instructions). For every
    offset of longer than 8 bits, an additional instruction is required.
    Determine the number of instruction bytes fetched in this computer with
    fixed instruction size versus those fetched with a byte-variable-sized
    instruction as defined in part (a).



  \item Now suppose we use a fixed offset length of 16 bits so that no
    additional instruction is ever required. How many instruction bytes would
    be required? Compare this result to your answer to part (b), which used
    8-bit fixed offsets that used additional instruction words when larger
    offsets were required.


  \end{enumerate}

\item[2.2] Several researchers have suggested that adding a register-memory
  addressing mode to a load-store computer might be useful. The idea is to
  replace sequences of

\begin{verbatim}
LOAD R1,0(Rb)
ADD R2,R2,R1
\end{verbatim}

  by

\begin{verbatim}
ADD R2,0(Rb)
\end{verbatim}

  Assume the new instruction will cause the clock cycle to increase by 10\%.
  Use the instruction frequencies for the gcc benchmark on the load-store
  computer from Figure 2.32. The new instruction affects only the clock cycle
  and not the CPI.

  \begin{enumerate}

  \item What percentage of the loads must be eliminated for the computer with
    the new instruction to have at least the same performance?


  \item Show a situation in a multiple instruction sequence where a load of
    \texttt{R1} followed immediately by a use of \texttt{R1} (with some type of
    opcode) could not be replaced by a single instruction of the form proposed,
    assuming that the same opcode exists.


  \end{enumerate}


\item[2.4] What are the \emph{economic} arguments (i.e., more computers sold)
  for and against changing instruction set architecture in desktop and server
  markets? What about embedded markets?



\item[2.11] Compute the effective CPI for MIPS using Figure 2.32. Suppose we
  have made the following measurements of average CPI for instructions:

  {\centering
  \begin{tabular}{lc}
    \hline
    \emph{Instruction} & \emph{Clock cycles} \\
    \hline
    All ALU instructions & 1.0 \\
    Loads-stores & 1.4 \\
    Conditional branches \\
    \qquad Taken & 2.0 \\
    \qquad Not taken & 1.5 \\
    Jumps & 1.2 \\
    \hline
  \end{tabular}
  \par}

  Assume that 60\% of the conditional branches are taken and that all
  instructions in the miscellaneous category of Figure 2.32 are ALU
  instructions. Average the instruction frequencies of gcc and espresso to
  obtain the instruction mix.


% -----------------------------------------------------------------------------

\item[3.1] Use the following code fragment:

\begin{verbatim}
loop:   LW      R1,0(R2)
        ADDI    R1,R1,#1
        SW      0(R2),R1
        ADDI    R2,R2,#4
        SUB     R4,R3,R2
        BNEZ    R4,Loop
\end{verbatim}

  Assume that the initial value of \texttt{R3} is \texttt{R2} + 396.

  Throughout this Exercise use DLX integer pipeline and assume all memory
  accesses are cache hits.

  \begin{enumerate}

  \item Show the timing of this instruction sequence for the DLX pipeline
    \emph{without} any forwarding or bypassing hardware but assuming a register
    read and a write in the same clock cycle ``forwards'' through the register
    file, as in Figure~3.10. Use a pipeline timing chart like Figure~3.14
    or~3.15. Assume that the branch is handled by flushing the pipeline. If all
    memory references hit in the cache, how many cycles does this loop take to
    execute?


  \item Show the timing of this instruction sequence for the DLX pipeline with
    normal forwarding and bypassing hardware. Use a pipeline timing chart like
    Figure~3.14 or~3.15. Assume that the branch is handles by predicting it as
    not taken. If all memory references hit the cache, how many cycles does
    this loop take to execute?


  \item Assuming the DLX pipeline with a single-cycle delayed branch and normal
    forwarding and bypassing hardware, schedule the instructions in the loop
    including the branch delay slot. You may reorder instructions and modify
    the individual instruction operands, but do not undertake other loop
    transformations and modify the number or opcode of the instructions in the
    loop (that's for the next chapter!). Show a pipeline timing diagram and
    compute the number of cycles needed to execute the entire loop.


  \end{enumerate}


\item[3.4] Consider the example on page 137 that compares the unpipelined and
  pipelined machine. Assume that 1 ns overhead is fixed and that each pipeline
  stage is balanced and takes 10 ns in the five stage pipeline. Plot the
  speedup of the pipelined machine versus the unpipelined machine as the number
  of pipeline stages is increades from five stages to 20 stages, considering
  only the impact of the pipelining overhead and assuming that the work can be
  evenly divided as stages are increased (which is not generally true). Also
  plot the ``perfect'' speedup that would be obtained of there was no overhead.


\item[3.5] A machine is called ``underpipelined'' if additional levels of
  pipelining can be added without changing the pipeline-stall behavor
  appreciably. Suppose that the DLX integer pipeline was changed to four stages
  by merging EX and MEM and lengthening the clock cycle by 50\%. How much
  faster would the conventional DLX pipeline be versus the unpipelined DLX on
  integer code only? Make sure you include the effect of any change in pipeline
  stalls using the data for gcc in Figure~3.38.

\end{enumerate}


\end{document}
