\documentstyle[twocolumn]{article}

\setlength{\oddsidemargin}{0in}
\setlength{\evensidemargin}{0in}
\setlength{\topmargin}{-0.3in}
\setlength{\headheight}{0in}
\setlength{\headsep}{0in}
\setlength{\textwidth}{6.5in}
\setlength{\textheight}{9.8in}
\setlength{\parindent}{0in}
\setlength{\parskip}{0.1in}
\setlength{\columnseprule}{0.4pt}

\begin{document}

\bf
\hfill Name:  $\underline{ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \
\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ }$
% \_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_
\rm
\bigskip
                                      
{\bf Directions:} Work on this sheet (both sides, if needed) only;
{\bf do not turn in any supplementary sheets of paper}.  
In order to get full credit, {\bf SHOW YOUR WORK.}

{\bf 1.} (10) Suppose we have a real microengine with the design of Mic-1,
and that instead of burning the microcode into ROM, we load it into RAM
from disk whenever we power up the machine.  If the file names followed
the patterns in the DePaul package, what would be the file-name suffix
(.def, .asm, etc.) of the file from which the microcode will be loaded?

{\bf 2.}  Here is most of the listing of the file ist/one/ten.asm: 

\begin{verbatim}
ten     equ    4000        
        loco   10
        stod   ten         
        loco   1
        stod   one         
        loco   0           
        stod   index       
loop    lodd   index
        addd   one         
        stod   index
        subd   ten         
        jneg   loop        
\end{verbatim}

\begin{itemize}

\item [(a)]  (10) What will be the Mac-1 machine code resulting from
the assembly of the {\bf loco 10} instruction?  Give your answer in
hex.

\item [(b)] (10) How many clock cycles will the instruction {\bf addd
one} take to execute (including fetch and decode)?  Count major cycles
only, not the four subcycles.

\end{itemize}

{\bf 3.}  (15) This problem concerns the microcode file three.mal in the
DePaul package.  We wish to do a partial instruction prefetch, i.e. do
part of the fetch of the next instruction while executing the current
instruction.  Give an example of a target-architecture instruction whose
microcode can be modified so that we save one cycle of the fetch of the
next instruction, but for which a two-cycle savings is impossible.  Show
how to change the microcode for that instruction (just show the lines
which change).

{\bf 4.}  (10) In the feedback-pipe example whose forbidden list is

\begin{verbatim}
{2,3,6}
\end{verbatim}

suppose we start Widget I at time 34 and start Widget II at time
38 (not 39).  List all times at which we CANNOT start Widget III. 

{\bf 5.}  (10) Suppose we have two reservation tables, A and B.  They are
identical except that B has an extra row on the bottom that
A does not have.  Let $MAL_A$ and $MAL_B$ be the minimum average
latencies for the two pipes.  Then which of the following statements
is guaranteed to hold?  (i) $MAL_A \leq MAL_B$; (ii) $MAL_B \leq MAL_A$;
(iii) neither of the two MAL values is guaranteed to be less than or
equal to the other. 

{\bf 6.}  (10) Fill in the blank:  The analog of the ``Write data'' line in
Fig. 5.6 in Patterson and Hennessy in Mic-1 is
\_\_\_\_\_\_\_\_\_\_\_\_\_.

{\bf 7.}  (10) Fill in the blank:  Say we have a MIPS instruction 

\begin{verbatim}
beq $s3,$s4,T
\end{verbatim}

Then in Fig. 5.21 in Patterson and Hennessy the value of the memory
address T (i.e. the actual address we jump to) is on the line between
\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_ and
\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_.  (Just describe
the two places in English, with enough detail so that I know exactly
what spot in the figure you are referring.)

{\bf 8.}  (15) Implement a MUL3 instruction for Mac-1, which will perform the
operation  

\begin{verbatim}
ac:=ac*3
\end{verbatim}

Assume that it will replace the DESP instruction, i.e. it will use the
op code 1111111000000000, and thus its microcode will begin at location
77.  Just show the microassembly language code for execution of this
new instruction, not the code for its fetch or decode.

\bigskip

{\bf Solutions:}

1.  .mic.

2.a.  0x700a.
2.b.  9 (microinstructions 0, 1, 2, 3, 4, 11, 12, 13, 14).

3.  For example, change the microinstruction in location 7 to

\begin{verbatim}
ac := mbr; mar := pc; rd; goto 1;
\end{verbatim}

4.  Look at the state diagram on p.12.  At the time we were deciding
when to schedule Widget II, we were in state (0,1,1,0,0,1).  We then
chose to start Widget II 4 time units (38-34=4) after Widget I,
so we follow the arrow labeled `4', which brings up back to state
(0,1,1,0,0,1).  In other words, at the time we are deciding when to
start Widget III (time 38), we are in state (0,1,1,0,0,1).  In that
state, the 0s say we cannot start Widget III 2, 3 or 6 units of time
after Widget II, i.e. at times 40, 41 or 44.

5.  The forbidden list for B will be a superset of that of A, i.e.
everything in A's list is also in B's.  The two lists could either
be identical, or B's list could have everything in A's list and more.
Now, suppose we start Widget I in both pipes at, say, absolute time 500.  
Then the fact that B's forbidden list is a superset of A's implies that    
any possible sequence of widget-start times for B is also allowable for
A (though not necessarily vice versa).  In other words, we can do at
least as well with A as with B, so the correct answer is (i).

6.  It is the c bus.

7.  Between the ALU and MUX which are near the upper-right corner.

8.  For example:

\begin{verbatim}
    77: a := ac;
    78: a := lshift(a);
    79: ac := ac + a; goto 0;
\end{verbatim}
 
\end{document}