Analysis of parallelization strategies in the context of hierarchical matrix factorizations

Resumen

(English summary below) Las H-Matrices nacen como una potente herramienta numérica para abordar aplicaciones cuyos datos generan estructuras que se sitúan entre los escenarios densos y dispersos. El beneficio clave por el que las H-Matrices son valiosas es el ahorro tanto en términos de almacenamiento como de cómputo, de un modo tal que llegan a reducirse hasta un coste logarítmico-lineal. La clave del éxito de las H-Matrices reside en la compresión controlable que ofrecen: eligiendo la condición de admisibilidad adecuada para separar los datos importantes de los prescindibles, así como un buen algoritmo de particionado, puede controlarse la pérdida de precisión que se quiere asumir, a cambio de acelerar los cálculos y reducir el consumo de memoria. Esta es la razón por la que las H-Matrices son especialmente apropiadas para métodos de elementos de contorno y elementos finitos, donde el resultado que se persigue no es necesario que sea totalmente preciso, pero sí importa disponer del mismo cuanto antes, dado que puede determinar, por ejemplo, si un diseño de ingeniería está listo para ser producido o necesita ser mejorado. Por su parte, el paralelismo de tareas ha demostrado con creces sus beneficios cuando se utiliza para optimizar las ejecuciones paralelas al resolver sistemas de ecuaciones lineales. Particularmente, los algoritmos por bloques o tiles, combinados con esta estrategia de paralelismo, han sido ampliamente utilizados (y lo siguen siendo) para proveer a la comunidad científica de soluciones paralelas potentes y eficientes en arquitecturas multinúcleo. El objetivo principal de esta tesis es diseñar, implementar y evaluar algoritmos paralelos para operar de un modo eficiente con H-Matrices en arquitecturas multinúcleo. Con este objetivo en mente, la primera contribución que describimos es un estudio en el que demostramos que el paralelismo de tareas es apropiado para operar con H-Matrices, simplificando para ello, tanto como nos es posible, la Aritmética con H-Matrices. A continuación, describimos en detalle las dificultades a las que se debe hacer frente cuando se paralelizan las complejas implementaciones que sirven para operar con estas matrices. Tras esto, explicamos cómo nos ayudaron las nuevas funcionalidades del modelo de programación OmpSs-2 a sortear la mayoría de dichas cuestiones, para así llegar a alcanzar una buena eficiencia al ejecutar nuestra implementación de la H-LU basada en paralelismo de tareas. Finalmente, explicamos cómo hemos explorado el diseño e implementación de una versión regularizada de las H-Matrices, a la que denominamos Tile H-Matrices, en la que somos capaces de mantener un ratio de precisión y compresión competitivo con el proporcionado por H-Matrices puras, a la vez que aprovechamos los beneficios de los algoritmos por bloques, ampliamente conocidos y utilizados en matrices particionadas en bloques (regulares), es decir, que presentan tamaños de bloque bastante homogéneos. --- H-Matrices were born as a powerful numerical tool to tackle applications whose data generates structures that end laying in between dense and sparse scenarios. The key benefit that makes H-Matrices valuable is the savings that offer both in terms of storage and computations, in such a way that they are reduced to log-linear costs. The key behind the success of H-Matrices is the controllable compression they offer: by choosing the appropriate admissibility condition to discern important versus dispensable data and designing good partitioning algorithms, one can choose the accuracy loss that wants to assume in exchange for computations acceleration and memory consumption reduction. This is the reason why H-Matrices are specially suitable for boundary element and finite element methods where the pursued result does not need to be totally accurate, but it is important to have it ready as fast as possible, as it can determine, for example, whether an engineering design is ready to be produced or needs to be improved. On their side, task-parallelism has proved suffciently its benefits when being employed to optimize the parallel execution when solving linear systems of equations. Particularly, tiled or block algorithms combined with this parallelism strategy have widely been (and are still) employed to provide the scientific community with powerful and efficient parallel solutions for multicore architectures. The main objective of this thesis is designing, implementing and evaluating parallel algorithms to operate efficiently with H-Matrices in multicore architectures. To this end, the first contribution we describe is a study in which we prove that task-parallelism is suitable for operating with H-Matrices, by simplifying as much as possible the H-Arithmetic scenario. Next, we describe in detail the difficulties that need to be addressed when parallelizing the complex implementations that operate with this type of matrices. Afterwards, we explain how the new features included in OmpSs-2 programming model helped us avoiding the majority of the described issues and thus we were able to attain a fair efficiency when executing a task-parallel H-LU. Lastly, we illustrate how we explored a regularized version of H-Matrices, which we call Tile H-Matrices, in which we are able to maintain competitive-with-pure-H-Matrices precision and compression ratios, while leveraging the well known benefits of tile algorithms applied to matrices provided with (regular) tiles (this is, mostly homogeneous block dimensions).