Question:Consider the following piece of C code:
for (j=2;j<1000;j++)
D[j] = D[j−1]+D[j−2];
Th e MIPS code corresponding to the above fragment is:
addiu \(s2,\)zero,7992
addiu \(s1,\)zero,16
loop: l.d \(f0, _16(\)s1)
l.d \(f2, _8(\)s1)
add.d \(f4, \)f0, \(f2
s.d \)f4, 0(\(s1)
addiu \)s1, \(s1, 8
bne \)s1, $s2, loop
Instructions have the following associated latencies (in cycles):
6.4.1 How many cycles does it take for all instructions in a single iteration of the above loop to execute?
6.4.2 When an instruction in a later iteration of a loop depends upon a data value produced in an earlier iteration of the same loop, we say that there is aloop carried dependencebetween iterations of the loop. Identify the loop-carried dependences in the above code. Identify the dependent program variable and assembly-level registers. You can ignore the loop induction variable j.
6.4.3 Loop unrolling was described in Chapter 4. Apply loop
unrolling to this loop and then consider running this code on a 2-node distributed memory message-passing system. Assume that we are going to use message passing as described in Section 6.7, where we introduce a new operation send (x, y) that sends to node x the value y, and an operation receive( ) that waits for the value being sent to it. Assume that send operations take a cycle to issue (i.e., later instructions on the same node can proceed on the next cycle), but take 10 cycles to be received on the receiving node. Receive instructions stall execution on the node where they are executed until they receive a message. Produce a schedule for the two nodes assuming an unroll factor of 4 for the loop body (i.e., the loop body will appear 4 times). Compute the number of cycles it will take for the loop to run on the message passing system.
6.4.4 The latency of the interconnect network plays a large role in the efficiency of message-passing systems. How fast does the interconnect need to be in order to obtain any speedup from using the distributed system described in Exercise 6.4.3
