В параллельных вычислениях модель разветвления-объединения представляет собой способ настройки и выполнения параллельных программ, при котором выполнение разветвляется параллельно в определенных точках программы, чтобы «присоединиться» (слиться) в последующей точке и возобновить последовательное выполнение. Параллельные секции могут рекурсивно разветвляться до тех пор, пока не будет достигнута определенная степень детализации задачи. Форк-объединение можно считать шаблоном параллельного проектирования . [1] : 209 и сл. Он был сформулирован еще в 1963 году. [2] [3]
Путем рекурсивного вложения вычислений разветвления и соединения можно получить параллельную версию парадигмы «разделяй и властвуй» , выраженную следующим общим псевдокодом : [4]
решить(проблему) : если проблема достаточно мала: решить задачу напрямую (последовательный алгоритм) else : для части в подзадаче subdivide (problem) fork для решения (части) объединить все подзадачи, порожденные в предыдущем цикле, вернуть объединенные результаты
Простой вариант параллельного слияния CLRS представляет собой алгоритм разветвления-соединения. [5]
mergesort(A, lo, hi): if lo < hi: // хотя бы один элемент ввода середина = ⌊lo + (привет - лоу) / 2⌋ fork mergesort(A, lo, Mid) // обработка (потенциально) параллельно с основной задачей mergesort(A, Mid, hi) // основная задача обрабатывает второе рекурсивное соединение слияние (А, вот, середина, привет)
Первый рекурсивный вызов является «разветвленным», что означает, что его выполнение может выполняться параллельно (в отдельном потоке) со следующей частью функции, вплоть до соединения, которое вызывает синхронизацию всех потоков. Хотя соединение может выглядеть как барьер , оно отличается тем, что потоки продолжают работать после барьера, тогда как после соединения продолжает работать только один поток. [1] : 88
Второй рекурсивный вызов не является ответвлением приведенного выше псевдокода; это сделано намеренно, поскольку разветвление задач может потребовать дополнительных затрат. Если бы оба рекурсивных вызова были настроены как подзадачи, основной задаче не пришлось бы выполнять никакой дополнительной работы, прежде чем она была бы заблокирована при соединении . [1]
Реализации модели fork-join обычно разветвляют задачи , волокна или легкие потоки , а не «тяжеловесные» потоки или процессы уровня операционной системы , и используют пул потоков для выполнения этих задач: примитив fork позволяет программисту указать потенциальный параллелизм. , который затем реализация сопоставляет с фактическим параллельным выполнением. [1] Причиной такой конструкции является то, что создание новых потоков обычно приводит к слишком большим накладным расходам. [4]
Облегченные потоки, используемые в программировании разветвлений и объединений, обычно имеют собственный планировщик (обычно планировщик, перехватывающий работу ), который сопоставляет их с базовым пулом потоков. Этот планировщик может быть намного проще, чем полнофункциональный вытесняющий планировщик операционной системы: планировщики потоков общего назначения должны иметь дело с блокировкой блокировок , но в парадигме разветвления-соединения потоки блокируются только в точке соединения. [4]
Форк-объединение — это основная модель параллельного выполнения в среде OpenMP , хотя реализации OpenMP могут поддерживать или не поддерживать вложенность параллельных разделов. [6] Он также поддерживается средой параллелизма Java , [7] библиотекой параллельных задач для .NET, [8] и блоками Intel Threading Building Blocks (TBB). [1] Язык программирования Cilk имеет поддержку fork и join на уровне языка в виде ключевых слов spawnand sync, [4] или cilk_spawnand cilk_syncв Cilk Plus . [1]
