1. [15] 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 ) and is the central operation in Gaussian elimination. The following code implements the DAXPY operation, Y=aX+ Y. Initially, F4 holds constant a, R1 is set to the base address of array X, and R2 is set to the base address of array Y: load X(i) to Reg(F6) Reg(F2)=a*X(i) Reg(F8)=Y(i) foo: LD MULD F6, 0(R1) F2, F6, F4 L.D F8,0(R2) ADD.D F8, F2, F8 S. D F8,0(R2) store Reg(F8) to Y(i) DADDIU R1, R1, # 8 increase X index Reg(F8)=a*X(i)+Y(i) DADDIU R2, R2, #8 increase Y index DSLTU BNEZ R5, R1, R3 R5, foo test: continue loop? loop if needed The table below shows the number of intervening clock cycles needed to avoid a stall. Assume that results are fully bypassed. Instruction producing result Instruction using result Latency in clock cycles FP multiply FP store 5 FP ALU op FP store 2 FP multiply FP ALU op 6 FP ALU op FP ALU op 3 Load Store 0 Load Other than store 1 Integer ALU op Branch 1 0 Integer ALU op Integer ALU op a. [10] 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. [5] 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? You can assume that the number of iterations is always a multiple of the unrolled loop body. Answer: a. Clock cycle 1 2 Unscheduled code L.D F6, 0(R1) Scheduled code L.D F6, 0(R1) 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 Unscheduled: ? cycles per element Scheduled: ? cycles per element b. The code must be unrolled? times to eliminate stalls after scheduling. Clock cycle 1 Unrolled and scheduled code L.D F6,0(R1) 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 1. [15] 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 ) and is the central operation in Gaussian elimination. The following code implements the DAXPY operation, Y=aX+ Y. Initially, F4 holds constant a, R1 is set to the base address of array X, and R2 is set to the base address of array Y: load X(i) to Reg(F6) Reg(F2)=a*X(i) Reg(F8)=Y(i) foo: LD MULD F6, 0(R1) F2, F6, F4 L.D F8,0(R2) ADD.D F8, F2, F8 S. D F8,0(R2) store Reg(F8) to Y(i) DADDIU R1, R1, # 8 increase X index Reg(F8)=a*X(i)+Y(i) DADDIU R2, R2, #8 increase Y index DSLTU BNEZ R5, R1, R3 R5, foo test: continue loop? loop if needed The table below shows the number of intervening clock cycles needed to avoid a stall. Assume that results are fully bypassed. Instruction producing result Instruction using result Latency in clock cycles FP multiply FP store 5 FP ALU op FP store 2 FP multiply FP ALU op 6 FP ALU op FP ALU op 3 Load Store 0 Load Other than store 1 Integer ALU op Branch 1 0 Integer ALU op Integer ALU op a. [10] 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. [5] 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? You can assume that the number of iterations is always a multiple of the unrolled loop body. Answer: a. Clock cycle 1 2 Unscheduled code L.D F6, 0(R1) Scheduled code L.D F6, 0(R1) 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 Unscheduled: ? cycles per element Scheduled: ? cycles per element b. The code must be unrolled? times to eliminate stalls after scheduling. Clock cycle 1 Unrolled and scheduled code L.D F6,0(R1) 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30