Работа воровства и отдыха

Question

Зачем нам нужен дерок для кражи работы? (например, в Cilk). Владелец работает сверху, а вор крадет со дна. Почему это полезно?

У нас может быть несколько похитителей воров со дна. Итак, разве нам не нужен замок? Я где-то читал, что более крупные задания (например, созданные в дереве) добавляются к нижней части. Таким образом, кража с дна более эффективна (меньше общения, поскольку воры становятся более занятыми, крадя их). Это оно?

Answer 1

Детали В протоколе описаны в разделе 5 «Реализация на Cilk-5 многопоточных язык», который доступен из MIT: http://supertech.csail.mit.edu/papers/cilk5.pdf

Answer 2

Вам не нужно Deque для работы воровства. Возможно (и люди сделали это) использовать параллельную структуру данных для хранения пула задач. Но проблема в том, что операции push/pop от рабочих и запросы воровства от воров должны быть синхронизированы.

Поскольку из-за кражи, как ожидается, будут относительно редкими событиями, можно создать структуру данных, чтобы синхронизация выполнялась по-разному во время попыток кражи, и даже тогда, когда вполне вероятно, что может возникнуть конфликт при появлении элемента из структура данных. Именно поэтому в Cilk использовались deques - чтобы минимизировать синхронизацию. Работники рассматривают свои собственные деки как стек, толкают и выталкивают нити снизу, но обрабатывают deque другого занятого рабочего как очередь, крадя потоки только сверху, всякий раз, когда у них нет локальных потоков для выполнения. Так как операция кражи синхронизирована, все равно, что несколько воров пытаются украсть у одной и той же жертвы.

Дополнительные задания, добавляемые на дно, распространены в алгоритмах типа «разделяй и властвуй», но не все. Существует множество различных стратегий для того, что делать во время кражи. Украдите одну задачу, несколько задач, половину задач и т. Д. Каждый из этих вариантов хорошо работает для некоторых приложений и не так хорош в других.

Answer 3

Кража работы на самом деле действительно нуждается в deque. В оригинальной работе они доказали максимальную используемую память в системе с процессорами P. Предел задается максимальным размером любого стека, умноженным на количество процессоров. Это на самом деле возможно только после использования теоремы занятых листов. Кроме того, еще одной важной особенностью кражи работы является то, что: Когда работник делает икру, он немедленно спасает создателя на deque и начинает работать над ребенком. Для получения дополнительной информации об их доказательствах, пожалуйста, прочитайте их оригинальную статью, в которой они объясняют все, что я говорю. http://supertech.csail.mit.edu/papers/steal.pdf

Контроль параллелизма при работе с краткими образами доступа не связан с планировщиком работы, и на самом деле было сделано много исследований по устранению блокировок из deque (с использованием незакрепленных конструкций), а также для сведения к минимуму насколько возможно, барьеры памяти. Например, в этой статье (я сожалею, если не могу получить доступ, но вы можете прочитать резюме в любом случае, чтобы получить эту идею): http://dl.acm.org/citation.cfm?id=1073974 авторы создают новый инструмент для улучшения вышеупомянутых аспектов.

Кражи сделаны со стороны, над которой рабочий не работает, по нескольким причинам: Поскольку deque действует как стек для каждого работника (владельца deque), «большие» задания должны быть сверху (как вы можете понять, прочитав статью). Когда я говорю больше, я хочу сказать, что это, вероятно, те, которые будут иметь больше вычислений. Кроме того, еще один важный аспект заключается в том, что, делая это (краду с противоположной стороны работы владельца deque), уменьшается конкуренция, так как в некоторых новых деках жертва и вор могут одновременно работать на одном и том же уровне.