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