Triangularización de espacios de datos a través de la librería Hitmap

Abstract

Actualmente, el paradigma de la computación paralela es ampliamente utilizado por cientificos e investigadores para la resolución de problemas de cálculo con gran carga computacional. En la lista de TOP 500 se refleja el ranking con los 500 supercomputadores más potentes del mundo que existen en la actualidad. Estos sistemas son empleados para realizar cálculos con grandes volúmenes de datos en diferentes áreas de conocimiento tales como las matemáticas, la astronomía, la biología o la medicina. Dentro del paradigma de la computación paralela destacamos la técnica denominada como “Tiling". Esta técnica consiste en el reparto de la carga computacional entre diferentes unidades computaciones. Este reparto de carga se consigue a través del particionado del espacio de memoria donde se alojan los datos. Se realiza una división del dominio de datos del problema en bloques asignados a cada procesador. Hitmap es una librería diseñada por el grupo de investigación Trasgo que aúna mecanismos de comunicación así como mecanismos del particionado de datos. Este particionado se realiza con bloques de forma rectangular modelados a través de la estructura de datos Shape, que permite la creación de polígonos rectangulares de n-dimensiones. En este trabajo se desarrolla una extensión de la librería Hitmap para la triangularización del espacio de datos. Esta técnica se implementa a través de particiones triangulares de memoria permitiendo al sistema de cómputo paralelo aprovechar mejor la geometría del espacio de datos en ciertos tipos de problema, para reducir, en la medida de lo posible, las operaciones de comunicación y sincronización. Para realizar este particionado en polígonos triangulares se desarrollan los algoritmos de intersección, diferencia y unión.

Nowadays, the paradigm of parallel computing is widely used by scientists and researchers for solving computational problems with high computational load. The TOP 500 list reflects the ranking of the 500 most powerful supercomputers in the world that currently exist. These systems are used to perform calculations with large volumes of data in dfferent areas of knowledge such as mathematics, astronomy, biology or medicine. Within the paradigm of parallel computing we highlight the technique known as "Tiling". This technique consists of the distribution of the computational load between different computational units. This load sharing is achieved through the partitioning of the memory space where the data is stored. The data domain of the problem is divided into blocks assigned to each processor. Hitmap is a library designed by the Trasgo research group that combines communication mechanisms as well as data partitioning mechanisms. This partitioning is done with rectangular shaped blocks modeled through the Shape data structure, which allows the creation of n-dimensional rectangular polygons. In this project an extension of the Hitmap library is developed for the triangularization of the data space. This technique is implemented through triangular memory partitions, allowing the parallel computing system to take better advantage of the geometry of the data space in certain types of problems, to reduce, as far as possible, the communication and synchronization operations. To carry out this partitioning in triangular polygons, the intersection, difference and union algorithms are developed.