Slide summary: We can parallelize this algorithm by computing each element on a diagonal in parallel (note: NOT by doing all the diagonals in parallel) sweeping from the upper-left diagonal, since each element only depends on the points up and to the left.
However, this is not ideal since we only get peak parallelism at the largest diagonal (which isn't all that much compared to the number of elements to compute anyway), with very little parallelism at the beginning and end of the computation. Additionally, there has to be synchronization after every diagonal in order to correctly compute the next one, since each following diagonal depends on the previous one.
Slide summary: We can parallelize this algorithm by computing each element on a diagonal in parallel (note: NOT by doing all the diagonals in parallel) sweeping from the upper-left diagonal, since each element only depends on the points up and to the left.
However, this is not ideal since we only get peak parallelism at the largest diagonal (which isn't all that much compared to the number of elements to compute anyway), with very little parallelism at the beginning and end of the computation. Additionally, there has to be synchronization after every diagonal in order to correctly compute the next one, since each following diagonal depends on the previous one.
@jocelynh, nice comment.