Кража работы

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

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

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

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

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

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

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

function f(a, b):
    c ← fork g(a)
    d ← h(b)
    join
    return c + d

function g(a):
    return a × 2

function h(a):
    b ← fork g(a)
    c ← a + 1
    join
    return b + c

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

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

Алгоритм

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

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

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

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

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

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

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

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

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

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

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

for i = 0 to n:
    fork f(i)
join

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

Мультипрограммный вариант

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

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

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

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

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

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

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

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

Примечания

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

Ссылки

^ Jump up to: ^а ^б Чен, Шимин; Гиббонс, Филипп Б.; Козуч, Михаил; Лиасковитис, Василейос; Айламаки, Анастасия; Блеллок, Гай Э.; Фальсафи, Бабак; Фикс, Лимор; Хардавеллас, Никос; Моури, Тодд С.; Вилкерсон, Крис (2007). Планирование потоков для конструктивного совместного использования кэша на CMP (PDF) . Учеб. Симптом ACM. по параллельным алгоритмам и архитектурам. стр. 105–115.
^ Jump up to: ^а ^б ^с ^д ^и ^ж Блюмоф, Роберт Д.; Лейзерсон, Чарльз Э. (1999). «Планирование многопоточных вычислений путем кражи работы» (PDF) . Дж АСМ . 46 (5): 720–748. дои : 10.1145/324133.324234 . S2CID 5428476 .
^ Блюмоф, Роберт Д.; Йорг, Кристофер Ф.; Кушмаул, Брэдли С.; Лейзерсон, Чарльз Э.; Рэндалл, Кейт Х.; Чжоу, Юли (1996). «Cilk: эффективная многопоточная система выполнения» . Журнал параллельных и распределенных вычислений . 37 (1): 55–69. дои : 10.1006/jpdc.1996.0107 .
^ Дуг Ли (2000). Платформа разветвления/соединения Java (PDF) . Конференция АКМ. на Яве.
^ Лейен, Даан; Шульте, Вольфрам; Буркхардт, Себастьян (2009). «Проектирование библиотеки параллельных задач». Уведомления ACM SIGPLAN . 44 (10): 227. CiteSeerX 10.1.1.146.4197 . дои : 10.1145/1639949.1640106 .
^ «Что такое Токио? · Токио» . tokio.rs . Проверено 27 мая 2020 г.
^ Криль, Пол (08 января 2021 г.). «Среда выполнения Tokio Rust достигла статуса 1.0» . Инфомир . Проверено 26 декабря 2021 г.
^ Jump up to: ^а ^б ^с ^д ^и Робисон, Арч (15 января 2014 г.). Учебное пособие по планированию параллелизма разветвлений и объединений с кражей работы (PDF) (технический отчет). ISO/IEC JTC 1/SC 22 /WG 21 — Комитет по стандартизации C++ . Н3872.
^ Хальперн, Пабло (24 сентября 2012 г.). Строгий параллелизм разветвлений и объединений (PDF) (Технический отчет). ISO/IEC JTC 1/SC 22 /WG 21 — Комитет по стандартам C++ . N3409=12-0099.
^ Лейзерсон, Чарльз Э .; Шардл, Тао Б.; Суксомпонг, Варут (2016). «Верхние границы количества краж в деревьях с корнями». Теория вычислительных систем . 58 (2): 223–240. arXiv : 1706.08219 . дои : 10.1007/s00224-015-9613-9 . S2CID 424692 .
^ Суксомпонг, Варут; Лейзерсон, Чарльз Э .; Шардл, Тао Б. (2016). «Об эффективности хищения локализованных работ». Письма об обработке информации . 116 (2): 100–106. arXiv : 1804.04773 . дои : 10.1016/j.ipl.2015.10.002 . S2CID 1180480 .
^ Jump up to: ^а ^б Ачар, Умут А.; Блеллох, Гай Э .; Блюмофе, Роберт Д. (2002). «Локализация данных при краже работы» (PDF) . Теория вычислительных систем . 35 (3): 321–347. CiteSeerX 10.1.1.19.3459 . дои : 10.1007/s00224-002-1057-3 . S2CID 10235838 .
^ Блюмоф, Роберт Д.; Лейзерсон, Чарльз Э. (1998). «Экономичное планирование многопоточных вычислений». СИАМ Дж. Компьютер . 27 (1): 202–229. CiteSeerX 10.1.1.48.9822 . дои : 10.1137/s0097539793259471 .
^ Дин, Сяонин; Ван, Кайбо; Гиббонс, Филипп Б.; Чжан, Сяодун (2012). BWS: Сбалансированное перехват работы для многоядерных процессоров с разделением времени (PDF) . ЕвроСис.
^ Блюмоф, Роберт Д.; Пападопулос, Дионисиос (1998). Производительность перехвата работы в многопрограммных средах (технический отчет). Техасский университет в Остине , факультет компьютерных наук. CiteSeerX 10.1.1.48.2247 .
^ Арора, Нимар С.; Блюмоф, Роберт Д.; Плакстон, К. Грег (2001). «Планирование потоков для многопрограммных мультипроцессоров» (PDF) . Теория вычислительных систем . 34 (2): 115–144. дои : 10.1007/s002240011004 .
^ Чейз, Дэвид Р.; Лев, Йосеф (2005). Динамическая круговая дека с кражей работы . ACM симп. о параллелизме в алгоритмах и архитектурах. CiteSeerX 10.1.1.170.1097 .
^ Блеллок, Гай Э.; Гиббонс, Филипп Б.; Матиас, Йоси (1999). «Доказуемо эффективное планирование для языков с детальным параллелизмом» (PDF) . Журнал АКМ . 46 (2): 281–321. CiteSeerX 10.1.1.48.8238 . дои : 10.1145/301970.301974 . S2CID 47102937 .

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

