Question:
Exercise 4.2 requests a list of the dependences. It seems to me that there exists a true dependency from S1 to S3 on a. This is not listed in the answer. Is this because S3 does not do useful work? Does the existance of a true dependence require that the code is useful code? If that is the case, then anytime we are trying to determine the dependence, we will have to verify the usage of the code. Is this the case?
Answer:
This is a bad example of a tricky situation... Obviously, since the last instruction is not doing any useful work, there is no data-flow alteration because of this dependency. I would personally list it when solving the problem. If you look in the textbook pg. 229, in the definition of a data dependence it says that "An instruction j is data-dependent on instruction i if EITHER of the following holds: a) Instruction i produces a result that is used by instruction j, or b) (etc...)" It says nothing on whether this result actually affects the data-flow of the program, although later on the text the authors make a case that the ultimate criterion is the data-flow correctness. There is a lot of tricks one can play but in our case I would consider both answers correct. I said above that this is a bad example, because if you have a smart compiler that is going to find all these nice dependencies and optimize them, it better find the garbage of the program (e.g, S3) and get rid of them, otherwise it's pointless to do all these things. In short, a smart compiler would have gotten rid of this instruction before trying to parallelize and therefore we wouldn't have to deal with this tricky situation of whether something is or is not a dependency.
Question:
In Exercise 4.3 the reason given that f = f + 2 can not be moved before the if statement is that "the value of f is conditionally computed and the value of f is used after the conditional statement". My question is what does "conditionally computed" have to do with anything. We can move d = d + 2 before the if statement and it is "conditionally computed" isn't it? I understand that you can't move f = f + 2 because the value of f is used after the conditioal statement, but how does "conditionally computed" play in the answer?
Answer:
Well, it doesn't. Even if it wasn't "conditionally computed", for example if it was right after the ELSE part, you still would not be able to put it above the IF, because of the dependency with c=c+f and b=a+f. It's just a bad explanation.
Question:
Still another question: On exercise 4.4, I believe the last three lines given in the answer key should read:
SD 16(R2), F0
BNEZ R1, loop
SD 8(R2), F6
In this way the unrolled code will access the same storage locations as the original code. Before moving the SUBI commands infront of the SD command functionally equivalent code after unrolling and interleaving is:
SD 0(R2), F0
SD -8(R2), F6
SUBI R1, R1, #16
SUBI R2, R2, #16 ...
The code in the answer would work, so is it normally the case that memory refernce is shifted for some purpose?
Answer:
Ok, you are right, the code in the answer is wrong. It should read exactly what you mentioned above otherwise it will store F0 in R2-16+8=R2-8 instead of R2, and F6 om R2-16+0=R2-16 instead of R2-8 that are the correct memory locations.