"Work stealing" vs. "Work shrugging (tm)"?
- by John
Why is it that I can find lots of information on "work stealing" and nothing on a "work shrugging(tm)" as a load-balancing strategy?
I am surprised because work-stealing seems to me to have an inherent weakness when implementating efficient fine-grained load-balancing. Vis:- Relying on consumer processors to implement distribution (by actively stealing) begs the question of what these processors do when they find no work?
None of the work-stealing references and implementations I have come across so far address this issue satisfactorarily for me. They either:-
1) Manage not to disclose what they do with idle processors! [Cilk] (?anyone know?)
2) Have all idle processors sleep and wake periodically and scatter messages to the four winds to see if any work has arrived [e.g. JAWS] (= way too latent & inefficient for me).
3) Assume that it is acceptable to have processors "spinning" looking for work ( = non-starter for me!)
Unless anyone thinks there is a solution for this I will move on to consider a "Work Shrugging(tm)" strategy. Having the task-producing processor distribute excess load seems to me inherently capable of a much more efficient implementation. However a quick google didn't show up anything under the heading of "Work Shrugging" so any pointers to prior-art would be welcome.
tx
Tags I would have added if I was allowed to [work-stealing]
