Chapter 5, Problem 16E

Explanation of Solution

a.

Explanation for the given code:

• In the give code, “A” and “B” are the arrays of pointer to structures.
• Every pointer is four bytes long.
• The programmers are interested in the value of fields at an offset of 12 bytes from the beginning of the structure.
• The C source program might look something like $\text{S := A [k] }\to \text{ f + B[k] }\to \text{ f;}$

Explanation of Solution

b.

Identifying flow dependences:

There are flow dependences from

• Instruction 1 to instruction 4 (r1)
• Instruction 2 to instruction 5 (r4)
• Instruction 3 to instruction 8 (r6)
• Instruction 4 to instruction 5 (r2)
• Instruction 4 to instruction 8 (r2)
• Instruction 5 to instruction 6 (r3)
• Instruction 6 to instruction 7 (r3)
• Instruction 7 to instruction 11 (r5)
• Instruction 8 to instruction 9 (r3)
• Instruction 9 to instruction 10 (r3)
• Instruction 10 to instruction 11 (r7)
• Instruction 11 to instruction 12 (r3)

Identifying anti-dependences:

• There are anti-dependences from instruction 6 to 8, 9, and 11;
  • Instruction 7 to 8, 9, and 11;
  • Instruction 9 to 11; and
  • Instruction 10 to 11.
• All of them are carried by “r3” register.

Identifying output dependences:

• There are output dependences from instruction 5 to 6, 8, 9, and 11;
  • Instruction 6 to 8, 9, and 11;
  • Instruction 8 to 9 and 11; and
  • Instruction 9 to 11.
• Again, all are carried by “r3” register.

Explanation of Solution

c.

Scheduling the code to reduce the load delay on a single-pipeline, in-order processor:

• There are 3 load delays to worry about, after the instructions 6, 9, and 10.
• The best way is to move an instruction down into the delay slot of instruction 6.

Modified code is as follows:

$\begin{array}{l}1. r1:=l\\ 2. r4:=\&A\\ 3. r2:=r1\times 4\\ 4. r3:=r4+r2\\ 5. r3:=*r3\\ 6. r6:=\&B ---filledthisslot\\ 7. r5:=*\left(r3+12\right)\\ 8. r3:=*r6+r2 \\ 9. r3:=*r3 ---stilladelayafterthisload\\ 10. r7=*\left(r3+12\right)---andthisone\\ 11. r3:=r5+r7\\ 12. S:=r3\end{array}$

There will still be delays after instruction 9 and 10.

Explanation of Solution

d.

Justification:

“Yes”, if the programmer introduce a new register name (r8) for the reuse of “r3” at instruction 8 then the programmer can move the second load downward, where it becomes instruction 9:

$\begin{array}{l}1. r1:=l\\ 2. r4:=\&A\\ 3. r2:=r1\times 4\\ 4. r3:=r4+r2\\ 5. r3:=*r3\\ 6. r6:=\&B \\ 7. r8:=r6+r1\\ 8. r8:=\text{ *}r8 \\ 9. r5:=*\left(r3+12\right) ---filledthisslot\\ 10. r7=*\left(r8+12\right)---stilladelayafterthisload\\ 11. r3:=r5+r7\\ 12. S:=r3\end{array}$

Without a longer window to consider, there is still no way to delete the delay after instruction 10.