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

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

В планировщике захвата работы каждый процессор в компьютерной системе имеет очередь рабочих элементов (вычислительных задач, потоков) для выполнения. Каждый рабочий элемент состоит из серии инструкций, которые должны быть выполнены последовательно, но в ходе своего выполнения рабочий элемент может также порождать новые рабочие элементы, которые могут быть выполнены параллельно с его другой работой. Эти новые элементы изначально помещаются в очередь процессора, выполняющего рабочий элемент. Когда процессору не хватает работы, он просматривает очереди других процессоров и «крадет» их рабочие элементы. По сути, захват работы распределяет работу по планированию по простаивающим процессорам, и пока все процессоры имеют работу, никаких накладных расходов на планирование не происходит. [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] Т 1 / П + О ( Т ∞ ) {\displaystyle T_{1}/P+O(T_{\infty })} П {\displaystyle P} Т 1 {\displaystyle T_{1}} Т ∞ {\displaystyle T_{\infty}} Т ∞ {\displaystyle T_{\infty}}

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

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

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

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

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

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

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

О ( Т 1 П а в г + Т ∞ П П а в г ) , {\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. ^ ab 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. ^ abcdef 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. ^ abcde Робинсон, Арч (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. ^ ab 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. 
Взято с "https://en.wikipedia.org/w/index.php?title=Workstealing&oldid=1216652959"