En la informática paralela , el modelo fork-join es una forma de configurar y ejecutar programas paralelos, de modo que la ejecución se bifurca en paralelo en puntos designados del programa, para "unirse" (fusionarse) en un punto posterior y reanudar la ejecución secuencial. Las secciones paralelas pueden bifurcarse de forma recursiva hasta alcanzar una determinada granularidad de la tarea. La unión entre horquillas puede considerarse un patrón de diseño paralelo . [1] : 209 y sigs. Fue formulado ya en 1963. [2] [3]
Al anidar recursivamente los cálculos de bifurcación y unión, se obtiene una versión paralela del paradigma de divide y vencerás , expresado mediante el siguiente pseudocódigo genérico : [4]
resolver(problema) : si el problema es lo suficientemente pequeño: resolver el problema directamente (algoritmo secuencial) else : para parte en subdividir (problema), bifurcar la subtarea para resolver (parte) , unir todas las subtareas generadas en el bucle anterior y devolver resultados combinados.
El tipo de combinación paralela simple de CLRS es un algoritmo de unión-bifurcación. [5]
mergesort(A, lo, hola): si lo < hola: // al menos un elemento de entrada medio = ⌊lo + (hola - bajo) / 2⌋ fork mergesort(A, lo, mid) // procesa (potencialmente) en paralelo con la tarea principal mergesort(A, mid, hi) // la tarea principal maneja la segunda unión recursiva fusionar (A, bajo, medio, hola)
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 subprocesos seguirán funcionando después de una barrera, mientras que después de una unión solo continúa un subproceso. [1] : 88
La segunda llamada recursiva no es una bifurcación del pseudocódigo anterior; Esto es intencional, ya que bifurcar tareas puede resultar costosa. 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 normalmente bifurcarán tareas , fibras o subprocesos livianos , no subprocesos o procesos "pesados" a nivel del sistema operativo , y utilizarán un grupo de subprocesos para ejecutar estas tareas: la primitiva de bifurcación permite al programador especificar un paralelismo potencial . , que la implementación luego 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 generar demasiada sobrecarga. [4]
Los subprocesos livianos utilizados en la programación fork-join generalmente tendrán su propio programador (generalmente uno de robo de trabajo ) que los asigna al grupo de subprocesos subyacente. Este programador puede ser mucho más simple que un programador de sistema operativo preventivo y con todas las funciones : los programadores 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 admitir o no el anidamiento de secciones paralelas. [6] También es compatible con el marco de concurrencia de Java , [7] la biblioteca paralela de tareas para .NET, [8] y Threading Building Blocks (TBB) de Intel . [1] El lenguaje de programación Cilk tiene soporte a nivel de lenguaje para fork y join, en forma de palabras clave spawny sync, [4] o cilk_spawny cilk_syncen Cilk Plus . [1]
