Loop unrolling and SW pipelining

Consider a basic in-order pipeline with bypassing (one instruction in each pipeline stage in any cycle). The pipeline has been extended to handle FP add. Assume the following delays between dependent instructions:

Load feeding any instruction: 3 stall cycles FP ALU feeding any instruction (except stores): 5 stall cycles FP ALU feeding store: 4 stall cycles Int add feeding a branch: 2 stall cycles Int add feeding any other instruction: 1 stall cycle A conditional branch has 1 delay slot (an instruction is fetched in the cycle after the branch without knowing the outcome of the branch and is executed to completion)

Below is the source code and default assembly code for a loop.

Source Code:

for (i=1000 i>0 i--) {

w[i] = x[i] + w[i]

}

Assembly Code:

Loop: L.D F1, 0(R1) ; Get w[i]

L.D F2, 0(R2) ; Get x[i]

ADD.D F1, F2, F1 ; Add two numbers

S.D F1, 0(R1) ; Store the result into w[i]

DADDUI R1, R1, #-8 ; Decrement R1

DADDUI R2, R2, #-8 ; Decrement R2

BNE R1, R3, Loop ; Check if we've reached the end of the loop

NOP

(a) Show how the loop would look for unscheduled execution by the compiler(default schedule) (use a table to show the cycle at which an instruction is issued) for the default code. (b) How should the compiler order instructions to minimize stalls (without unrolling) (note that the execution of a NOP instruction is effectively a stall)? Show the schedule. How many cycles can you save per iteration, compared to the default schedule? (c) How many times must the loop be unrolled to eliminate stall cycles? Show the schedule for the unrolled code. What is the execution time per element of the result?