Previous | Next --- Slide 29 of 48
Back to Lecture Thumbnails
tarabyte

Though this solution may only give an approximate solution, it is easy to parallelize because we can be sure that no red cells depend on each other an update them at the same time. Likewise, we can assume no black cells depend on each other.

kayvonf

@tarabyte. It turns out that this new algorithm does not yield an approximation to the original solution, it's an alternative iterative algorithm that converges to the same quality of solution. By using this algorithm, the developers gained the ability to parallelize widely, but did so at the cost of likely requiring additional iterations to converge to the desired error threshold. (In other words, the parallel program will do more work than the sequential one.)

elephanatic

I think that tradeoff is interesting. In order to get a better speedup in this case we are actually increasing the computational work of the algorithm. How do you determine when this is actually worth it? Do we/can we/should we assume some limit on the additional number of iterations this could take, or some minimum size of the grid with respect to the number of processors?

viveksri

I'm curious as to how different the results are because we're technically cheating on the algorithm, as compared to the original algorithm with the iterative update. How much worse is the correctness of the results, or does it just take longer to converge but is equally correct?

kayvonf

@viveksri: This problem is fundamentally well suited for employing a change in algorithm without impacting "correctness". This application is an iterative solver that needs to converge to within an error threshold, not obtain a specific number as a result. Therefore, we'd happy with an alternative solution that converges, even if it takes a different path to convergence.

This is a property of many optimization problems, such those used to train models in modern machine learning.

tarabyte

@kayvonf Ahh, I see what you mean by "approximation" on the last slide now. That's pretty cool! Thanks for the clarification. So, from a work and span perspective, the parallel algorithm has more work, but a small span. Is it useful to think of these problems from that perspective?

unparalleled

Just wanted to clarify here that the process of convergence becomes slow when we parallelise the execution. But the cost of increased convergence time is very less when compared to the gain we get from parallelism. So even though the convergence is slow, we do not see much of its implications. Is my understanding correct?

yeq

Is the convergence of this new approach guaranteed to be maintained? Are there any cases when the method diverge? The Gauss-Seidel model works fine with the 2-D grids since the dependency could be easily marked by two colors. As the dimension rises up to 3, the number of required marking colors also grows exponentially. It will make the convergence rate suffer more and incurs higher communication overhead.

yes

For many problems of this type where it's possible to change the algorithm without significantly impacting correctness, I wonder how it's determined whether the tradeoff between extra iterations before convergence are worth the speedup due to parallelization? Perhaps empirically?

Penguin

I think as the scale of the problem increases, parallel solutions such as the one in the slide become much more desirable. Also, designers in some cases can calculate whether the algorithm in the general case will terminate after few enough iterations to give an improvement over a more accurate algorithm, say calculating along the diagonals in the picture above.

tkli

@yeq Correct me if I am wrong, but I believe that the number of colors needed for 3 dimensions is still 2. If the coordinates of a point are (x,y,z), we can color this point x+y+z mod 2. Then, if a point depends on the points above, below, and horizontally, we know that (x,y,z) depends on (x+1,y,z),(x-1,y,z),(x,y+1,z),(x,y-1,z),(x,y,z+1),(x,y,z-1) all of which are a different color from (x,y,z). In addition, this pattern will generalize to 4 dimensions and higher!

l8b

I agree that only 2 colors should be needed for 3 dimensions. In 2 dimensions, a point has 4 neighbors, one in each direction, none of which are neighbors with each other. This allows us to color a point and its neighbors different colors. With three dimensions, we add two more neighbors on the top and bottom, but these new points are still not neighbors with each other or with the original 4 neighbors, so it's okay to color them all the same color.