CS 207
Midterm 1
Ondich
Due 11:10 AM Monday, October 25, 1999
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
- (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?
- (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.
- (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?
- (2 points) What book should I read next?
- (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?