Modelo Fork Join Flashcards
¿Qué es el modelo Fork Join?
Es un estilo de paralelización donde el cómputo (task) es partido (fork) en sub-cómputos (subtasks). Los resultados de estos se unen (join) para construir la solución al cómputo inicial.
¿Cual es la condición de carrera del Modelo Fork Join?
Es un modelo sin condiciones de carrera.
¿Cómo funcionan las tareas en el Modelo Fork Join?
- Se divide la tarea en subcómputos siendo éstos independientes (de forma recursiva)
- 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.
¿Qué tipo de modelo es el Modelo Fork Join?
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.
¿Cuales son las ventajas del modelo Fork Join?
- Reutiliza los threads que crea.
- Paralelismo
- Es facil de programar
- El resultado final no varía en cada corrida por la race condition
- Escalable: Aprovecha todos los cpus y núcleos, lo cual lo hace escalable
¿Cuales son las desventajas del Modelo Fork Join?
- Requiere que las unidades de trabajo (tareas) sean aisladas.
- Si las tareas no están bien equilibradas o las subtareas son muy pequeñas, puede sobre cargarse la división y unión de las tareas
- Manejo de excepciones
A los threads se le van asignando las subtareas (algunas más grandes que otras).
Puede o no pasar que el caso ideal sea el de dividir las tareas por threads o el de fork-join.
¿Qué es el Work Stealing?
Es un algoritmo usado para hacer scheduling de tareas entre threads.
¿Cómo funciona el Work Stealing?
Worker threads inactivos roban trabajo a threads ocupados, para realizar balanceo de carga.
1. Cada thread tiene su propia cola de dos extremos (deque, double ended queue) donde almacena las tareas listas por ejecutar.
2. Cuando un thread termina la ejecución de una tarea coloca las subtareas creadas al final de la cola.
3. Luego, toma la siguiente tarea para ser ejecutada.
4. Si la cola está vacía, y el thread no tiene más trabajo, tratar de robar tareas del inicio de una cola de otro thread (random).
¿Cuales son las ventajas del Work Stealing?
- Cada hilo tiene su propia cola, por lo que no necesitan coordinarse constantemente para decidir qué tarea ejecutar.
- La sincronización entre hilos suele ser costosa, ya que implica locks o primitivas atómicas para evitar condiciones de carrera. En work stealing, la mayoría de las operaciones en la cola de cada hilo son locales (sin necesidad de sincronización).
¿Qué es MapReduce?
MapReduce es un modelo de programación y una implementación asociada para procesar y generar data sets de gran tamaño. Los usuarios especifican una función map que va a procesar un par key/value para generar un set de pares key/values intermedios, y una función de reducción que va a mergear todos los valores intermedios asociados a la misma clave intermedia.Es un modelo de programación y una implementación asociadad para procesar y generar datasets de gran tamaño.
¿Qué es Rayon?
Rayon es una biblioteca de paralelismo de datos para Rust. Es extremadamente liviana y facilita la conversión de un cálculo secuencial en uno paralelo. También garantiza la libertad de las carreras de datos.
¿Qué es Dremel?
Sistema de consultas en tiempo casi real, expuesto al público como BigQuery
