Кража работы

Алгоритм параллельных вычислений

В параллельных вычислениях кража работы — это стратегия планирования для многопоточных компьютерных программ. Она решает проблему выполнения динамически многопоточного вычисления, которое может «порождать» новые потоки выполнения, на статически многопоточном компьютере с фиксированным числом процессоров (или ядер ). Она делает это эффективно с точки зрения времени выполнения, использования памяти и межпроцессорного взаимодействия.

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

Кража работы контрастирует с разделением работы , другим популярным подходом к планированию для динамической многопоточности, где каждый рабочий элемент планируется на процессоре, когда он порождается. По сравнению с этим подходом, кража работы уменьшает объем миграции процесса между процессорами, поскольку такая миграция не происходит, когда все процессоры должны что-то сделать. ^[2]

Идея перехвата работы восходит к реализации языка программирования Multilisp и работе над параллельными функциональными языками программирования в 1980-х годах. ^[2] Она используется в планировщике для языка программирования Cilk , ^[3] фреймворке fork/join Java , ^[4] библиотеке параллельных задач .NET , ^[5] и среде выполнения Rust Tokio . ^{[6] [7]}

Модель исполнения

Work stealing разработан для «строгой» модели fork–join параллельных вычислений, что означает, что вычисление можно рассматривать как направленный ациклический граф с одним источником (начало вычисления) и одним стоком (конец вычисления). Каждый узел в этом графе представляет либо вилку , либо соединение . Вилки производят несколько логически параллельных вычислений, называемых по-разному «нитями» ^[2] или «нитями». ^[8] Ребра представляют последовательные вычисления. ^{[9] [примечание 1]}

В качестве примера рассмотрим следующую тривиальную программу fork-join в синтаксисе, подобном Cilk :

функция f(a, b): c ← вилка g(a) г ← ч(б) присоединиться вернуть с + dфункция g(a): вернуть × 2функция h(a): б ← вилка г(а) с ← а + 1 присоединиться вернуть б + с

Вызов функции f(1, 2) приводит к следующему графу вычислений:

В графе, когда два ребра покидают узел, вычисления, представленные метками ребер, логически параллельны: они могут выполняться либо параллельно, либо последовательно. Вычисление может продолжаться только после узла соединения , когда вычисления, представленные его входящими ребрами, завершены. Работа планировщика теперь заключается в назначении вычислений (ребер) процессорам таким образом, чтобы все вычисления выполнялись до завершения в правильном порядке (ограниченном узлами соединения), желательно как можно быстрее.

Алгоритм

Рандомизированная версия алгоритма кражи работы, представленная Блюмофом и Лейзерсоном, поддерживает несколько потоков выполнения и распределяет их по процессорам . Каждый из процессоров имеет двухстороннюю очередь (deque) потоков. Назовем концы deque «top» и «bottom». ${\displaystyle P}$

Каждый процессор, имеющий текущий поток для выполнения, выполняет инструкции в потоке одну за другой, пока не встретит инструкцию, которая вызывает одно из четырех «особых» поведений: ^{[2] : 10}

• Инструкция spawn приводит к созданию нового потока. Текущий поток помещается в конец очереди, и процессор начинает выполнять новый поток.
• Инструкция остановки — это та, которая временно останавливает выполнение своего потока. Процессор выталкивает поток из нижней части своего дека и начинает выполнение этого потока. Если его дек пуст, он начинает захват работы, как описано ниже.
• Инструкция может привести к остановке потока . Поведение в этом случае такое же, как и для инструкции, которая останавливается.
• Инструкция может включить другой поток. Другой поток помещается в конец очереди, но процессор продолжает выполнение текущего потока.

Первоначально вычисление состоит из одного потока и назначается некоторому процессору, в то время как другие процессоры начинают простаивать. Любой процессор, который становится простаивающим, запускает фактический процесс кражи работы, что означает следующее:

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

Детское воровство против продолжения воровства

Обратите внимание, что в правиле для spawn Блюмоф и Лейзерсон предлагают, чтобы «родительский» поток выполнял свой новый поток, как будто выполняя вызов функции (в C-подобной программе f(x); g(y); вызов функции f завершается до того, как выполняется вызов g ). Это называется «похищением продолжения», потому что продолжение функции может быть похищаемо во время выполнения порожденного потока, и является алгоритмом планирования, используемым в Cilk Plus . ^[8] Это не единственный способ реализовать похитение работы; альтернативная стратегия называется «похищением потомка» и ее проще реализовать в виде библиотеки , без поддержки компилятора . ^[8] Похищение потомка используется Threading Building Blocks , Microsoft Task Parallel Library и OpenMP , хотя последний дает программисту контроль над используемой стратегией. ^[8]

