Модель разветвления-объединения

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

Путем рекурсивного вложения вычислений fork-join можно получить параллельную версию парадигмы « разделяй и властвуй» , выраженную следующим общим псевдокодом : ^{[ 4 ]}

solve(problem):
    if problem is small enough:
        solve problem directly (sequential algorithm)
    else:
        for part in subdivide(problem)
            fork subtask to solve(part)
        join all subtasks spawned in previous loop
        return combined results

Примеры

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

mergesort(A, lo, hi):
    if lo < hi:                     // at least one element of input
        mid = ⌊lo + (hi - lo) / 2⌋
        fork mergesort(A, lo, mid)  // process (potentially) in parallel with main task
        mergesort(A, mid, hi)       // main task handles second recursion
        join
        merge(A, lo, mid, hi)

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

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

Реализации

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

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

Форк-объединение — это основная модель параллельного выполнения в среде OpenMP , хотя реализации OpenMP могут поддерживать или не поддерживать вложенность параллельных разделов. ^{[ 6 ]} Он также поддерживается средой параллелизма Java , ^{[ 7 ]} библиотека параллельных задач для .NET, ^{[ 8 ]} Intel и строительные блоки Threading (TBB). ^{[ 1 ]} Язык программирования Cilk имеет поддержку fork и join на уровне языка в форме spawn и sync ключевые слова, ^{[ 4 ]} или cilk_spawn и cilk_sync в Силк Плюс . ^{[ 1 ]}

См. также

Ссылки

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

Внешние ссылки

Учебное пособие по планированию развилки: присоединение к параллелизму с кражей работы
Сортировка слиянием Fork-Join (Java) (на португальском языке)

[spp-1] Перейти обратно: ^а ^б ^с ^д ^и ^ж Майкл МакКул; Джеймс Рейндерс; Арч Робисон (2013). Структурированное параллельное программирование: шаблоны для эффективных вычислений . Эльзевир.

[2] Мелвин Э. Конвей (1963). Проектирование многопроцессорной системы . Осень Присоединяйтесь к компьютерной конференции. стр. 139–146. дои : 10.1145/1463822.1463838 .

[3] Найман, Лайнус; Лааксо, Микаэль (2016). «Заметки по истории форка и объединения». IEEE Анналы истории вычислений . 38 (3). Компьютерное общество IEEE: 84–87. дои : 10.1109/MAHC.2016.34 .

[lea-4] Перейти обратно: ^а ^б ^с ^д Дуг Ли (2000). Платформа разветвления/соединения Java (PDF) . Конференция ACM по Java.

[5] Кормен, Томас Х .; Лейзерсон, Чарльз Э .; Ривест, Рональд Л .; Стоун, Клиффорд (2009) [1990]. Введение в алгоритмы (3-е изд.). MIT Press и McGraw-Hill. п. 797. ИСБН 0-262-03384-4 .

[6] Блез Барни (12 июня 2013 г.). «ОпенМП» . Ливерморская национальная лаборатория Лоуренса . Проверено 5 апреля 2014 г.

[7] «Разветвление/Присоединение» . Учебники по Java . Проверено 5 апреля 2014 г.

[8] Даан Лейен; Вольфрам Шульте; Себастьян Буркхардт (2009). Проектирование библиотеки параллельных задач . УПСЛА .

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]