Distribución óptima de la carga de trabajo en aplicaciones MPI a gran escala
Tengo un gran número de tareas, x, y n rangos de MPI (x >> n). Cada tarea tiene una carga de trabajo diferente y requiere una gran comunicación con algunas otras tareas.
¿Cómo puedo encontrar una distribución óptima para asignar múltiples tareas a cada rango de manera que la comunicación entre los rangos sea mínima y la carga de trabajo sea igual?
En otras palabras:
Tengo un grafo g con x nodos (tareas). Tanto los nodos como las aristas están ponderados. Necesito un algoritmo de agrupamiento de grafos que asigne n colores diferentes a cada nodo de manera que el peso total de todas las aristas entre diferentes colores sea mínimo y cada color tenga (aproximadamente) los mismos pesos de nodo.
¿Existen algoritmos adecuados para este problema de agrupamiento? Pensé en recocido simulado o alguna forma de algoritmo genético. Otra idea es cortar las aristas de bajo peso y crear subgrafos para reducir el problema.
davy.ai
Como experto en tecnologías de la información especializado en optimización, MPI, teoría de grafos, algoritmos de grafos y comunicación, existen varias formas de encontrar una distribución óptima para asignar múltiples tareas a cada rango. Una posible solución es utilizar algoritmos de agrupamiento de grafos, como espectrales, k-means o Louvain, para particionar las tareas en n grupos basados en los pesos de los nodos y las aristas. Estos algoritmos tienen como objetivo minimizar el peso total de todas las aristas entre los diferentes colores, al mismo tiempo que aseguran que cada grupo tenga pesos de nodos aproximadamente iguales.
Otro enfoque es utilizar heurísticas como el recocido simulado o algoritmos genéticos para encontrar una buena distribución de tareas a los rangos que minimice la comunicación y equilibre la carga de trabajo. Estas técnicas implican explorar diferentes soluciones, evaluar su función objetivo y mejorarlas iterativamente hasta encontrar una solución satisfactoria.
Además, eliminar aristas de bajo peso y crear subgrafos puede ayudar a reducir la complejidad del problema y generar tareas más pequeñas que sean más fáciles de manejar. Este enfoque se puede combinar con los métodos anteriores para lograr un mejor rendimiento y eficiencia.
En general, encontrar una distribución óptima para asignar múltiples tareas a cada rango de manera que se minimice la comunicación y se equilibre la carga de trabajo es un problema desafiante que requiere una consideración cuidadosa de la estructura y los pesos del grafo. Los métodos mencionados anteriormente, ya sea de forma individual o combinada, pueden ayudar a resolver este problema y optimizar el rendimiento del sistema.