What happens if we write forall, but the loop iteration is not actually independent?
Is there a way to tell the compiler that part (but possibly not all) of a loop iteration is independent?
RomanArena
In the slides, it says that "Compiler understands loop iterations are independent, and that same loop body will be executed on a large number of data elements". And my question is that how does the compiler determine whether iterations are independent or not?such like by checking the instructions' impact on memory and registers in the loop?
kavyon
@williamx To your first question, remember that this is Kayvon's fictitious language. The forall syntax used here means that the programmer is letting the compiler assume that each iteration of the loop body is independent of the others. We can only hope that a well-written compiler for this language would do its best to determine if the loop iterations are actually independent or not, and if not, would fail or produce a warning message. However, if the compiler attempts to optimize code for which that assumption does not hold, then incorrect programs could be produced.
To answer your second question, if you find yourself wanting to just denote part of the loop body as independent, but not the rest, you may consider splitting up the loop body into two for loops: one that takes advantage of data-parallel optimizations and one that does not.
@RomanArena One method of determining whether iterations are independent of each other is by creating a dependency graph similar to how a superscalar processor would in Slide 4. However, it is important to note that iterations of a loop may sometimes be independent (say, it could be independent if a dynamically-determined address we're writing to is unique). The compiler may have to make conservative decisions when deciding whether code is independent or not.
What happens if we write forall, but the loop iteration is not actually independent?
Is there a way to tell the compiler that part (but possibly not all) of a loop iteration is independent?
In the slides, it says that "Compiler understands loop iterations are independent, and that same loop body will be executed on a large number of data elements". And my question is that how does the compiler determine whether iterations are independent or not?such like by checking the instructions' impact on memory and registers in the loop?
@williamx To your first question, remember that this is Kayvon's fictitious language. The
forallsyntax used here means that the programmer is letting the compiler assume that each iteration of the loop body is independent of the others. We can only hope that a well-written compiler for this language would do its best to determine if the loop iterations are actually independent or not, and if not, would fail or produce a warning message. However, if the compiler attempts to optimize code for which that assumption does not hold, then incorrect programs could be produced.To answer your second question, if you find yourself wanting to just denote part of the loop body as independent, but not the rest, you may consider splitting up the loop body into two for loops: one that takes advantage of data-parallel optimizations and one that does not.
@RomanArena One method of determining whether iterations are independent of each other is by creating a dependency graph similar to how a superscalar processor would in Slide 4. However, it is important to note that iterations of a loop may sometimes be independent (say, it could be independent if a dynamically-determined address we're writing to is unique). The compiler may have to make conservative decisions when deciding whether code is independent or not.