CPSC 330 - Fall 2007 Homework 5 Due by 5:00 on Monday, December 3 1. Draw the true data dependency diagram for instructions I1-I7 below. Destination registers are listed last. Assume the condition codes are set by each ALU operation (i.e., by "add" and "dec" operations, but not by "ld", "st", or "bne") loop: // in RTL: in pseudo-C code: I1: ld 0(R1), R2 // R2 <- memory[0+R1] I2: add R2, 1, R2 // R2 <- R2 + 1 I3: st R2, 0(R3) // memory[0+R3] <- R2 do { I4: add R1, 4, R1 // R1 <- R1 + 4 *y++ = (*x++) + 1; I5: add R3, 4, R3 // R3 <- R3 + 4 i--; I6: dec R4 // R4 <- R4 - 1 } while( i != 0 ); I7: bne loop // if cc shows that the // last ALU result was // not equal to 0, then // PC <- loop 2. Can the instruction I4 be moved above instruction I1 and the resulting code be executed with the same results in memory as the original code? Explain. 3. Redraw the data dependency diagram for instructions I1-I7 with added arcs for any situations where instructions cannot be swapped in execution order because registers must be read in one instruction before being written in another instruction. 4. Assume no forwarding is used in the five-stage pipeline and that instruction I1 is fetched in cycle 1. At what cycle count does the writeback of R4 occur for instruction I6. 5. Assume forwarding is used in the five-stage pipeline and provides immediate availability of values calculated by the ALU but a one-cycle load-use penalty. That is, a dependent instruction that immediately follows a load will be stalled for one cycle. In this case, if instruction I1 is fetched in cycle 1, at what cycle count does the writeback of R4 occur for instruction I6. XC-1. Is there a way in which the instructions above could be scheduled so that all dependencies are obeyed but there are no stall cycles? XC-2. Is scheduling the code made any easier by the approach used in the SPARC instruction set architecture where operations do not change the condition codes unless explicitly marked as doing so in the instruction format? (e.g., "sub" versus "subcc")