algoritmos de balanceo de carga y programación

Question

así que aquí está mi problema:

Tengo varios servidores de configuración diferentes. Tengo diferentes cálculos (trabajos); Puedo predecir cuánto tiempo tardará cada trabajo aproximadamente en caclularse. Además, tengo prioridades. Mi pregunta es cómo mantener todas las máquinas cargadas al 99-100% y programar las tareas de la mejor manera.

Cada máquina puede hacer varios cálculos a la vez. Los trabajos se envían a la máquina. La máquina central conoce la carga actual de cada máquina. Además, me gustaría asignar aquí algún tipo de aprendizaje automático, porque sabré estadísticas de cada trabajo (iniciado, finalizado, carga de la CPU, etc.).

¿Cómo puedo distribuir trabajos (cálculos) de la mejor manera posible, teniendo en cuenta las prioridades?

¿Alguna sugerencia, idea o algoritmo?

FYI: Mi plataforma .NET.

Answer 1

Parece que esto tiene muy poco que ver con .NET.

Pero piense en sus máquinas como 'hilos de trabajo', haga un 'pool' de máquinas disponibles ordenadas en la CPU disponible (u otro recurso importante), luego use su conocimiento de cada tarea para empujar cada trabajo a la máquina más adecuada .

Si conoce todos los trabajos por adelantado, probablemente pueda usar un algoritmo de "mejor ajuste" para programarlos en el orden correcto en las máquinas correctas. También puede ver los algoritmos de "corte de existencias"; http://en.wikipedia.org/wiki/Cutting_stock_problem ...

Answer 2

1. Mire Dryad linq. Ya está en versión académica y puede ser útil.
2. Win HPC server - solución empresarial para informática distribuida de Microsoft.
3. Algunos code samples que pueden ayudar a construir el equilibrio de carga analizando los contadores de rendimiento.
4. Microsoft tiene StockTrader aplicación de muestra (con fuentes), que es un ejemplo de SOA distribuible con balanceo de carga RoundRobin escrito a mano.

Answer 3

Microsoft publicó recientemente un paper en su planificador de quincy. Si simplemente está optimizando la utilización de la CPU, un solucionador muy simple puede encontrar el óptimo global. Si necesita optimización en más ejes, obviamente el espacio problemático será más complicado.

¿Qué tan grande es su clúster? ¿Cómo lidiar con la optimización de casos de fallas? ¿Importan? ¿Hay IO? ¿Los datos tienen afinidad de disco? ¿Hay más de un lugar para ejecutar un trabajo? Todas las cosas a considerar

Answer 4

Como un enfoque alternativo, puede utilizar las estimaciones de relación de rendimiento máximo de cada máquina para programar trabajos. Esto puede ser muy efectivo solo si está considerando el rendimiento del tiempo de ejecución de la CPU de un sistema con equilibrio de carga. Los problemas relacionados con E/S, tamaño del clúster, rendimiento de la red, tipos de modelo de memoria, etc., se descuidan con este enfoque. Eche un vistazo a http://dx.doi.org/10.1145/1513895.1513901

Una propuesta para un enfoque más preciso (distribución de trabajo equilibrado y con carga equilibrada) será el algoritmo, dependiente de la arquitectura de la computadora. En este caso, el trabajo de mayor prioridad puede programarse para el mejor servidor que satisfaga sus demandas, pero primero debe determinar una asignación óptima de trabajos al servidor.También puede aplicar algunos métodos de algoritmos de programación de SO en multiprocesadores (no uniprocesadores). Espero que esto te sea útil.