Эффективность

Было предложено несколько вариантов кражи работы. Рандомизированный вариант, предложенный Блюмофе и Лейзерсоном, выполняет параллельное вычисление за ожидаемое время на процессорах; здесь — работа , или количество времени, необходимое для выполнения вычисления на последовательном компьютере, а — промежуток , количество времени, необходимое на бесконечно параллельной машине. ^{[примечание 2]} Это означает, что в ожидании требуемое время — это максимум постоянный множитель, умноженный на теоретический минимум. ^[2] Однако время выполнения (в частности, количество выполненных краж) может быть экспоненциальным в худшем случае. ^[10] Локализованный вариант, в котором процессор пытается украсть свою собственную работу, когда она свободна, также был проанализирован теоретически и практически. ^{[11] [12]} ${\displaystyle T_{1}/P+O(T_{\infty })}$ ${\displaystyle P}$ ${\displaystyle T_{1}}$ ${\displaystyle T_{\infty }}$ ${\displaystyle T_{\infty }}$

Использование пространства

Вычисление, запланированное версией перехвата работы Блюмофе–Лейзерсона, использует стековое пространство , если бы это было использование стека тем же вычислением на одном процессоре, ^[2] что соответствует собственному более раннему определению эффективности пространства авторами. ^[13] Эта граница требует продолжения перехвата; в планировщике перехвата потомков она не выполняется, как можно увидеть из следующего примера: ^[8] ${\displaystyle O(S_{1}P)}$ ${\displaystyle S_{1}}$

для i = 0 до n: fork f(i) join

В реализации с кражей потомков все «разветвленные» вызовы f помещаются в очередь работ, которая таким образом увеличивается до размера n , который может быть сделан произвольно большим.

Вариант мультипрограммирования

Алгоритм кражи работы, описанный ранее, и его анализ предполагают вычислительную среду, в которой вычисление запланировано на наборе выделенных процессоров. В среде многопрограммирования (многозадачности) алгоритм должен быть изменен, чтобы вместо этого запланировать вычислительные задачи на пул рабочих потоков , которые, в свою очередь, планируются на фактические процессоры планировщиком операционной системы . В любой момент времени планировщик ОС назначит процессу кражи работы некоторое число P _A ≤ P из P процессоров в компьютере, поскольку другие процессы могут использовать оставшиеся процессоры. В этой настройке кража работы с пулом из P рабочих потоков имеет проблему, заключающуюся в том, что рабочие, действующие как воры, могут вызвать лайвлок : они могут блокировать выполнение рабочих, которые на самом деле порождают полезные задачи. ^{[14] [15]}

Для этой ситуации был разработан вариант перехвата работы, который выполняет вычисления за ожидаемое время.

$${\displaystyle O\left({\frac {T_{1}}{P_{\mathrm {avg} }}}+{\frac {T_{\infty }P}{P_{\mathrm {avg} }}}\right),}$$

где P _avg — среднее количество процессоров, выделенных для вычисления планировщиком ОС за время выполнения вычисления. ^[16] Многопрограммный планировщик работ отличается от традиционной версии в двух отношениях:

• Его очереди неблокируемые . Хотя на выделенных процессорах доступ к очередям может быть синхронизирован с помощью блокировок , это не рекомендуется в многопрограммной среде, поскольку операционная система может прервать рабочий поток, удерживающий блокировку, блокируя ход выполнения любых других рабочих потоков, которые пытаются получить доступ к той же очереди.
• Перед каждой попыткой украсть работу рабочий поток вызывает системный вызов « yield », который уступает процессор, на котором он запланирован, ОС, чтобы предотвратить «голодание» .

Попытки улучшить многопрограммный кражу работы были сосредоточены на проблемах локальности кэша ^[12] и улучшенных структурах данных очереди. ^[17]

Альтернативы

Несколько алгоритмов планирования для динамически многопоточных вычислений конкурируют с кражей работы. Помимо традиционного подхода разделения работы, существует планировщик, называемый параллельным глубинным (PDF), который улучшает границы пространства кражи работы, ^[18] а также обеспечивает лучшую производительность в некоторых ситуациях, когда ядра чипа мультипроцессора совместно используют кэш. ^[1]

Примечания

1. В исходной презентации последовательные вычисления также были представлены в виде узлов, а направленное ребро представляло отношение «следует за».
2. Определения см . в анализе параллельных алгоритмов .

Ссылки

