Particionamiento y Balance de Carga en Simulaciones Distribuidas de Bancos de Peces

Abstract

El particionamiento y balance de carga son aspectos de gran interés en simulaciones distribuidas basadas en modelos orientados al individuo espacialmente explícitos. La descomposición equitativa del dominio del problema y la distribución eficiente de las particiones sobre las unidades de cómputo de la arquitectura paralela/distribuida son factores cruciales cuando se plantea como objetivo obtener el mejor rendimiento de la aplicaciÛn de simulaciÛn distribuida. Además, en modelos que exhiben patrones de movimiento es necesario establecer políticas competentes de balance de carga dinámico para continuar satisfaciendo el objetivo de rendimiento a medida que la simulación evoluciona en función del tiempo. En el presente trabajo se han desarrollado mÈtodos de particionamiento y balance de carga para simulaciones distribuidas a gran escala de modelos orientados al individuo espacialmente explícitos que exhiben patrones de movimiento. Se ha utilizado el modelo de Huth & Wissel, el cual representa el movimiento coordinado y polarizado de bancos de peces, para validar las estrategias desarrolladas. El método de particionamiento consiste en descomponer el dominio del problema en particiones compactas generadas a partir del criterio del radio cobertor y diagramas de Voronoi. La distribución de las particiones se realiza por medio de la agrupación de particiones por proximidad en un conjunto meta-particiones de cardinalidad igual a la cantidad de unidades de cómputo. La estrategia de balance de carga dinámica consiste en detectar el desbalance por medio de un algoritmo basado en umbrales y re-configurar las meta-particiones para lograr el re-equilibrio. Finalmente, se ha realizado experimentación exhaustiva con motivo de validar y verificar la viabilidad del simulador distribuido en distintos escenarios.

artitioning and load balancing are highly important issues in distributed simulations based on spatially-explicit individual-oriented models. Choosing how to decompose the domain of an individual-oriented system and efficiently distribute the set of partitions are crucial factors at the moment to execute the distributed simulation. Furthermore, if the individual-oriented model exhibits mobility patterns, we should be able to maintain the load balancing in order to keep the global application performance as the distributed simulation evolves in time. In this work, we have developed partitioning and load balancing strategies for distributed spatially-explicit individual-oriented simulations with mobility patterns. We have used the Huth and Wissel model, which represents the coordinated and polarized motion of fish schools, in order to validate the developed strategies.Our partitioning method consists of decomposing an individual-oriented system into a collection of compact partitioning generated by means of covering radius criterion and Voronoi diagrams. The distribution model consists of grouping partitions by proximity into a set of meta-partitions. The number of meta-partitions should be equal to the number of computing resources of the distributed architecture. The dynamic load balancing strategy consists of detecting imbalance by means of a threshold-based algorithm and reconfiguration the set of meta-partitions in order to re-balance the workload. We have done exhaustive experimentation using a large set of scenarios in order to validate and verify the distributed simulator feasibility.