[pmoriarty]

"In an ideal world all of your tasks would take exactly as long as the other, because if one task takes far longer than the others you have to wait for it. So, the minimal run time of your parallel problem is bound by the time of your longest sub-problem. If one of the problems takes far longer than the others (and they depend on each other) you've lost."

Could the cores that would otherwise be waiting for the longest sub-problem to complete start working on some new sub-problems to make the following set of sub-problems finish sooner?

[sgift]

If you have a set left that doesn't depend on the result of the problem still in computation you can do this, yes. Though in that case you don't actually have two sets, you have one set which is bigger than your core count. I simplified a bit before, but if you have more problems than cores your longest sub-problem shouldn't run longer than the time it takes you to compute all other sub-problems (i.e. that includes computing five sub-problems on one core while another core computes one longer problem) or you'll have to wait.

Unfortunately, I had this happen to a program of mine last year. All other tasks were long done but one kept running and running. The run time of the program escalated to hours with the first few minutes being marked by high usage of the system and then only one core in use, while everything else had to wait. It sucked.