Distribución dinámica de carga y redistribuciones de datos en aplicaciones paralelas

Abstract

Actualmente, la computación de alto rendimiento es la técnica utilizada para resolver grandes problemas en diversas áreas de investigación (ciencia, ingeniería, etc.) debido al aumento de rendimiento que proporcionan los supercomputadores. La computación heterogénea permite adaptar un sistema a un rango mayor de aplicaciones gracias a la integración de componentes de naturalezas diferentes en el sistema de cómputo, aprovechando así cada uno de los recursos hardware de cada dispositivo. Los supercomputadores con arquitecturas heterogéneas se cuentan actualmente entre los más potentes del mundo. Tiling es un método utilizado para mejorar el rendimiento de los sistemas paralelos que consiste en dividir el espacio de datos de un problema entre los procesos. Para equilibrar el tiempo de ejecución de cada proceso y mejorar así el tiempo total del programa se puede aplicar el balanceo de carga, un particionado irregular en el que el tamaño asignado a cada proceso depende de su capacidad computacional. La estimación de la capacidad puede realizarse antes de la ejecución de un programa o en tiempo de ejecución. El balanceo de carga adaptativo permite reestimar la carga y modificar el reparto de trabajo entre los procesos a lo largo de la ejecución de un programa, pero es un trabajo que tiene que hacer el programador para su aplicación concreta. No existe una función estándar de balanceo adaptativo dinámico para aplicaciones paralelas. La librería Hitmap proporciona herramientas para la gestión del particionado y mapeado de arrays de una manera simple y eficiente en un modelo de paralelismo SPMD. Cuenta con diversos tipos de particiones y separa la parte de comunicación del particionado de los datos, adaptando automáticamente las funciones al tipo de partición elegido gracias al uso de abstracciones. Este trabajo propone una función de balanceo de carga dinámico, adaptativo y transparente para entornos de computación paralela utilizando los recursos de Hitmap. Los resultados experimentales muestran que su uso mejora el rendimiento de los programas, reduciendo el tiempo total de ejecución frente a un reparto equitativo de la carga entre los procesos, sin suponer un sobrecoste de tiempo o recursos.

Nowadays, high performace computing is the technique used to solve big problems in varied research areas (science, engineering, etc.) due to the increase of performance the supercomputers provide. Heterogeneous computing allows to adapt a system to a bigger range of applications thanks to the integration of different natured components into the computing system, making advantage of every one of the hardware resources of each device. Supercomputers with heterogeneous architectures are currently included among the most powerful ones in the world. Tiling is a method used to improve the performance of parallel systems, consisting of splitting the data space of a problem among the processes. In order to balance the execution time of each process and therefore improving the total execution time of the program, load balancing can be applied, an irregular tiling where the size assigned to each process depends on its computational capacity. The estimation of capacity can be done before the execution of the program or at runtime. Adaptive load balancing allows to re-estimate the load and to modify the distribution of work amongst the processes throughout the execution of a program, but is a task that must be made by the programmer for his particular application. There is not a standard function for dynamic, adaptive load balancing for parallel applications. The Hitmap library provides tools to manage the tiling and mapping of arrays in a simple and efficient way in a SPMD parallel model. It features many partition types and it isolates the communication part from the data partitioning, automatically adapting the functions to the partition type chosen thanks to the use of abstractions. This work proposes a dynamic, adaptive and transparent load balancing function for parallel computing environments using Hitmap’s resources. The experimental results show that using it improves the performance of the programmes, reducing the execution time compared to an equitative load distribution among the processes, without signifying a time or resources overhead.