Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску

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

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

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

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

Модель исполнения [ править ]

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

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

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

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

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

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

Алгоритм [ править ]

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

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

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

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

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

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

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

Эффективность [ править ]

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

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

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

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

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

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

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

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

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

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

Попытки улучшить работу с мультипрограммным стилером были сосредоточены на проблемах локализации кэша [11] и улучшенных структурах данных очереди. [16]

Альтернативы [ править ]

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

Заметки [ править ]

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

Ссылки [ править ]

  1. ^ a b Чен, Шимин; Гиббонс, Филип Б .; Козуч, Михаил; Лясковитис, Василиос; Айламаки, Анастасия; Blelloch, Guy E .; Фальсафи, Бабак; Фикс, Лимор; Хардавеллас, Никос; Моури, Тодд С.; Вилкерсон, Крис (2007). Планирование потоков для конструктивного совместного использования кеша на CMP (PDF) . Proc. ACM Symp. по параллельным алгоритмам и архитектурам. С. 105–115.
  2. ^ a b c d e е Блюмофе, Роберт Д.; Лейзерсон, Чарльз Э. (1999). «Планирование многопоточных вычислений путем кражи работы» (PDF) . J ACM . 46 (5): 720–748. DOI : 10.1145 / 324133.324234 .
  3. ^ Блюмофе, Роберт Д .; Joerg, Christopher F .; Kuszmaul, Bradley C .; Leiserson, Charles E .; Randall, Keith H .; Чжоу, Юли (1996). «Cilk: эффективная многопоточная система выполнения». Журнал параллельных и распределенных вычислений . 37 (1): 55–69. DOI : 10,1006 / jpdc.1996.0107 .
  4. ^ Дуг Ли (2000). Платформа Java fork / join (PDF) . ACM Conf. на Java.
  5. ^ Leijen, Даан; Шульте, Вольфрам; Буркхардт, Себастьян (2009). «Дизайн параллельной библиотеки задач». Уведомления ACM SIGPLAN . 44 (10): 227. CiteSeerX 10.1.1.146.4197 . DOI : 10.1145 / 1639949.1640106 . 
  6. ^ «Что такое Токио? · Токио» . tokio.rs . Проверено 27 мая 2020 .
  7. ^ a b c d e Робисон, Arch (15 января 2014 г.). Учебник по планированию параллелизма форк-объединений с использованием кражи работы (PDF) (Технический отчет). ISO / IEC JTC 1 / SC 22 / WG 21 - Комитет по стандартам C ++ . N3872.
  8. ↑ Halpern, Pablo (24 сентября 2012 г.). Строгий параллелизм форк – соединения (PDF) (Технический отчет). ISO / IEC JTC 1 / SC 22 / WG 21 - Комитет по стандартам C ++ . N3409 = 12-0099.
  9. ^ Leiserson, Чарльз Э .; Schardl, Tao B .; Суксомпонг, Варут (2016). «Верхние границы количества краж деревьев с укоренившимися деревьями». Теория вычислительных систем . 58 (2): 223–240. arXiv : 1706.08219 . DOI : 10.1007 / s00224-015-9613-9 .
  10. ^ Суксомпонг, Варут; Лейзерсон, Чарльз Э .; Шардл, Тао Б. (2016). «Об эффективности локализованного хищения работ». Письма об обработке информации . 116 (2): 100–106. arXiv : 1804.04773 . DOI : 10.1016 / j.ipl.2015.10.002 .
  11. ^ a b Acar, Umut A .; Blelloch, Guy E .; Блюмофе, Роберт Д. (2002). "Локализация данных о краже работы" (PDF) . Теория вычислительных систем . 35 (3): 321–347. CiteSeerX 10.1.1.19.3459 . DOI : 10.1007 / s00224-002-1057-3 .  
  12. ^ Блюмофе, Роберт Д .; Лейзерсон, Чарльз Э. (1998). «Экономичное планирование многопоточных вычислений». SIAM J. Comput . 27 (1): 202–229. CiteSeerX 10.1.1.48.9822 . DOI : 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. DOI : 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 . DOI : 10.1145 / 301970.301974 .