CS 61C (Fall 2007)

Homework Assignment 10

Two exercises.  Due 2:45pm before lecture 11/14/2007.


Goals

This assignment is intended to give you more practice with aspects of the MIPS pipeline.

Submission instructions

Submit a file named "hw10.txt" as hw10.

Exercise 1 (4 points)

Consider the following function, which when given as arguments a pointer to the start of an integer array values and an integer n, returns the sum of the first n elements of values.

# $a0 contains array address, $a1 contains # elements
firstNsum:
	move $t0,$a0  # current element address
	move $t1,$0   # current element index
	move $v0,$0   # sum
loop:
	beq  $t1,$a1,gotsum
	lw   $t2,0($t0) # get element
	add  $v0,$v0,$t2
	addi $t0,$t0,4
	addi $t1,$t1,1
	j loop
gotsum:
	jr $ra
  1. Assume that there is no forwarding, and branch and load delays are required as described in Patterson and Hennessy section 6.1. (Branches are resolved in stage 2.) Indicate clearly in the code above where to add nop instructions to remove all data and control hazards in the function. Provide only as many nops as are necessary to avoid hazards. You should strongly consider creating simple ASCII tables/diagrams which show the timing of these instructions with one clock cycle per column.
  2. Indicate which of the nop instructions you added become unnecessary with the addition of forwarding circuitry from the ALU output and the memory unit to the ALU inputs.
  3. Rewrite the loop so that each iteration takes only five clock cycles once the pipeline is full. Assume that forwarding, branch, and load delays are as described in Patterson and Hennessy section 6.1, with branches resolved in stage 2.

Exercise 2 (4 points)

The following two instructions are being proposed for addition to the MIPS hardware instruction set.

For each of the two instructions, provide the following information.

  1. Indicate whether the instruction can be implemented in a way that is consistent with the existing five-stage pipeline, but that doesn't add any extra functional units such as another ALU or memory port. (Extra control signals, wires, and multiplexors are OK.)

  2. If your answer to part a is "yes, it can", list what happens in stages 3, 4, and 5 when processing the instruction. If your answer to part a is "no, it can't", explain why.