Redistribución automática de carga para ejecución paralela heterogénea de aplicaciones Iterative Stencil Loop

Abstract

La computación paralela es un paradigma de cómputo cuyo fundamento principal es la utilización de múltiples unidades de procesamiento para ejecutar tareas, que se dividen en sub-tareas que se pueden trabajar de forma simultánea. Para ello se pueden utilizar desde pequeños sistemas con múltiples núcleos, hasta grandes clústeres con una cantidad masiva de equipos interconectados por redes de alta velocidad. La computación paralela heterogénea es un caso especial de la computación paralela donde se utilizan nodos con distintos tipos de dispositivos o unidades de cómputo adaptados para diferentes tipos de tareas, lo cual les da una ventaja para trabajos más especializados y una mayor flexibilidad. Las aplicaciones de tipo ISL (Iterative Stencil Loop) representan una clase importante de soluciones a problemas científicos en diversos campos de simulación. En este tipo de simulaciones, el valor de cada celda de una matriz multidimensional se actualiza a partir de los valores de sus celdas vecinas. Las celdas que se consideran vecinas las determina un patrón, denominado “stencil”, definido por cada aplicación concreta. Estas aplicaciones presentan un alto grado de paralelismo, ya que cada celda se puede calcular de forma independiente basándonos en valores anteriores de celdas cercanas, esta es una propiedad denominada “alta localidad de datos”. Solo es necesario sincronizar o coordinar los elementos de cómputo entre iteraciones. El tiling es una técnica de transformación de código que separa las estructuras de datos y, por tanto, el cómputo, en bloques o tiles de tamaño fijo de celdas vecinas. Es especialmente útil para distribuir el trabajo en aplicaciones, como ISL, donde la alta localidad de datos reduce la necesidad de interacciones o sincronizaciones globales, siendo necesarias solo entre bloques o tiles vecinos. Hitmap, Controllers y Epsilod son una pila de bibliotecas de funciones y herramientas desarrolladas por el grupo de investigación Trasgo de la Universidad de Valladolid, que permiten aplicar tiling para particionar, desplegar y ejecutar aplicaciones ISL en múltiples tipos de dispositivos y clústeres paralelos heterogéneos. Sin embargo, la computación paralela heterogénea presenta un problema adicional aún no resuelto por estas herramientas. Al mezclarse elementos de cómputo diferentes, no tardan lo mismo en realizar la misma cantidad de trabajo. Esto implica que en cada operación de sincronización el tiempo pasa a ser el del bloque de cómputo más lento. En trabajos previos se desarrolló un mecanismo automático de equilibrado de carga para CPUs en Hitmap. La idea de este trabajo es, integrar en las herramientas Controllers y EPSILOD el sistema de equilibrado automático de carga, adaptándolo para su uso en sistemas heterogéneos, incluyendo dispositivos con memorias globales separadas. Este sistema estudia, de forma periódica, los tiempos de ejecución de cada elemento de cómputo. En función de los tiempos observados, calcula una nueva partición de datos con forma irregular en la que cada parte tenga un tamaño acorde a su rendimiento. En caso de ser necesario, mueve los datos entre los procesos paralelos, extrayéndolos de las memorias de los dispositivos y recolocándolos en las de otros, de forma completamente transparente al usuario. Se han realizado una serie de pruebas experimentales en sistemas heterogéneos reales para mostrar las ventajas de añadir este mecanismo.

Parallel computing is a computing paradigm whose main foundation is the use of multiple processing units to execute tasks, which are divided into sub-tasks that can be worked on simultaneously. This can range from small systems with multiple cores to large clusters with a massive number of computers interconnected by high-speed networks. Heterogeneous parallel computing is a special case of parallel computing where nodes with different types of devices or computing units adapted for different types of tasks are used, which gives them an advantage for more specialized jobs and greater flexibility. ISL (Iterative Stencil Loop) applications represent an important class of solutions to scientific problems in various fields of simulation. In this type of simulations, the value of each cell of a multidimensional matrix is updated from the values of its neighboring cells. The cells considered as neighbors are determined by a pattern, called a stencil, defined by each specific application. These applications have a high degree of parallelism since each cell value can be computed independently based on previous values of neighboring cells, this is a property called “high data locality”. It is only necessary to synchronize or coordinate the computation elements between iterations. Tiling is a code transformation technique that separates data structures, and thus computation, into fixed-size blocks or tiles of neighboring cells. It is especially useful for distributing work in applications, such as ISL, where high data locality reduces the need for global interactions or synchronizations, being necessary only between neighboring blocks or tiles. Hitmap, Controllers and Epsilod are a stack of function libraries and tools developed by the Trasgo research group at the University of Valladolid, which allow applying tiling to partition, deploy and run ISL applications on multiple types of devices and heterogeneous parallel clusters. However, heterogeneous parallel computing presents an additional problem not yet solved by these tools. As different computational elements are mixed, they do not take the same amount of time to perform the same amount of work. This implies that in each synchronization operation, the time becomes that of the slowest computation block. Previous work was done to develop an automatic load balancing mechanism for CPUs in Hitmap. The idea for this work is to integrate the automatic load balancing system into the Controllers and EPSILOD tools, adapting it for use in heterogeneous systems, including devices with separate global memories. This system periodically studies the execution times of each computation element. Based on the observed times, it calculates a new irregularly shaped data partition in which each part is sized according to its performance. If necessary, it moves the data between the parallel processes, extracting them from the devices’ memories and relocating them to those of others, in a completely transparent way to the user. A series of experimental tests have been performed on real heterogeneous systems to show the advantages of adding this mechanism.