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, R1 is set to the base address of array X and R2 is set to the base address of Y:

Assume the functional unit latencies as shown in the following table. Assume a one-cycle delayed branch that resolves in the ID stage. 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 for both floating-point operation and branch delays, including any stalls or idle clock cycles. What is the execution time (in cycles) per element of the result vector, Y, unscheduled and scheduled? How much faster must the clock be for processor hardware alone to match the performance improvement achieved by the scheduling compiler? (Neglect any possible effects of increased clock speed on memory system performance.)

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. How many times must the loop be unrolled? Show the instruction schedule.
What is the execution time per element of the result?

c. Assume a VLIW processor with instructions that contain five operations, as shown in Figure 3.20. We will compare two degrees of loop unrolling. First, unroll the loop 6 times to extract ILP and schedule it without any stalls (i.e., completely empty issue cycles), collapsing the loop overhead instructions, and then repeat the process but unroll the loop 10 times. Ignore the branch delay slot. Show the two schedules. What is the execution time per element of the result vector for each schedule? What percent of the operation slots are used in each schedule? How much does the size of the code differ between the two schedules? What is the total register demand for the two schedules?

Figure 3.20

Transcribed Image Text:

addi x4, x1, #800 ; x1 = upper bound for X foo: fld F2,0 (x1) F4, F2, FO ; (F2) = X(i) ; (F4) = a*X(i) ; (F6)=Y (1) F6,0 (x2) F6, F4, F6 F6,0 (x2) ; (F6) = a*X(1) + y(i) ; Y(i) = a*X(i) + Y (1) ; increment X index x1,x1, #8 x2,x2, #8 x3, x1, x4 x3, foo fmul.d fld fadd.d fsd addi addi sltu bnez increment Y index ; test: continue loop? ; loop if needed