Los conceptos de equilibrio de carga y programación están estrechamente relacionados y, a menudo, se usan con el mismo significado.
El objetivo de la estrategia de programación es maximizar el rendimiento de un sistema paralelo, mediante la transferencia de tareas de procesadores ocupados a otros procesadores que están menos ocupados o incluso inactivos. Una estrategia de programación implica dos decisiones importantes:
- determinar tareas que se pueden ejecutar en paralelo, y
- determinar dónde ejecutar las tareas paralelas.
Normalmente, se toma una decisión con base en el conocimiento previo o en la información recopilada durante la ejecución.
- ¿Un programador autodidacta necesita aprender materias como algoritmos y cálculo? ¿Por qué?
- ¿Cuál es el mejor algoritmo de aprendizaje automático sin supervisión para la segmentación de imágenes basada en color?
- Cómo mejorar la lógica o la presentación de la conjetura descrita en una respuesta para que más personas puedan entender lo que creo que es un método sorprendente para crear algorítmicamente un conjunto primo potencialmente infinito
- ¿Cuáles son algunos algoritmos básicos en el aprendizaje automático para que su programa aprenda de otros datos (aprendizaje supervisado)?
- ¿Cómo se ordenan las matrices para que los valores altos y bajos se distribuyan en diagonal?
Dificultades para diseñar una estrategia de programación
El diseño de una estrategia de programación depende de las propiedades de las tareas:
- Costo de las tareas : ¿todas las tareas tienen el mismo costo de cálculo? Si no lo hacen, ¿cuándo se conocen esos costos? F antes de la ejecución, cuando se crea una tarea, o solo cuando termina?
- Dependencias entre tareas : ¿podemos ejecutar las tareas en cualquier orden? Si no, ¿cuándo se conocen las dependencias entre tareas? F antes de la ejecución, cuando se crea la tarea, o solo cuando termina?
- Localidad : ¿es importante que algunas tareas se ejecuten en el mismo procesador para reducir los costos de comunicación? ¿Cuándo sabemos los requisitos de comunicación?
Soluciones de programación : –
Programación estática : las decisiones se toman en el momento de la compilación.
- el análisis estático de programas se usa para estimar el tamaño de las tareas; Esta información es difícil de obtener y, a menudo, incompleta.
- mapeo estático del árbol de búsqueda en la arquitectura paralela (el mapeo óptimo es NP-completo).
- construya un gráfico dirigido con los nodos que representan las tareas y los enlaces que representan datos o dependencias de comunicación; Determinar el orden de ejecución de las tareas para minimizar el tiempo de ejecución.
Programación dinámica (o trabajo compartido adaptable) : utiliza información de estado computacional durante la ejecución para tomar decisiones.
Ejemplo : verifica la carga de cada procesador y garantiza un equilibrio de carga dinámico entre todos los procesadores.
¿Por qué la programación dinámica?
Una gran clase de problemas tiene un espacio de solución que corresponde a un árbol de búsqueda. Estos problemas son comúnmente:
- computacionalmente exigente
- permitir diferentes estrategias de paralelización
- requieren equilibrio de carga dinámico
Ejemplos :
- enumerar subgrafías de tamaño k de un gráfico dado
- minería de patrones en redes sociales y biológicas
- problema de colocar reinas en un tablero de ajedrez
- problemas de divide y vencerás y ramificará
- Árbol de ejecución de Prolog
Estrategias para la programación dinámica
Las estrategias de programación dinámica pueden ser:
centralizado
- un planificador central contiene toda la información sobre el sistema, es decir, la carga de trabajo, y toma decisiones para compartir y transferir el trabajo.
- funciona bastante bien en la memoria compartida, pero con un número reducido de procesadores.
- es ineficiente en la memoria distribuida, ya que requiere mucha comunicación para mantener actualizada la información de programación.
repartido
- Hay un planificador por procesador que toma decisiones autónomas con respecto al trabajo compartido.
- El objetivo es mantener ocupado su procesador y equilibrar la carga de trabajo en el sistema.
para más:-
Algoritmos de equilibrio de carga
Tipos de equilibrio de carga
Comparación de algoritmos de equilibrio de carga
Sistemas operativos: programación de CPU
Problema de secuencia de trabajo | Set 1 (Algoritmo codicioso) – GeeksforGeeks
Programación ponderada de trabajos – GeeksforGeeks
