work-stealing applications in real life

[David_S_10]

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.

[TimP]

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.

[jimdempseyatthecove]

"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 LOOP1: 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 END LOOP1 LOOP2: 3) threads atomically picking tasks from the non-spin-wait task list END LOOP1 barrier 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