From my understanding, work allocation is about riding a fine line between what we define as a task. We don't want to define tasks as too granular because then the overhead to communicate and synchronize is too high. We don't want them to be too big because then there's a poor work distribution.

Expanding on rosalg's comment, my understanding is that the extreme cases for partitioning would be completely fine partitioning similar to the example on this slide, vs. taking the entire problem to be one task, aka running it sequentially. Kayvon remarked in lecture that the ideal mid-point for performance is often determined empirically.

Yeah, along the lines of what has been mentioned here already, to me answering the question "So... Is it a problem?" requires an understanding of how substantial the work is that you do during each task, and how that relates proportionally to the amount of time you might spend on and acquiring a lock. In the case of the specific code example shown on the left, testing the primality of a number is a relatively computationally intense activity, so its likely that the synchronization overhead introduced here is acceptable.

I disagree with you here nick, yes it is true that the primality of a number can be computationally intense, but generally if we are dealing with a small number or an even number then the ratio of the computation time to the overhead would be small enough that we wouldn't experience that much speedup. I think that a more unpredictable problem like the 3n + 1 problem would be an acceptable problem where we don't need to care about the overhead that much.

@marwan That's a good point that the workload of the primality test can vary drastically and can be quite small for small and even numbers. I guess that's why the diagram in this slide has a fair number of blocks that are quite small, which makes the synchronization overhead compared to these blocks pretty substantial. I agree with you that we would care less about the synchronization overhead if we knew that each component of our workload was going to be fairly computationally intensive!