Partición de modelos de gran escala para simulación en paralelo de sistemas de eventos discretos

Resumen

Los algoritmos de simulación en paralelo de sistemas de eventos discretos utilizan un modelo dividido en tantas partes como procesadores requeridos de manera que cada procesador simula un sub-modelo más pequeño. Para que esta estrategia permita acelerar eficientemente las simulaciones se requieren dos condiciones: que el costo asociado a simular cada sub-modelo sea similar y que la comunicación necesaria entre los sub-modelos sea la mínima posible. Estas condiciones conducen a que la partición del modelo debe realizarse resolviendo un problema de balance de carga, lo que habitualmente se resuelve mediante un problema equivalente de teoría de grafos: como partir un grafo en un número dado de sub-grafos de manera que los sub-grafos tengan un número similar de vértices y que a la vez haya un número mínimo de aristas entre distintos subgrafos. De esta manera las simulaciones pueden avanzar en forma paralela y la sincronización sólo se hace necesaria cuando ocurre un cambio en un sub-modelo que afecta el comportamiento de otro sub-modelo. Una observación esencial es que habitualmente los modelos de gran escala son el resultado de utilizar estructuras repetitivas regulares (ecuaciones definidas de forma compacta en ciclos for loop que involucran arreglos de variables). Con el objetivo de explotar esta característica al representar un modelo mediante un grafo, se propuso recientemente el concepto de Grafos Basados en Conjuntos (SBG por Set Based Graphs) . Los SBGs son grafos en los cuales los vértices y aristas están agrupados en distintos conjuntos que se pueden representar de manera compacta por comprensión. De esa forma, al cambiar el tamaño de los arreglos de un modelo sin cambiar la estructura del mismo la representación del SBG asociado se mantiene idéntica. En este trabajo presentamos una adaptación del algoritmo clásico de Kernighan-Lin que utilizando la representación SBG permite generar particiones con un costo computacional independiente del tamaño de los arreglos de variables definidos en el modelo original.