work-stealing applications in real life

work-stealing applications in real life

There are many papers about work-stealing in the academic.  Cilk ,Cilk plus,TPL and so on also use work stealing. I want to know which applications are suitable to be solved by work-stealing in real life.

 I'm studying the fine-grained task parallelism now.   I also want to know which applications are suitable written in fine-grained task parallelism in real life. Thank you very much.

3 posts / 0 new
Last post
For more complete information about compiler optimizations, see our Optimization Notice.

The Wikipedia article notes that clarification is needed on the terminology "fine-grained task parallelism." I'm skeptical about equating it with work-stealing.
In case it's of interest, I'll point out the contrast between OpenMP and cluster applications where it's most efficient to set processor affinity and static scheduling prior to beginning the job, vs. the work-stealing model where there is no affinity setting. Those jobs can be accomplished by a work-stealing model; it simply takes longer.

"fine-grained task parallelism." is a subjective term. This generally means the amount of work/task is relatively small (what is relatively?).
In a general tasking system, task switching is generalized and has "reasonable" overhead. Further the task switch is performed as if there is no interdependance of the tasks.

For fine-grained task parallelism your design goal is to reduce the task selection overhead as well as eliminate spin-waits for threads in your thread group. Therefore, the design of the section of the application using fine-grained parallelism would:

a) pre-construct two task list (pick lists); One known to have spin-waits (e.g. mutex) and the other known not to have spin-waits
b) request of the general task manager that other threads may join in the picking
c) initiating thread immediately begins atomically picking tasks from the spin-wait task list
d) other threads join and continues atomically picking tasks from the task list
3) threads atomically picking tasks from the non-spin-wait task list

The above can be further enhanced by
Should a thread in the "fine-grained parallelism" encounter what would othewise be a spin-wait, instead of spinning, it picks another task from the non-spin-wait pick list.

Once running the "task switching" overhead is ~that of an atomic incriment of the index into the pick lis(s)

Jim Dempsey

Leave a Comment

Please sign in to add a comment. Not a member? Join today