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 amount of memory consumed by the subroutine.

   
   / Preconditions: The page-0 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 sum of the elements
   /	in the array.  This subroutine does *not* correct for
   /	overflow.
   ADDARRAY,	0000
   			...
   			JMP I ADDARRAY
   

   Briefly describe what you would do differently if your goal was to minimize the number of instructions executed by the subroutine.
   
   

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 800MHz.
   • 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. (4 points) Who are Federico Faggin and Ted Hoff, and why are they important in the history of computer architecture?
   
   
5. (2 points) My daughter Elena is going to turn 7 next week, and we'd like to give her a computer game for her birthday. Any suggestions?
   
   
6. (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.
   
   
   
7. (7 points) Write an algebraic expression describing the following boolean function of three variables. Then simplify the expression as much as you can, and draw a digital logic circuit that implements the function based on your simplified formula.

   
   	  A     B     C   ||  f(A,B,C)
   	===============================
   	  0     0     0   ||     0 
   	  0     0     1   ||     1 
   	  0     1     0   ||     1 
   	  0     1     1   ||     1 
   	  1     0     0   ||     0 
   	  1     0     1   ||     1 
   	  1     1     0   ||     0 
   	  1     1     1   ||     0