CSE 378 Midterm

Ben Dugan, Winter 2001 


2/8/01                                   Name: _________________________

Instructions:

This test has 5 questions, totaling 50 points.

The test is closed book, closed notes, closed calculator, open mind, etc. In general, we are insensitive to small syntactic errors, unless we think they are symptomatic of a a significant misunderstanding of the material, so don't be panicked over details of that sort. Remember, don't spend all your time on one question. You should budget roughly one minute per point.

Question Possible Score
1 10
2 10
3 3
4 10
5 17
Total 50

Question 1. (10 points)

Suppose you are a manager of a project to build a new processor. You must ship the processor in 3 months. On benchmarks running on a prototype, you have observed the following instruction mix and CPIs:

ClassFrequencyCPI
Stores 10% 5
Loads 20% 7
Branches 20% 3
ALU operations 50% 4

1. What is the average CPI of your machine?
2. Which class of instructions contributes the most to the average CPI?
3. The hardware team tells you they can either reduce the CPI of loads to 4 cycles, or reduce the CPI of ALU operations to 3 cycles. You don't have time to make both improvements, which do you choose? Why?
4. Someone suggests a last-minute modification to the ISA. By adding some new instructions to the ISA, the instruction count for the benchmark programs will drop by 10%. However, implementing the new instructions will mean that the CPI of ALU operations and stores will increase by 1 cycle each. The modification will impact neither cycle time nor the instruction mix shown above. Should you make the modification? Why or why not? (In your calculations, compare against the original machine. Not the modified machine from part 3, above.)

Question 2. (10 points)

True/False questions. 1 point for each correct answer.
  1. TRUE / FALSE In the MIPS procedure call convention, leaf procedures (those that don't call any other procedures) often don't have to save any registers.
  2. TRUE / FALSE The disadvantage of the single-cycle implementation we studied in class is that the CPI is too low.
  3. TRUE / FALSE All MIPS instructions are 4 bytes long.
  4. TRUE / FALSE The VAX implementation is complicated by the many addressing modes provided by the the ISA.
  5. TRUE / FALSE In the BEQ instruction, a branch target may not be further than 2^15 bytes away.
  6. TRUE / FALSE The multi-cycle implementation minimizes both instruction count and cycle time.
  7. TRUE / FALSE A program compiled for a CISC machine will typically have a smaller executable than the same program compiled for a RISC machine.
  8. TRUE / FALSE Compilers for the MIPS will typically place long-lived values into caller-saved registers ($T0-$T9) in order to minimize loads and stores to/from the stack.
  9. TRUE / FALSE Pipelining improves both instruction throughput and latency compared to the multi-cycle implementation.
  10. TRUE / FALSE The cycle time of a pipelined machine is determined by the maximum time required to complete a single stage of the pipeline.

Question 3. (3 points)

What is the effect of the following sequence of MIPS instructions on the contents of register $T0? 
        LI      $t0, 0xF000F00F
        SRL     $t1, $t0, 31
        SLL     $t0, $t0, 1
        OR      $t0, $t0, $t1

Question 4. (10 points)

1. The single-cycle datapath we studied in class does not implement the JR instruction. Show or describe the changes you would make to the datapath to implement this instruction. The instruction 
    JR   $RA
would be encoded as follows (all numbers in decimal):

Opcodersrtrdshamtfunc
0310008

Please see the diagram of the single-cycle implementation on the following page. You may make your changes directly to the diagram, if you wish.
2. Fill in the table of control signals below for the JR instruction. If you needed to add a new control line, use the provided empty column for it, and show us the appropriate values (for all of the listed instructions). Use don't-cares where appropriate.

InstructionRegDstALUSrcMemTo
Reg		Reg
Write 		Mem
Read 		Mem
Write		Branch           
R-format1001000
lw0111100
swX1X0010
beqX0X0001
jr







3. Is the above modification likely to impact the cycle time of the single-cycle implementation? Why or why not?

Question 5. (17 points)

Below is a simple C++ function for computing grades. Write the MIPS assembly program that implements this function. Your procedure call convention should follow the basic guidelines presented in class. You should only feel obliged to write comments if you are doing something really strange. To perform input, you must use the provided function readInt, not the MIPS syscall. 
// readInt() is a function defined elsewhere.
int readInt();

// Args:    The number of students in the course.
// Reads the specified number of scores and inserts each score into
// the provided array.
// Returns: The average score.  Modifies the array.

int grades(int A[], int students) {
  int sum = 0;
  for (int i=0; i < students; i++) {
    int score = readInt();
    A[i] = score;
    sum = sum + score;
  }
  int average = sum / students;
  return average;
}