Fork - Join

Estilo de paralelización donde:

1. El cómputo (task) es partido en sub-cómputos menores (subtasks).
2. Los resultados de estos se unen (join) para construir la solución al cómputo inicial.

• Partir el cómputo se realiza en general de forma recursiva:
  • los sub-cómputos son independientes → el cómputo se puede realizar en paralelo.
• Las sub-tareas se pueden crear en cualquier momento de la ejecución de la tarea.
• Las tareas no deben bloquearse, excepto para esperar el final de las subtareas.

Diagrama Fork-Join

Propiedades

• Modelo de Concurrencia sin condiciones de carrera (Race Conditions)
  • Se genera cuando se depende del orden del procesamiento.
• Los programas Fork-Join son determinísticos, los threads están aislados.
  • El programa produce el mismo resultado independientemente de las diferencias de velocidad de los threads.
• Performance: en el caso ideal $t_{secuencial}$ / $N_{threads}$
• Desventaja: requiere que las unidades de trabajo sean aisladas.

Work Stealing

Algoritmo usado para hacer scheduling de tareas entre threads.

Worker threads inactivos roban trabajo a threads ocupados, para realizar balanceo de carga.

• Cada thread tiene su propia cola de dos extremos (deque) donde almacena las tareas listar por ejecutar.
• Cuando un thread termina la ejecución de una tarea, coloca las subtareas creadas al final de la cola.
• Luego, toma la siguiente tarea para ser ejecutada del final de la cola.