Assignment 12, due April 23

Always, on every assignment, please write your name legibly as it appears on your University ID and on the class list! All assignments will be due on Fridays at the start of class, and unless there is what insurance companies call "an act of God", the only exceptions to this rule will be by advance arrangement.

1. There are two ways to execute a skip in a pipelined machine. The notes suggest invalidating the instruction in the previous pipeline stage, but this can get complicated if there are bubbles in the pipe. Another way to do it is to have the pipeline stage that executes the skip set a flipflop that reminds it to invalidate the next instruction to arrive in this stage. Work out the logic for doing this.

   a) Work it out assuming there are no bubbles or other events that might invalidate instructions.

   b) What problems do bubbles and stalls cause with your solution.

   c) What problems do branches cause with your solution.

2. The exercise in lecture 24 in pipelining at the program level assumed that multiplication and addition take the same amount of time, and that each is completed in one clock cycle. Assume that ALUa, the one that is used for multiplication, is slower, so that the aDST field of each instruction always shows where to store the result computed by the previous instruction, not the result computed using aS1, aS2 and aOP from this instruction. Redo the exercise of reducing this code to machine code under these conditions:

           t = 0
           for i = 1 to 10 do t = t + a[i]*b[i]
   

   As in the notes, begin with non-optimal code that follows the logic of the original program, then optimize.

3. Work out a calling sequence for use in the example architecture from the midterm exam that is suitable for use with a recursive function. For the sake of example, focus on this function:

           int fib(int i)
   	{
   		if (i < 2) return i;
   		return fib(i - 1) + fib(i - 2);
   	}
   

   Do not code this function! The assignment is to create a calling sequence, receiving sequence and return sequence appropriate for this function.