work stealing algorithm

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.

Solution 1

Are any of these helpful?

Work-Stealing in .NET 4.0

Scheduling Multithreaded Computations by Work Stealing

Solution 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.

Solution 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)

Solution 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

View more solutions

Comments

[Lrrr]

Thanks, the first like was good enough:) but second link is so long:D

[Suresh]

very informative article. thanks for sharing.

[Suresh]

very informative video. thanks for sharing.

[Javad Alimohammadi]

The first link is broken.