WikiDer > Модель вилки и соединения - Википедия

Fork–join model - Wikipedia
Иллюстрация парадигмы fork-join, в которой три области программы допускают параллельное выполнение блоков разного цвета. Последовательное выполнение отображается вверху, а его эквивалентное выполнение fork – join находится внизу.

В параллельные вычисления, то модель fork – join - это способ установки и выполнения параллельных программ, так что выполнение разветвляется параллельно в обозначенных точках программы, чтобы «соединиться» (объединить) в следующей точке и возобновить последовательное выполнение. Параллельные секции могут разветвляться рекурсивно пока не будет достигнута определенная степень детализации задачи. Вилку – соединение можно рассматривать как параллельную шаблон дизайна.[1]:209 сл. Он был сформулирован еще в 1963 году.[2][3]

Рекурсивно вкладывая вычисления fork – join, можно получить параллельную версию разделяй и властвуй парадигма, выраженная следующим общим псевдокод:[4]

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

Примеры

Простая параллель Сортировка слиянием из CLRS представляет собой алгоритм разветвления-соединения.[5]

mergesort (A, lo, hi): если ло <привет: // хотя бы один элемент ввода        mid = ⌊lo + (привет - lo) / 2⌋ вилка mergesort (A, lo, mid) // обрабатываем (потенциально) параллельно с основной задачей        mergesort (A, середина, привет) // основная задача обрабатывает вторую рекурсию        присоединиться        слияние (А, вот, середина, привет)

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

Второй рекурсивный вызов не является ответвлением псевдокода выше; это сделано намеренно, так как разветвление задач может дорого обойтись. Если бы оба рекурсивных вызова были настроены как подзадачи, у основной задачи не было бы дополнительной работы, которую нужно было бы выполнить, прежде чем она будет заблокирована в присоединиться.[1]

Реализации

Реализации модели fork-join обычно разветвляются задачи, волокна или же легкие нити, а не "тяжеловес" на уровне операционной системы потоки или процессов, и используйте пул потоков для выполнения этих задач: примитив fork позволяет программисту указать потенциал параллелизм, который реализация затем отображает на фактическое параллельное выполнение.[1] Причина такого дизайна в том, что создание новых потоков приводит к слишком большим накладным расходам.[4]

Облегченные потоки, используемые в программировании fork-join, обычно имеют собственный планировщик (обычно работа воровство one), который отображает их в базовый пул потоков. Этот планировщик может быть намного проще, чем полнофункциональный, упреждающий планировщик операционной системы: поток общего назначения планировщики должен иметь дело с блокировкой для замки, но в парадигме fork – join потоки блокируются только в точке соединения.[4]

Fork – join - основная модель параллельного выполнения в OpenMP framework, хотя реализации OpenMP могут поддерживать или не поддерживать вложение параллельных разделов.[6] Это также поддерживается Параллелизм Java рамки,[7] то Библиотека параллельных задач для .NET,[8] и Intel Заправка строительных блоков (TBB).[1] В Силк язык программирования имеет поддержку на уровне языка для fork и join в форме порождать и синхронизировать ключевые слова,[4] или же cilk_spawn и cilk_sync в Силк Плюс.[1]

Смотрите также

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

  1. ^ а б c d е ж Майкл МакКул; Джеймс Рейндерс; Арка Робисон (2013). Структурированное параллельное программирование: шаблоны для эффективных вычислений. Эльзевир.
  2. ^ Мелвин Э. Конвей (1963). Дизайн многопроцессорной системы. Осень Присоединяйтесь к компьютерной конференции. С. 139–146. Дои:10.1145/1463822.1463838.
  3. ^ Найман, Линус; Лааксо, Микаэль (2016). «Заметки по истории развилки и соединения». IEEE Annals of the History of Computing. Компьютерное общество IEEE. 38 (3): 84–87. Дои:10.1109 / MAHC.2016.34.
  4. ^ а б c d Дуг Ли (2000). Фреймворк Java fork / join (PDF). Конференция ACM по Java.
  5. ^ Кормен, Томас Х.; Лейзерсон, Чарльз Э.; Ривест, Рональд Л.; Штейн, Клиффорд (2009) [1990]. Введение в алгоритмы (3-е изд.). MIT Press и McGraw-Hill. ISBN 0-262-03384-4.
  6. ^ Блэз Барни (12 июня 2013 г.). «OpenMP». Национальная лаборатория Лоуренса Ливермора. Получено 5 апреля 2014.
  7. ^ "Вилка / Присоединение". Учебники по Java. Получено 5 апреля 2014.
  8. ^ Даан Лейен; Вольфрам Шульте; Себастьян Буркхардт (2009). Дизайн библиотеки параллельных задач. OOPSLA.

внешняя ссылка