For this exam, you may use your textbook, your notes and assignments, your brain, and divine guidance if available. You may use an introductory CS text if you don't remember what selection sort is. You may not use other books, other people, or Internet resources. If you get stuck, talk to Jeff Ondich, but please don't talk to anyone else about the exam.

Submit your answers on paper. For the PDP8 code in problem 1, submit your .pal file using HSP

1. (15 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)
   --------------------------------------------------------
   

   • Write a PDP8 program that starts at address 0200 and sorts the contents of page 2 (0400-0577) using selection sort.
     
     
   • Think of each execution time in the table above (1.2, 2.4, 2.6, 3.8, and 4.0) as defining an instruction class. So, for example, Class A consists of direct JMPs and all opcode 7 instructions, Class B of all indirect JMP instructions, etc. When you run your sorting program, how many instructions in each class get executed? (Please show mercy on me by explaining clearly how you came up with the answer to this question.)
     
     
   • If you use your sorting program as a benchmark, what is the native MIPS rating of the PDP8/E?
     
     
   • What is the peak MIPS rating of the PDP8/E? Why is it uninteresting?
     
     
   • Based on what Patterson and Hennessy say about the MIPS ratings, approximately how much faster than the PDP8/E are current desktop machines? Is comparing MIPS ratings a fair comparison for this purpose?
   
   
   
2. (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.
   
   
   
3. (15 points) Find out and report as much as you can about the function calling mechanism and the structure of stack frames as they are created by the g++ compiler on our Silicon Graphics computers.

   To do this, log in to green.mathcs.carleton.edu, blue.mathcs.carleton.edu, or cyan.mathcs.carleton.edu, either via telnet or by sitting at the machine in CMC307. Then, write small C++ programs and compile them with the -S flag (for example, "g++ -S program.cpp" will create the MIPS assembly language file called "program.s"). By examining the MIPS versions of your programs, you should be able to discover how g++ organizes its function calls and stack frames for MIPS.

   Some questions you should try to answer are:
   
   

   • Does the stack grow towards larger addresses or towards smaller addresses?
   • Where (if anywhere) in the stack frame does the return address go?
   • Where do parameters go, and in what order?
   • Where does a function's return value get put? Does it matter whether the return value takes up a lot of memory (for example, if the return type is a struct of some kind)?
   • Where do local variables go, and in what order?
   • Which has the responsibility for tearing down the stack frame--the caller or the function?
   
   
   
4. (2 points) What book should I read next?
   
   
5. (10 points) Consider the fictional machine Mbase from problem 18 on pages 93-94 of P&H. The compiler team from problem 21 has gone on vacation, and the iterim compiler team has cooked up yet another compiler. The new compiler generates code with 90% as many instructions of each class as the base compiler, and then replaces every class D instruction by two class A instructions. Call the machine with the new compiler Mnew.
   
   
   • What is the CPI for Mnew?
   • How much faster is Mnew than Mbase?
   • The head of the design project reads the Mnew report, and immediately starts firing people. Who, and why?