1. Chen, Shimin; Gibbons, Phillip B.; Kozuch, Michael; Liaskovitis, Vasileios; Ailamaki, Anastassia; Blelloch, Guy E.; Falsafi, Babak; Fix, Limor; Hardavellas, Nikos; Mowry, Todd C.; Wilkerson, Chris (2007). Планирование потоков для конструктивного совместного использования кэша на CMP (PDF) . Proc. ACM Symp. on Parallel Algorithms and Architectures. стр. 105–115.
2. Blumofe, Robert D.; Leiserson, Charles E. (1999). «Планирование многопоточных вычислений с помощью перехвата работы» (PDF) . J ACM . 46 (5): 720–748. doi :10.1145/324133.324234. S2CID  5428476.
3. Blumofe, Robert D.; Joerg, Christopher F.; Kuszmaul, Bradley C.; Leiserson, Charles E.; Randall, Keith H.; Zhou, Yuli (1996). «Cilk: эффективная многопоточная система времени выполнения». Журнал параллельных и распределенных вычислений . 37 (1): 55–69. doi : 10.1006/jpdc.1996.0107 .
4. Дуг Ли (2000). Java fork/join framework (PDF) . ACM Conf. on Java.
5. Лейен, Даан; Шульте, Вольфрам; Буркхардт, Себастьян (2009). «Проектирование библиотеки параллельных задач». Уведомления ACM SIGPLAN . 44 (10): 227. CiteSeerX 10.1.1.146.4197 . дои : 10.1145/1639949.1640106. 
6. "Что такое Токио? · Токио". tokio.rs . Получено 2020-05-27 .
7. Крилл, Пол (08.01.2021). "Tokio Rust runtime достигает статуса 1.0". InfoWorld . Получено 26.12.2021 .
8. Робинсон, Арч (15 января 2014 г.). Учебник по планированию параллелизма Fork–Join с захватом работы (PDF) (Технический отчет). ISO/IEC JTC 1/SC 22 /WG 21 — Комитет по стандартам C++ . N3872.
9. Halpern, Pablo (24 сентября 2012 г.). Strict Fork–Join Parallelism (PDF) (Технический отчет). ISO/IEC JTC 1/SC 22 /WG 21 — Комитет по стандартам C++ . N3409=12-0099.
10. Лейзерсон, Чарльз Э .; Шардл, Тао Б.; Суксомпонг, Варут (2016). «Верхние границы количества краж в корневых деревьях». Теория вычислительных систем . 58 (2): 223–240. arXiv : 1706.08219 . doi : 10.1007/s00224-015-9613-9. S2CID  424692.
11. Suksompong, Warut; Leiserson, Charles E .; Schardl, Tao B. (2016). «Об эффективности локального хищения работы». Information Processing Letters . 116 (2): 100–106. arXiv : 1804.04773 . doi : 10.1016/j.ipl.2015.10.002. S2CID  1180480.
12. Acar, Umut A.; Blelloch, Guy E .; Blumofe, Robert D. (2002). «Локальность данных кражи работы» (PDF) . Теория вычислительных систем . 35 (3): 321–347. CiteSeerX 10.1.1.19.3459 . doi :10.1007/s00224-002-1057-3. S2CID  10235838. 
13. Blumofe, Robert D.; Leiserson, Charles E. (1998). «Эффективное планирование многопоточных вычислений». SIAM J. Comput . 27 (1): 202–229. CiteSeerX 10.1.1.48.9822 . doi :10.1137/s0097539793259471. 
14. Дин, Сяонин; Ван, Кайбо; Гиббонс, Филлип Б.; Чжан, Сяодун (2012). BWS: Сбалансированное перехват работы для многоядерных процессоров с разделением времени (PDF) . EuroSys.
15. Blumofe, Robert D.; Papadopoulos, Dionisios (1998). The Performance of Work Stealing in Multiprogrammed Environments (технический отчет). Техасский университет в Остине , кафедра компьютерных наук. CiteSeerX 10.1.1.48.2247 . 
16. Арора, Нимар С.; Блюмофе, Роберт Д.; Плакстон, К. Грег (2001). «Планирование потоков для многопрограммных мультипроцессоров» (PDF) . Теория вычислительных систем . 34 (2): 115–144. doi :10.1007/s002240011004.
17. Чейз, Дэвид Р.; Лев, Йосеф (2005). Динамическая круговая очередь с кражей работы . Симптом ACM по параллелизму в алгоритмах и архитектурах. CiteSeerX 10.1.1.170.1097 . 
18. Blelloch, Guy E.; Gibbons, Phillip B.; Matias, Yossi (1999). «Доказуемо эффективное планирование для языков с мелкозернистым параллелизмом» (PDF) . Journal of the ACM . 46 (2): 281–321. CiteSeerX 10.1.1.48.8238 . doi :10.1145/301970.301974. S2CID  47102937.