A grid-hypergraph load balancing approach for agent based applications in HPC systems

Abstract

Hoy en día, una gran cantidad de problemas científicos y de ingeniería pueden ser estudiados y resueltos gracias a sistemas HPC (High Performance Computing). Los entornos HPC pueden resolver problemas cuando éstos son más complejos y los requerimientos de cómputo aumentan. Dentro de las aplicaciones HPC, existe un caso particular llamado ABMS (Agent-Based Modelling and Simulation), el cual permite analizar las propiedades emergentes de un sistema a partir de simular las interacciones entre entidades autónomas llamadas agentes. Las interacciones y comportamiento de los agentes están definidas según sus reglas de acción, parámetros y la evolución del conjunto de la población y del entorno simulado. Con la aparición de las plataformas ABMS para entornos HPC, los sistemas reales pueden ser modelados, analizados y simulados de forma más precisa, a través de incluir un gran número de agentes y reglas complejas, para representar más detalles, parámetros e interacciones del sistema. Esto conlleva a modelos basados en agentes (AB) aún más complejos, resultando un alto costo computacional. En este sentido, simular modelos AB complejos y realistas en un tiempo razonable es sólo si la simulación es ejecutada en paralelo en un entorno HPC. En términos de estructura de programa paralelo, SPMD (Single Program Multiple Data) es la más usada, la cual consiste en ejecutar el mismo programa en diferentes PEs (processing elements), pero sobre un distinto subconjunto del dominio. Sin embargo, en simulaciones grandes y complejas, aparecen requerimientos de cómputo irregulares y sobrecarga de comunicación, debido a políticas inapropiadas de particionamiento de datos y características dinámicas de creación y eliminación de agentes, lo cual retrasa toda la simulación. En estos casos, una descomposición inicial no puede ofrecer una solución eficiente y la carga variable de cómputo/comunicación necesita ser abordada dinámicamente. Por lo cual, es altamente beneficiosa una solución dinámica para reajustar la carga de trabajo. Esta tesis propone una metodología que permite mejoras dinámicas en el rendimiento de aplicaciones ABMS SPMD para modelos basados en agentes espacialmente explícitos. La metodología presenta una estrategia de sintonización para reducir problemas de desbalance de carga durante la ejecución de la aplicación. Esta estrategia ajusta la carga de trabajo global de la simulación, migrando grupos de agentes entre PEs según sus cargas computacionales y su interconectividad, modelando el sistema como un hipergrafo. Un hipergrafo es una generalización de grafo qué, en este caso, permite modelar interacciones de grupos de agentes de forma más precisa. Este hipergrafo se particiona utilizando un algoritmo paralelo de particionamento para decidir una distribución más apropiada. Esta estrategia define dos fases: monitorización and sintonización. En la fase de monitorización, se mide el tiempo de ejecución para evaluar problemas de rendimiento y, cuando sea necesario, aplicar la estrategia de balance de carga en la fase de sintonización. La estrategia de balance de carga contiene tres componentes principales: la representación de sistema de los agentes (ASR), las políticas de sintonización y la migración de agente. Esta estrategia, representa grupos de agentes como grids y modela la carga de trabajo de los grids como un hipergrafo, el cual se particiona para determinar una distribución más balanceada. Finalmente, los agentes son migrados por grupos para ajustar la carga de trabajo global. Adicionalmente, se define un mecanismo eficiente para comunicación de los agentes basado el ASR. Hemos evaluado esta estrategia usando una plataforma ABMS HPC real, llamada Flame (Flexible Large Scale Agent Modelling Environment), y simulando tres modelos reales Susceptible-Infected-Remove (SIR), Colorectal Tumour Growth (CTG) and Keratinocyte Colony Formation (KCF). Evaluando distintos aspectos de nuestra metodología, así como en su conjunto, hemos obtenido importantes ganancias de rendimiento y una significativa reducción del tiempo total de ejecución.

Nowadays, there are a large amount of scientific and engineering problems that can be studied and solved thanks to High Performance Computing (HPC) systems. HPC environments can solve computing problems when these become more complex and the amount of required computing power increases. Within HPC applications there is a particular case called Agent-Based Modelling and Simulation (ABMS), which allows analysing the emergent properties of a system from simulating the interactions amongst autonomous entities called agents. Agent interactions and behaviour are defined according to their procedural rules, characteristic parameters and the evolution of the whole population and the simulated environment. With the emergence of ABMS platforms intended to HPC environments, real systems can be more accurately modelled, analysed and simulated through including larger number of agents and complex rules for representing more system details, parameters and interactions. This leads to very complex agent-based (AB) models, resulting in a high computational cost. In this sense, simulating complex and realistic AB models is only feasible in a reasonable time if the simulation is executed in parallel on a HPC environment. In terms of the programming structure, due to its scalability and simplicity, single program multiple data (SPMD) is the dominant parallel application structure and consists of executing the same program in all processing elements (PEs), but on a different subset of the domain. However, in complex and large SPMD AMBS applications, improper data partition policies and dynamic characteristics related to the creation and elimination of agents introduce uneven computing requirements and network communication overhead that delays the simulation and may propagate across all PEs. Here, the initial decomposition cannot offer an efficient solution and the computing/communication workload needs to be dynamically tackled. At this point, an efficient dynamic solution to readjust the workload is incredibly beneficial. This thesis proposes a methodology that enables dynamic performance enhancements for SPMD ABMS applications and spatially-explicit AB models. The methodology introduces a tuning strategy which dynamically minimises the gaps of computing and communication workloads between PEs. As a result, the application will be able to process large number of agents with complex rules as fast and efficiently as possible. The strategy adjusts the global simulation workload migrating groups of agents among the PEs, according to their computation workload and their interconnectivity modelled using a hypergraph. A hypergraph is a graph generalisation that, in this case, allows more accurately modelling groups of agents’ interactions. This hypergraph is lastly partitioned using a parallel partitioning algorithm to decide a proper workload distribution. This approach defines two phases: monitoring and tuning. In the monitoring phase, the application workload is measured at runtime to identify and evaluate performance problems according to a permissive imbalance value and, when necessary, applying the load balancing strategy in the tuning phase. The load balancing contains three main components: agent system representation (ASR), tuning decisions and agent migration. The ASR, created through a clustering algorithm, represents groups of agents as grids, and models the grid’s workload as a global hypergraph which is partitioned to determine a more balanced grid distribution. From this distribution, groups of agents are migrated for adjusting the global workload. Additionally, we provide an efficient agent communication mechanism, based on the ASR, to determine the message receivers PEs. We have evaluated our strategy using a real HPC ABMS platform, so-called Flexible Large Scale Agent Modelling Environment (Flame), simulating three real AB models Susceptible-Infected-Remove, Colorectal Tumour Growth and Keratinocyte Colony Formation. Evaluating different aspects of our methodology, as well as an integral whole, we have obtained significant performance gains and hence an important reduction of the total execution times.