work stealing algorithm [closed]

Question

Closed. This question needs to be more focused. It is not currently accepting answers.

---

Want to improve this question? Update the question so it focuses on one problem only by editing this post.

Closed 6 years ago.

Improve this question

I am reading an article about Concurrency Runtime, and there is algorithm named work stealing in this article. but I have no idea what this algorithm is! so I want a little explanation or some good link that could help me to make a presentation about this algorithm.

Answer 1

Are any of these helpful?

Work-Stealing in .NET 4.0

Scheduling Multithreaded Computations by Work Stealing

Answer 2

I recently read that paper, which describes a Java Fork / Join framework with Work Stealing Algroithms found here

Taken from that paper, we start with this:

Result solve(Problem problem) {
    if (problem is small)
       directly solve problem
    else {
       split problem into independent parts
       fork new subtasks to solve each part
       join all subtasks
       compose result from subresults
    }
}

Those forked subtasks (line 2 in the else block) can recursively create more subtasks themself and thus fill up the working queues of the parallely working threads. If one thread finished and has nothing more to do, he can "steal" the work from the queue of another thread.

So much for short, for all the details I would suggest looking into the paper.

Answer 3

Pretty nice and easy-to-understand explanation of the Work Stealing algorithm you can find in the following Channel9 video: "Parallel Extensions: Inside the Task Parallel Going Deep" Duffy, Huseyin Yildiz, Daan Leijen, Stephen Toub, see from 00:44:00 (by Daan Leijen)

Answer 4

you could have a look at Intel TBB algorithm for task scheduler, it is using Work Stealing pattern. See https://software.intel.com/fr-fr/node/468190