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 7.4, 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 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.

Consider the following piece of C code:

Instructions have the following associated latencies (in cycles):

Transcribed Image Text:

for (j 2; j<1000; j++) D[j] = D[j-1]+D[j-2]; The MIPS code corresponding to the above fragment is: DADDIU r2, r2,999 loop: L.D L.D ADD.D S.D DADDIU BNE f1, -16(f1) f2, -8(f1) f3, f1, f2 f3, 0(rl) rl, rl, 8 r1, r2, loop