In this exercise, we look at how software techniques can extract instruction-level parallelism (ILP) in a common vector loop. The following loop is the so-called DAXPY loop (double-precision aX plus Y) and is the central operation in Gaussian elimination. The following code implements the DAXPY operation, Y = aX + Y, for a vector length 100. Initially, F0 holds constant a, R1 is set to the base address of array X, and R2 is set to the base address of array Y:

DADDIU R4, R1, #800 ; R4 = upper bound for X foo: L.D F2, 0(R1) ; load X(i) to F2 MUL.D F4, F2, F0 ; (F4) = a*X(i) L.D F6, 0(R2) ; (F6) = Y(i) ADD.D F6, F4, F6 ; (F6) = a*X(i) + Y(i) S.D F6, 0(R2) ; store F6 to Y(i) DADDIU R1, R1, #8 ; increase X index DADDIU R2, R2, #8 ; increase Y index DSLTU R3, R1, R4 ; test: continue loop? BNEZ R3, foo ; loop if needed

The table below shows the number of intervening clock cycles needed to avoid a stall. Assume that results are fully bypassed.

a. Assume a single-issue pipeline. Show how the loop would look both unscheduled by the compiler and after compiler scheduling, including any stalls or idle clock cycles. What is the execution time (in cycles) per element of the result vector Y, unscheduled and scheduled?

b. Assume a single-issue pipeline. Unroll the loop as many times as necessary to schedule it without any stalls, collapsing the loop overhead instructions. Show the instruction schedule. What is the execution time per element of the result?

Instruction producing Instruction using result Latency in clock cycles result FP multiply FP ALU op FP multiply FP ALU op Integer ALU op Integer ALU op FP ALU op FP ALU op FP store FP store Branch Integer ALU op Store Other than store Load