Кража работы - Work stealing

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

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

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

Идея кражи работы восходит к реализации Multilisp язык программирования и параллельная работа функциональное программирование языки в 1980-х.[2] Он используется в планировщике для Силк язык программирования,[3] то Ява структура вилки / соединения,[4] сеть Библиотека параллельных задач,[5] и Ржавчина Время выполнения Tokio.[6]

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

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

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

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

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

Графическое представление вычисления fork – join.

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

Алгоритм

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

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

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

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

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

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

Обратите внимание, что в правиле для порождать, Блюмофе и Лейзерсон предлагают, чтобы «родительский» поток выполнял свой новый поток, как если бы выполнял вызов функции (в C-подобной программе f (x); г (у);, вызов функции ж завершается перед вызовом грамм выполняется). Это называется «кражей продолжения», потому что продолжение функции могут быть украдены во время выполнения порожденного потока, и это алгоритм планирования, используемый в Силк Плюс.[7] Это не единственный способ осуществить кражу работы; альтернативная стратегия называется «воровство детей», и ее легче реализовать в качестве библиотека, без компилятор поддерживать.[7] Воровство детей используется Заправка строительных блоков, Параллельная библиотека задач Microsoft и OpenMP, хотя последний дает программисту контроль над тем, какая стратегия используется.[7]

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

Было предложено несколько вариантов кражи работы. В рандомизированный вариант, предложенный Блюмофе и Лейзерсоном, выполняет параллельное вычисление в ожидаемое время на процессоры; здесь, это работай, или количество времени, необходимое для выполнения вычислений на последовательном компьютере, и это охватывать, количество времени, необходимое для бесконечно параллельной машины.[заметка 2] Это означает, что, в ожидании, требуемое время - не более чем постоянный коэффициент, умноженный на теоретический минимум.[2] Однако время выполнения (в частности, количество выполненных перехватов) может быть экспоненциальным в зависимости от в худшем случае.[9] Локализованный вариант, в котором процессор пытается украсть свою работу, когда он свободен, также был проанализирован теоретически и практически.[10][11]

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

Вычисление, запланированное версией кражи работы Блюмофе – Лейзерсона, использует пространство стека, если были ли стеком одно и то же вычисление на одном процессоре,[2] соответствует собственному более раннему определению эффективности использования пространства авторами.[12] Эта граница требует продолжения кражи; в планировщике кражи дочерних элементов это не выполняется, как видно из следующего примера:[7]

за я = 0 к n: вилка f (i)присоединиться

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

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

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

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

куда псредний - это среднее количество процессоров, выделенных для вычислений планировщиком ОС за время выполнения вычислений.[15]Планировщик работы с мультипрограммированием отличается от традиционной версии в двух отношениях:

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

Попытки улучшить мультипрограммную работу Stealer были сосредоточены на местонахождение тайника вопросы[11] и улучшенные структуры данных очереди.[16]

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

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

Примечания

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

Рекомендации

  1. ^ а б Чен, Шимин; Гиббонс, Филип Б .; Козуч, Михаил; Лясковитис, Василиос; Айламаки, Анастасия; Blelloch, Guy E .; Фальсафи, Бабак; Фикс, Лимор; Хардавеллас, Никос; Моури, Тодд С.; Вилкерсон, Крис (2007). Планирование потоков для конструктивного совместного использования кеша на CMP (PDF). Proc. ACM Symp. по параллельным алгоритмам и архитектурам. С. 105–115.
  2. ^ а б c d е ж Блюмофе, Роберт Д.; Лейзерсон, Чарльз Э. (1999). «Планирование многопоточных вычислений путем кражи работы» (PDF). J ACM. 46 (5): 720–748. Дои:10.1145/324133.324234.
  3. ^ Блюмофе, Роберт Д.; Joerg, Christopher F .; Kuszmaul, Bradley C .; Leiserson, Charles E .; Randall, Keith H .; Чжоу, Юли (1996). «Cilk: эффективная многопоточная система выполнения». Журнал параллельных и распределенных вычислений. 37 (1): 55–69. Дои:10.1006 / jpdc.1996.0107.
  4. ^ Дуг Ли (2000). Фреймворк Java fork / join (PDF). ACM Conf. на 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. ^ а б c d е Робисон, Арка (15 января 2014 г.). Учебник по планированию распараллеливания форк – соединения с использованием кражи работы (PDF) (Технический отчет). ISO / IEC JTC 1 / SC 22 / WG 21 - The C ++ Комитет по стандартам. N3872.
  8. ^ Хальперн, Пабло (24 сентября 2012 г.). Строгий параллелизм разветвления и соединения (PDF) (Технический отчет). ISO / IEC JTC 1 / SC 22 / WG 21 - The C ++ Комитет по стандартам. N3409 = 12-0099.
  9. ^ Лейзерсон, Чарльз Э.; Schardl, Tao B .; Суксомпонг, Варут (2016). «Верхние границы количества краж деревьев с корнями». Теория вычислительных систем. 58 (2): 223–240. arXiv:1706.08219. Дои:10.1007 / s00224-015-9613-9.
  10. ^ Суксомпонг, Варут; Лейзерсон, Чарльз Э.; Шардл, Тао Б. (2016). «Об эффективности локализованного хищения работ». Письма об обработке информации. 116 (2): 100–106. arXiv:1804.04773. Дои:10.1016 / j.ipl.2015.10.002.
  11. ^ а б Acar, Umut A .; Блеллох, Гай Э.; Блюмофе, Роберт Д. (2002). "Местоположение данных кражи работы" (PDF). Теория вычислительных систем. 35 (3): 321–347. CiteSeerX  10.1.1.19.3459. Дои:10.1007 / s00224-002-1057-3.
  12. ^ Блюмофе, Роберт Д.; Лейзерсон, Чарльз Э. (1998). «Экономичное планирование многопоточных вычислений». SIAM J. Comput. 27 (1): 202–229. CiteSeerX  10.1.1.48.9822. Дои:10.1137 / s0097539793259471.
  13. ^ Дин, Сяонин; Ван, Кайбо; Гиббонс, Филип Б .; Чжан, Сяодун (2012). BWS: Сбалансированное кража работы для многоядерных компьютеров с разделением времени (PDF). EuroSys.
  14. ^ Блюмофе, Роберт Д.; Пападопулос, Дионисиос (1998). Производительность кражи работы в многопрограммных средах (Технический отчет). Техасский университет в Остине, Департамент компьютерных наук. CiteSeerX  10.1.1.48.2247.
  15. ^ Arora, Nimar S .; Блюмофе, Роберт Д.; Плэкстон, К. Грег (2001). «Планирование потоков для многопрограммных мультипроцессоров» (PDF). Теория вычислительных систем. 34 (2): 115–144. Дои:10.1007 / s002240011004.
  16. ^ Чейз, Дэвид Р .; Лев, Йосеф (2005). Динамический круговой рабочий-кража Deque. ACM Symp. по параллелизму в алгоритмах и архитектурах. CiteSeerX  10.1.1.170.1097.
  17. ^ Blelloch, Guy E .; Гиббонс, Филип Б .; Матиас, Йосси (1999). «Доказанно эффективное планирование для языков с мелкозернистым параллелизмом» (PDF). Журнал ACM. 46 (2): 281–321. CiteSeerX  10.1.1.48.8238. Дои:10.1145/301970.301974.