For this exam, you may use your textbook, the Internet, your notes and assignments, your brain, and divine guidance if available. You may not use other people. If you get stuck, talk to Jeff Ondich, but please don't talk to anyone else about the exam.

1. (12 points) Complete the following PDP8/E subroutine. Try to minimize the number of instructions executed by the subroutine.

    / Preconditions: The auto-increment location labeled ADDR contains
   / 	the address of the first element of an array of 12-bit words.
   /	The AC contains the number of words in the array.
   /
   / Postconditions: The AC contains the largest item
   /	in the array.  Note that all positive numbers are larger
   /   than all negative numbers.
   
   MAXARRAY,   0000
               ...
               JMP I MAXARRAY
   

   Briefly describe what, if anything, you would do differently if your goal was to minimize the amount of memory taken up by the the subroutine.

   Watch out: is it true that A > B if and only if A - B > 0?

2. (10 points) Give an example of each of the following situations. If your textbook contains such examples (in the main text or in the problems), you may refer to those examples. You may also just cook up examples of your own. (Note that the "performance" referred to in these situations is a technical term--it's the reciprocal of execution time.)

   • Machine M1 has a higher MIPS rating than machine M2, but M2's performance is better than M1's.
   • Machine M1 has a lower CPI than machine M2, but M2's performance is better than M1's.
   • Machine M1 has a higher clock rate than machine M2, but M2's performance is better than M1's.

   Is it possible for machine M1 to have higher MIPS rating, higher clock rate, and lower CPI than M2, but still have worse performance?

3. (12 points) The table below shows the execution times for all of the PDP8/E instructions (not including op-code 6).

   
   Execution times in micro-seconds for PDP8/E instructions
   --------------------------------------------------------
                            Addressing mode     
                 ------------------------------------------
   Instruction                            Indirect with
      Type       Direct      Indirect     auto-increment
   --------------------------------------------------------
   AND            2.6          3.8             4.0
   TAD            2.6          3.8             4.0
   ISZ            2.6          3.8             4.0
   DCA            2.6          3.8             4.0
   JMS            2.6          3.8             4.0
   JMP            1.2          2.4             2.6
   
   Opcode 7          1.2 (addressing mode irrelevant)
   --------------------------------------------------------
   

   Assume the following:

   • Of the instructions executed during the run of a typical PDP8/E program, 50% are op-code 7, 35% are direct memory references other than JMP, 10% are indirect memory references other than JMP, 1% are direct JMPs, 1% are indirect JMPs, 3% are indirect memory references (other than JMP) using auto-increment, and 0% are indirect JMP with auto-increment.
   • There exists a relatively modern machine (RMM) whose clock rate is 900MHz.
   • The CPI for a typical program run on the RMM is 2.
   • For programs that perform the same tasks, the instruction counts for the PDP8/E and the RMM are approximately the same.

   Answer the following questions:

   • What is the MIPS rating for the PDP8/E?
   • What is the MIPS rating for the RMM?
   • By what factor is the RMM faster than the PDP8/E?
   • Which of the assumptions in the list above is the most unreasonable? If you adjust that assumption to make it more reasonable, the RMM will still be a lot faster than the PDP8/E. But will the RMM appear even faster as a result of the changed assumption, or a bit slower, compared to the PDP8/E?

4. (12 points) The diagram below (Digital and Microprocessor Electronics for Scientific Application, Dennis Barnaal, Waveland Press, 1989, page D100) shows a circuit known as a JK flip-flop. The weird black triangle in the middle is a diode--you don't need to worry about it.

   • Suppose J, K, and Clock are all set to 0. What combinations of values are possible for Q, NOT Q, Q*, and NOT Q*?
   • Suppose J = K = Clock = Q = 0. Now set J = 1 and K = 0. Next, let Clock go up to 1 and then back down to 0. Draw a timing diagram showing the changes that take place in Clock, S*, Q*, and Q.
   • Based on your timing diagram, what happens to Q on a falling clock edge if J = 1 and K = 0?
   • What happens to Q on a falling clock edge if J = 0 and K = 1?
   (You could use an explanation based on symmetry.)
   • What happens to Q on a falling clock edge if J = K = 1? A timing diagram or two might be useful here.
   

5. (4 points) Who are Gordon Moore and Maurice Wilkes, and why are they important in the history of computer architecture?

6. (2 points) Direct me, if you wish, to a web site that you find amusing.

7. (12 points) Read sections A.1 through A.4 of your textbook.
   • Give a concrete example of C code that gives an "undefined reference" error from the linker used by g++ (the linker is called "ld", by the way, and will show up in the error message).
   • Under what very common conditions might the linker discover an external label in one object file that is not used to resolve a reference in any other object file of the program? What would be the most helpful action the linker could take in such a situation?
   • Consider the UNIX object file format shown on page A-13. Use g++ -c yourprogram.cpp to generate an object file yourprogram.o. Now use the UNIX command od ("octal dump") to examine yourprogram.o. List three pieces of evidence that Patterson & Hennessy are telling the truth about UNIX object files.