Previous | Next --- Slide 26 of 48
Back to Lecture Thumbnails
RomanArena

According to the update rule,

A[i,j] = 0.2f * (A[i,j] + A[i,j-1] + A[i-1,j] + A[i,j+1] + A[i+1,j]);

I think every element is dependent on 4 elements (top, bottom, left and right).

dyzz

I was also confused about this. This slide seems to contradict in terms of dependencies (as well as the diagonals slide).

If the slide is showing the true dependencies, could someone explain it to me?

If it is not, what would be the "correct" or "smarter" parallelism method for the corrected dependency graph.

kayvonf

The slide is correct, but I see how folks are getting confused. The dependencies on the slide are dependencies between operations in the same iteration of the solver. In other words, dependencies between iterations of the loop over elements -- this is the loop we are trying to parallelize.

Consider updating the elements in row-major order, as indicated by the code on the previous slide.

Now think about what happens in each iteration of the while loop in the solver:

When the code updates element (i,j), right after that it updates element (i+1,j). Note that the update to (i+1, j) depends on (i,j). This is a dependency represented by the horizontal arrows.

Also, not too long later, the code will also update (i,j+1), this is also a dependency on (i,j), indicated by the vertical arrows.

Yes, it's true that updating element (i,j) requires access to element (i+1,j), but element (i+1,j) was last updated in the previous solver iteration, and the dependencies we are concerned with here are dependencies within the loop over all the elements. We're trying to parallelize this loop, not parallelize around solver iterations.

sidzekrom

This problem is the same as finding a specific eigenvector of a $n^2\times n^2$ matrix. Are iterative methods the state of the art for computing an eigenvector, or are there other methods? I am interested in the literature surrounding this problem.

Metalbird

@sidzekrom from a quick search, it appears that in the general case for computing eigenvectors the state-of-the-art methods are typically iterative methods. However, there are special cases where you can use direct methods to solve these problems. That being said, I have seen some papers that talk about parallelizing at least the QR algorithm which can be used to solve the eigenvector problem.