[11] см . в анализе параллельных алгоритмов . Определения

[dfs-1] Jump up to: ^а ^б Чен, Шимин; Гиббонс, Филипп Б.; Козуч, Михаил; Лиасковитис, Василейос; Айламаки, Анастасия; Блеллок, Гай Э.; Фальсафи, Бабак; Фикс, Лимор; Хардавеллас, Никос; Моури, Тодд С.; Вилкерсон, Крис (2007). Планирование потоков для конструктивного совместного использования кэша на CMP (PDF) . Учеб. Симптом ACM. по параллельным алгоритмам и архитектурам. стр. 105–115.

[jacm-2] Jump up to: ^а ^б ^с ^д ^и ^ж Блюмоф, Роберт Д.; Лейзерсон, Чарльз Э. (1999). «Планирование многопоточных вычислений путем кражи работы» (PDF) . Дж АСМ . 46 (5): 720–748. дои : 10.1145/324133.324234 . S2CID 5428476 .

[3] Блюмоф, Роберт Д.; Йорг, Кристофер Ф.; Кушмаул, Брэдли С.; Лейзерсон, Чарльз Э.; Рэндалл, Кейт Х.; Чжоу, Юли (1996). «Cilk: эффективная многопоточная система выполнения» . Журнал параллельных и распределенных вычислений . 37 (1): 55–69. дои : 10.1006/jpdc.1996.0107 .

[lea-4] Дуг Ли (2000). Платформа разветвления/соединения Java (PDF) . Конференция АКМ. на Яве.

[5] Лейен, Даан; Шульте, Вольфрам; Буркхардт, Себастьян (2009). «Проектирование библиотеки параллельных задач». Уведомления ACM SIGPLAN . 44 (10): 227. CiteSeerX 10.1.1.146.4197 . дои : 10.1145/1639949.1640106 .

[6] «Что такое Токио? · Токио» . tokio.rs . Проверено 27 мая 2020 г.

[7] Криль, Пол (08 января 2021 г.). «Среда выполнения Tokio Rust достигла статуса 1.0» . Инфомир . Проверено 26 декабря 2021 г.

[primer-8] Jump up to: ^а ^б ^с ^д ^и Робисон, Арч (15 января 2014 г.). Учебное пособие по планированию параллелизма разветвлений и объединений с кражей работы (PDF) (технический отчет). ISO/IEC JTC 1/SC 22 /WG 21 — Комитет по стандартизации C++ . Н3872.

[9] Хальперн, Пабло (24 сентября 2012 г.). Строгий параллелизм разветвлений и объединений (PDF) (Технический отчет). ISO/IEC JTC 1/SC 22 /WG 21 — Комитет по стандартам C++ . N3409=12-0099.

[12] Лейзерсон, Чарльз Э .; Шардл, Тао Б.; Суксомпонг, Варут (2016). «Верхние границы количества краж в деревьях с корнями». Теория вычислительных систем . 58 (2): 223–240. arXiv : 1706.08219 . дои : 10.1007/s00224-015-9613-9 . S2CID 424692 .

[13] Суксомпонг, Варут; Лейзерсон, Чарльз Э .; Шардл, Тао Б. (2016). «Об эффективности хищения локализованных работ». Письма об обработке информации . 116 (2): 100–106. arXiv : 1804.04773 . дои : 10.1016/j.ipl.2015.10.002 . S2CID 1180480 .

[local-14] Jump up to: ^а ^б Ачар, Умут А.; Блеллох, Гай Э .; Блюмофе, Роберт Д. (2002). «Локализация данных при краже работы» (PDF) . Теория вычислительных систем . 35 (3): 321–347. CiteSeerX 10.1.1.19.3459 . дои : 10.1007/s00224-002-1057-3 . S2CID 10235838 .

[15] Блюмоф, Роберт Д.; Лейзерсон, Чарльз Э. (1998). «Экономичное планирование многопоточных вычислений». СИАМ Дж. Компьютер . 27 (1): 202–229. CiteSeerX 10.1.1.48.9822 . дои : 10.1137/s0097539793259471 .

[16] Дин, Сяонин; Ван, Кайбо; Гиббонс, Филипп Б.; Чжан, Сяодун (2012). BWS: Сбалансированное перехват работы для многоядерных процессоров с разделением времени (PDF) . ЕвроСис.

[17] Блюмоф, Роберт Д.; Пападопулос, Дионисиос (1998). Производительность перехвата работы в многопрограммных средах (технический отчет). Техасский университет в Остине , факультет компьютерных наук. CiteSeerX 10.1.1.48.2247 .

[arora-18] Арора, Нимар С.; Блюмоф, Роберт Д.; Плакстон, К. Грег (2001). «Планирование потоков для многопрограммных мультипроцессоров» (PDF) . Теория вычислительных систем . 34 (2): 115–144. дои : 10.1007/s002240011004 .

[19] Чейз, Дэвид Р.; Лев, Йосеф (2005). Динамическая круговая дека с кражей работы . ACM симп. о параллелизме в алгоритмах и архитектурах. CiteSeerX 10.1.1.170.1097 .

[20] Блеллок, Гай Э.; Гиббонс, Филипп Б.; Матиас, Йоси (1999). «Доказуемо эффективное планирование для языков с детальным параллелизмом» (PDF) . Журнал АКМ . 46 (2): 281–321. CiteSeerX 10.1.1.48.8238 . дои : 10.1145/301970.301974 . S2CID 47102937 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[примечание 1]

[примечание 2]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]