If the execution time of the function varies considerably (i.e., some of the sub-problems are faster to solve), then you want to be able to keep the other processors busy with the next sub-problems while one of them keeps gnawing at a particularly difficult one.

If the timing is very predictable, OpenMP's parallel-for construct fits your bill very nicely.

Hmm, I thought OpenMP's worker-pool management did do that? E.g. if you have an 100-iteration loop, and have your num_threads set to 10, then it'll start up the first 10 subproblems; the first thread to finish will get the 11th, etc. If one of the first 10 is really slow, the other threads will still move on to churn on the rest of the loop iterations. Or is that not how it works?

Actually, you're right. OpenMP allows you to choose between "static" scheduling (where it would just cut the 100-iteration loop into 0..24, 25..49, 50..74, 75..99 if you have four processors) and "dynamic" scheduling with a specifiable block size (where it would, for a block size of 10, first chop off four iteration blocks of 0..9, 10..19, 20..29, 30..39, and allocate the other six blocks depending on which processor wants more work first).

According to the OpenMP tutorial, the default for OMP_SCHEDULE is implementation dependent, and the gcc OpenMP implementation uses dynamic scheduling with a chunk size of 1 by default.