Алгоритм кражи работы

Question

Я читаю статью о Concurrency Runtime, и есть алгоритм с именем work stealing в этой статье. но я понятия не имею, что это за алгоритм! поэтому я хочу небольшое объяснение или какую-нибудь хорошую ссылку, которая могла бы помочь мне сделать презентацию об этом алгоритме.

Answer 1

Любые из них полезны?

Воровство в.NET 4.0

Планирование многопоточных вычислений путем кражи работ

Answer 2

Недавно я прочитал эту статью, в которой описывается среда Java Fork / Join с найденными здесь алгоритмами Work Stealing.

Взятые из этой статьи, мы начнем с этого:

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
    }
}

Эти разветвленные подзадачи (строка 2 в блоке else) могут сами рекурсивно создавать больше подзадач и таким образом заполнять рабочие очереди параллельно работающих потоков. Если один поток завершил работу и ему больше нечего делать, он может "украсть" работу из очереди другого потока.

Так много для краткости, для всех деталей, я бы посоветовал заглянуть в газету.

Answer 3

Довольно приятное и простое для понимания объяснение алгоритма Work Stealing, которое вы можете найти в следующем видео Channel9: "Параллельные расширения: внутри задачи Параллельное углубление" Даффи, Хусейн Йилдиз, Даан Лейджен, Стивен Туб, см. От 00:44:00 ( Даан Лейен)

Answer 4

Вы могли бы взглянуть на алгоритм Intel TBB для планировщика задач, он использует шаблон Work Stealing. См. https://software.intel.com/fr-fr/node/468190