For anyone interested in learning how a compiler could decide whether to run a loop iteratively or in parallel without the programmer having to declare independent loop iterations, I came across the GCD test:
This test checks whether loops that modify arrays can be legally parallelized. Consider:
For anyone interested in learning how a compiler could decide whether to run a loop iteratively or in parallel without the programmer having to declare independent loop iterations, I came across the GCD test:
This test checks whether loops that modify arrays can be legally parallelized. Consider:
for(i = 0; i < 500; i++) { A[Ki + L] = A[Mi+N]++; }
where A is an array, and K, L, M, and N are constants.
Each iteration of this loop is independent if $\not \exists i_1, i_2$ such that:
K$i_1$ + L = M$i_2$ + N
Using (Bezout's Lemma, we know that there are no such $i_1, i_2$ if GCD(K, M) does not divide N-L.
Perhaps someone who has taken compilers could explain another method loop dependency analysis.
This comment was marked helpful 3 times.