Part (a). In what pipeline stage are branches resolved? How many cycles would we have to stall after a branch, if branches are not predicted? (20 points)

Part (b). Label all dependences within one iteration of this code (not just the ones that will require forwarding). One iteration is defined as the instructions between the first add and the second bne, inclusive. (20 points)

int count(int *A, int val, int len) { int count = 0, *end = A + len; do { if (*A == val) { count += 1; } A += 1; // pointer arith } while (A != end) return count; }

The inner loop for the C code shown can be written as:

loop: add $a0, $a0, 4 lw $t0, -4($a0) bne $t0, $a1, skip add $v0, $v0, 1 skip: bne $a0, $t1, loop

Part (c). Consider the code in part (b). Using the pipeline shown on the previous page (assume branches are predicted not taken), determine in which cycle each instruction is in each pipeline stage using the grid below (stalls can be marked as --). Assume that both branches are always taken. (20 points)

1. (60 points) Pipelining: IDVEX RegisterDest IDIEX.MemRead ControlMux Control x 4 R1 R2 Registers Data Data RAM Data IF Flush Ext Forward Consider the data path shown above where only partial forwarding is implemented