En computación paralela , el modelo fork-join es una forma de configurar y ejecutar programas paralelos, de modo que la ejecución se bifurque en paralelo en puntos designados en el programa, para "unirse" (fusionarse) en un punto posterior y reanudar la ejecución secuencial. Las secciones paralelas pueden bifurcarse recursivamente hasta que se alcance una determinada granularidad de tarea. Fork-join puede considerarse un patrón de diseño paralelo . [1] : 209 y siguientes. Fue formulado ya en 1963. [2] [3]
Al anidar cálculos de bifurcación y unión de forma recursiva, se obtiene una versión paralela del paradigma de dividir y vencer , expresado por el siguiente pseudocódigo genérico : [4]
solve(problema) : si el problema es suficientemente pequeño: Resolver el problema directamente (algoritmo secuencial) de lo contrario : para la parte en subdividir (problema) bifurcar la subtarea a resolver (parte) unir todas las subtareas generadas en el bucle anterior devolver resultados combinados
La simple ordenación por fusión paralela de CLRS es un algoritmo de bifurcación-unión. [5]
mergesort(A, lo, hi): si lo < hi: // al menos un elemento de entrada medio = ⌊lo + (hola - bajo) / 2⌋ fork mergesort(A, lo, mid) // procesar (potencialmente) en paralelo con la tarea principal mergesort(A, mid, hi) // la tarea principal maneja la segunda recursión join fusionar(A, bajo, medio, alto)
La primera llamada recursiva se "bifurca", lo que significa que su ejecución puede ejecutarse en paralelo (en un hilo separado) con la siguiente parte de la función, hasta la unión que hace que todos los hilos se sincronicen. Si bien la unión puede parecer una barrera , es diferente porque los hilos continuarán funcionando después de una barrera, mientras que después de una unión solo continúa un hilo. [1] : 88
La segunda llamada recursiva no es una bifurcación en el pseudocódigo anterior; esto es intencional, ya que la bifurcación de tareas puede tener un costo. Si ambas llamadas recursivas se configuraran como subtareas, la tarea principal no tendría ningún trabajo adicional que realizar antes de ser bloqueada en la unión . [1]
Las implementaciones del modelo fork-join generalmente bifurcan tareas , fibras o subprocesos livianos , no subprocesos o procesos "pesados" a nivel de sistema operativo , y utilizan un grupo de subprocesos para ejecutar estas tareas: la primitiva fork permite al programador especificar un paralelismo potencial , que luego la implementación asigna a la ejecución paralela real. [1] La razón de este diseño es que la creación de nuevos subprocesos tiende a resultar en demasiada sobrecarga. [4]
Los subprocesos livianos que se usan en la programación de bifurcación y unión generalmente tienen su propio planificador (que generalmente roba trabajo ) que los asigna al grupo de subprocesos subyacente. Este planificador puede ser mucho más simple que un planificador de sistema operativo con todas las funciones y preemptivo : los planificadores de subprocesos de propósito general deben lidiar con el bloqueo de bloqueos , pero en el paradigma de bifurcación y unión, los subprocesos solo se bloquean en el punto de unión. [4]
Fork–join es el modelo principal de ejecución paralela en el marco OpenMP , aunque las implementaciones de OpenMP pueden o no admitir la anidación de secciones paralelas. [6] También es compatible con el marco de concurrencia de Java , [7] la biblioteca Task Parallel Library para .NET, [8] y los bloques de construcción de subprocesos (TBB) de Intel . [1] El lenguaje de programación Cilk tiene soporte a nivel de lenguaje para fork y join, en la forma de las palabras claves spawnand sync, [4] o cilk_spawnand cilk_syncen Cilk Plus . [1]
