What exactly is this algorithm? Why are the results immediately written back to the matrix, creating dependencies between computations in one sweep, instead of using a second matrix to apply the computations independently?
jerryzh
@Josephus, I think that is not our concern, this is just an example of one pattern of dependencies between different elements of the matrix, used as an illustration of how we could apply the dependency analysis and discover possible ways to parallelize the computation.
Khryl
Can we run this algorithm by placing the output into a new array B and not modifying array A, thus there will be no dependencies? To make this work we also need to interleave the role of array A and B. For example, first iteration use B as the output array, the next iteration use A as the output array.
vincom2
The algorithm seems to work by sweeps, so even on the same "iteration" over the matrix (i.e. what both @Josephus and @Khryl are probably thinking of when they say to use a separate output matrix), the calculations being done already depend on previous results generated during the current iteration (i.e. they would have to look at the "result matrix" B if you decided to use one). So using a separate matrix wouldn't help.
jerryzh
@Khryl, in this program, the value of A[i,j] depends on the old value of A[i, j] and all the element around it, A[i-1, j] and A[i,j-1] would be updated value. So, we could say that A[i,j] = 0.2 * (old A[i,j] + new A[i,j-1] + new A[i-1, j] + old A[i, j+1] + old A[i+1, j]). After this step, A[i,j] is updated to the new value and is used in later computations. Therefore, A[i,j] is dependent on A[i, j-1] and A[i-1, j]. If you put the result into array B, there will be the same dependencies between the elements of B.
zvonryan
@Khryl We should not place the output into a new array because this algorithm is designed to do sweeping while updating the values, thus making use of the newly updated values. We can take a look at this link The Gauss-Seidel Method.
pavelkang
I think this page will help people understand how to use a grid solver for PDEs: http://15462.courses.cs.cmu.edu/fall2015/lecture/pdes/slide_029
Basically, iterative update method is used to solve a differential equation. The update step runs until the difference converges.
What exactly is this algorithm? Why are the results immediately written back to the matrix, creating dependencies between computations in one sweep, instead of using a second matrix to apply the computations independently?
@Josephus, I think that is not our concern, this is just an example of one pattern of dependencies between different elements of the matrix, used as an illustration of how we could apply the dependency analysis and discover possible ways to parallelize the computation.
Can we run this algorithm by placing the output into a new array B and not modifying array A, thus there will be no dependencies? To make this work we also need to interleave the role of array A and B. For example, first iteration use B as the output array, the next iteration use A as the output array.
The algorithm seems to work by sweeps, so even on the same "iteration" over the matrix (i.e. what both @Josephus and @Khryl are probably thinking of when they say to use a separate output matrix), the calculations being done already depend on previous results generated during the current iteration (i.e. they would have to look at the "result matrix"
Bif you decided to use one). So using a separate matrix wouldn't help.@Khryl, in this program, the value of A[i,j] depends on the old value of A[i, j] and all the element around it, A[i-1, j] and A[i,j-1] would be updated value. So, we could say that A[i,j] = 0.2 * (old A[i,j] + new A[i,j-1] + new A[i-1, j] + old A[i, j+1] + old A[i+1, j]). After this step, A[i,j] is updated to the new value and is used in later computations. Therefore, A[i,j] is dependent on A[i, j-1] and A[i-1, j]. If you put the result into array B, there will be the same dependencies between the elements of B.
@Khryl We should not place the output into a new array because this algorithm is designed to do sweeping while updating the values, thus making use of the newly updated values. We can take a look at this link The Gauss-Seidel Method.
I think this page will help people understand how to use a grid solver for PDEs: http://15462.courses.cs.cmu.edu/fall2015/lecture/pdes/slide_029 Basically, iterative update method is used to solve a differential equation. The update step runs until the difference converges.