2023 1 Loop Unrolling 40 marks Consider the following loop loop l d f4 0 r1 | Assignment Collections

1. Loop Unrolling [40 marks]

Consider the following loop:

loop: l.d    f4,0(r1)    l1  
      l.d    f6,0(r2)    l2  
      mul.d  f4,f4,f0    m1  
      mul.d  f6,f6,f2    m2  
      add.d  f4,f4,f6    a1  
      s.d    f4,0(r1)    s1  
      daddui r1,r1,#-8   sub1
      daddui r2,r2,#-8   sub2
      bnez   r1,loop     br

Note: Our default is that FP arithmetics have 4 x-boxes.  

a) [4 marks] Using the names ‘l1’ to ‘s1’ for the first six instructions
in the body of this loop, draw the flow-dependence graph for just these
instructions.  Label each arrow with the dependence gap between the
producer and the consumer.

graph:

In what follows, focus on three flow-dependence types: i) FP arith to
FP arith, ii) FP arith to FP store, and iii) FP load to FP arith.  Denote
the number of m-boxes in memory references by ‘#m’, and the number of
x-boxes in FP arithmetics by ‘#x’.  By the way, memrefs have one x-box,
and arithmetics have one (never-used) m-box.

b) [6 marks] For each of the three designated flow-dependence types,
indicate the number of stalls in adjacent producer-consumer pairs as
functions of ‘#m” and ‘#x’.

FP arith —> FP arith =
FP arith —> FP store =
FP load  —> FP arith =

c) [10 marks] Suppose #m = 1 and #x = 4.  How many stalls occur in one
iteration of the loop if it is executed exactly as written?  Don’t
write out a space-time diagram; use the method of Chapter 3.

ans:

e) [10 marks] Unroll the loop twice.  If one reschedules the unrolled
loop optimally, how many stalls are left?  (Keep the branch as the last
instruction.  Show the rescheduled code using the _short_ names.)

ans:

f) [10 marks] Increases the ‘mul-add dependence gap’ to 5 cycles, leaving
everything else unchanged.  Unroll the loop three times.  If one reschedules
the unrolled loop optimally, how many stalls are left?  (Keep the branch as
the last instruction.  Show the rescheduled code using the _short_ names.)

ans:

2. Dynamic Instruction Scheduling I [30 marks]

Imagine that reservation stations only track whether floating-point operands
are valid, and that integer operands appear by magic whenever needed.

a) [10 marks] Stage instructions ‘l1’ to ‘s1’ to reservation stations rs1(l1)
to rs6(s1).  Show the contents of each reservation station.  Indicate both
present and pending operands in each station.  For the loads, you may make
the operand entries ‘blank’.  That is, mark all load dependences as resolved.
For the store, just invent a regular single-operand reservation station.

rs1(l1):
rs2(l2):
rs3(m1):
rs4(m2):
rs5(a1):
rs6(s1):

b) [10 marks] After both loads have completed, but no further action has
occurred, show the contents of each reservation station.  You may mark
entire reservation stations as ‘free’.  Syntax: result[rs9(a9)]; val[f12].
You may alter the tag inside parentheses if warranted. 

rs1(l1):
rs2(l2):
rs3(m1):
rs4(m2):
rs5(a1):
rs6(s1):

c) [10 marks] At this point, dispatch the two loads of the second iteration,
viz., ‘l3’ and ‘l4’, into reservation stations ‘rs1’ and ‘rs2’.  Moreover,
let instruction ‘m1’ of the first iteration complete.  Show the contents of
each reservation station.

rs1(l3):
rs2(l4):
rs3(m1):
rs4(m2):
rs5(a1):
rs6(s1):

3. Dynamic Instruction Scheduling II [15 marks]

a) [5 marks] Find a flow dependence in the original code, and show that it
cannot cause harm.

ans:

b) [5 marks] Find an antidependence in the original code, and show that it
cannot cause harm.

ans: 

c) [5 marks] Find an output dependence in the original code, and show that
it cannot cause harm.

ans:

4. Load Buffers and Store Buffers [15 marks]

a) [5 marks] Consider two code sequences:

l.d f4,0(r1)      l.d f6,0(r1)
s.d f6,0(r1)      s.d f6,0(r1)

Show that ignoring the register dependence and respecting the memory
dependence provides a uniform, correct solution to issue delay in
both code sequences.

ans:

b) [5 marks] Consider:

s.d f4,0(r1)
l.d f6,0(r1)

Assume these two instructions have been loaded into a store buffer and
a load buffer, respectively.  There is a memory dependence.  If we
delay the issue of the load until the store “completes”, operationally
what do we mean by “complete”?  (Forwarding is a different approach).

ans:

c) [5 marks] A _speculated_ load is allowed to progress through more
stages of an out-of-order pipeline compared to a _speculated_ store.
What is difference and why is it necessary?

ans: