The tree implementation of barrier can be better because we eliminate the high contention that occurs at a single barrier. Here we rely on each of the sub tree barriers resolving quickly because less threads are being blocked at each barrier. The trade off is that this method requires more barriers, and I believe large portions of the tree could be held up by a few barriers that takes longer to resolve, however, that is still better than the centralized barrier case.
CSGuy
For trees that have some subtrees that are highly contended and some that aren't, it might be worthwhile to have centralized barriers on low contention subtrees and combining barriers on highly contended ones to reduce lock overhead while minimizing lock waiting.
koala
I agree @CSGuy. Similar to the main idea in lecture 19, we may want to incorporate a heterogeneous mixture of resources (or in this case, tree sizes) to achieve high parallelism.
The tree implementation of barrier can be better because we eliminate the high contention that occurs at a single barrier. Here we rely on each of the sub tree barriers resolving quickly because less threads are being blocked at each barrier. The trade off is that this method requires more barriers, and I believe large portions of the tree could be held up by a few barriers that takes longer to resolve, however, that is still better than the centralized barrier case.
For trees that have some subtrees that are highly contended and some that aren't, it might be worthwhile to have centralized barriers on low contention subtrees and combining barriers on highly contended ones to reduce lock overhead while minimizing lock waiting.
I agree @CSGuy. Similar to the main idea in lecture 19, we may want to incorporate a heterogeneous mixture of resources (or in this case, tree sizes) to achieve high parallelism.