In (Blumofe and Leiserson, 1993), it is shown that for any multi-threaded computation with work T 1 and task graph depth T ∞ , and for any number P of processors, a scheduling will achieve T P ≤ T 1 /P + T ∞ if for the scheduling holds that whenever there are more than P tasks ready, all P threads are executing work.
as long as there is work on any queue, no thread should be idle.