Técnicas de optimización de rutinas paralelas de álgebra lineal en sistemas heterogéneos

Abstract

El objetivo principal de esta Tesis es el desarrollo de una metodología de autooptimizaci ón jerárquica para rutinas de álgebra lineal en entornos computacionales heterogéneos. Esta metodología ha sido diseñada de forma que permita la obtención de rutinas que sean ejecutadas de forma efi ciente desde el nivel más bajo de la jerarqu ía, tanto hardware como software, hasta llegar al nivel más alto en cada caso. En lo referente al hardware, los componentes que se consideran a más bajo nivel son los elementos computacionales básicos: CPU multicore, GPU y MIC (Xeon Phi). Los parámetros a tener en cuenta para optimizar las rutinas son distintos en cada uno de ellos, pero la metodología debe ser válida para todos. Estos elementos computacionales, a su vez, pueden agruparse para formar otros de mayor nivel (nodo). Generalmente, hoy en d a un nodo computacional estándar suele estar formado por una CPU multicore y uno o varios coprocesadores, que en algunos casos son de distinto tipo (GPU y/o MIC) e incluso pueden tener diferente capacidad computacional aunque sean del mismo tipo. La metodología, por tanto, debe considerar cómo combinar la información de auto-optimización a nivel de elemento computacional básico, para guiar la optimización a nivel de nodo. Los nodos, a su vez, se pueden agrupar en clusters, homogéneos o heterogéneos, por lo que la metodología jerárquica ha de ser capaz, a su vez, de obtener la información de optimización a nivel de nodo para guiar la optimización de las rutinas a nivel de cluster. En cuanto al software (rutinas de álgebra lineal), se comienza por el nivel correspondiente a las rutinas básicas, principalmente la multiplicación de matrices, pues constituye el componente computacional básico sobre el que se implementan otras rutinas e ficientes de álgebra lineal de nivel superior en los entornos computacionales actuales. A continuación, la metodología se extiende a rutinas de mayor nivel, como la multiplicación de Strassen o la factorización LU, las cuales utilizarían internamente la rutina de multiplicación de matrices previamente optimizada. Del mismo modo, en un siguiente nivel de la jerarquía se podría considerar la ejecución de códigos científi cos que realicen llamadas a rutinas del nivel inferior, como pueden ser simulaciones en las que se lleve a cabo la resolución simultánea de varios sistemas de ecuaciones. Además, dado que existen multitud de librerías de álgebra lineal optimizadas y, en algunos casos, paralelizadas para distintos sistemas, se hace uso de las rutinas que contienen y se analiza la aplicación de la metodología de autooptimización jerárquica considerando diferentes librerías. De esta manera, se puede mostrar su validez independientemente de las rutinas y librerías básicas utilizadas El proceso de auto-optimización tiene como principal objetivo obtener rutinas e ficientes en los sistemas computacionales para los que se diseñan, para lo cual es necesario seleccionar los valores a utilizar para cada uno de los parámetros del conjunto de parámetros ajustables que lleven a la obtención de tiempos de ejecución cercanos al óptimo experimental. La elección del conjunto de parámetros depende tanto de la rutina como del entorno computacional. Por tanto, la metodología de auto-optimización debe garantizar que es válida para múltiples rutinas, librerías y sistemas computacionales, de forma que sea fácilmente extensible en cualquiera de estas dimensiones. Para alcanzar el objetivo principal establecido, la metodología de trabajo utilizada comenzaría analizando el comportamiento de la metodología de auto-optimización jerárquica realizando un estudio por niveles (tanto hardware como software), considerando diferentes escenarios (sistemas y rutinas) y parámetros en cada nivel hasta llegar al mayor nivel considerado en cada caso, de forma que las conclusiones sean generales y no dependan de la rutina o de un sistema concreto. Los experimentos se llevarían a cabo sobre plataformas heterogéneas compuestas por nodos con distinto número y tipo de unidades de procesamiento paralelo (CPU, GPU, MIC). Se considerarían varias con figuraciones de unidades de cómputo, por ejemplo, multicores con distinto número de cores o agrupaciones de nodos a nivel de cluster, con el n de obtener diferentes grados de heterogeneidad. Una vez analizada la metodología en el primer nivel hardware, se pasaría al siguiente nivel de elementos de computación, analizando qué información del nivel anterior se puede utilizar para acelerar la toma de decisiones en el nivel actual manteniendo, al mismo tiempo, la calidad del proceso de optimización. Del mismo modo, tras analizar las rutinas de un nivel, se pasaría al siguiente nivel de la jerarquía software, recorriendo de nuevo, de forma incremental, los niveles de la jerarquía hardware. Así, mientras que en el nivel básico de las rutinas puede ser su ficiente trabajar con la multiplicación de matrices (al ser el núcleo computacional en el que se basan rutinas de mayor nivel), en el siguiente nivel se podrían considerar rutinas que invoquen a la multiplicación de matrices y hagan uso de parámetros de distinto tipo, como el nivel de recursión en la multiplicación de Strassen o el tamaño de bloque en las factorizaciones matriciales. La labor de investigación realizada en esta Tesis ha culminado con la publicación de un art culo en una revista de carácter científico e internacional. En este artículo se abordan los contenidos del núcleo de la Tesis y se muestran los principales resultados de investigación obtenidos con la metodología de auto-optimización jerárquica. Los resultados son satisfactorios y muestran la efectividad de aplicar la metodología siguiendo un enfoque jerárquico en los niveles hardware y software. De esta forma se constata, por un lado, el interés científi co que tiene el trabajo realizado y, por otro, la validez de la propia metodología, dada su capacidad para adaptarse a cualquier tipo de sistema computacional y de ser extendida con otras rutinas, librerías y técnicas de selección de los valores de los parámetros (algorítmicos y del sistema). El objetivo es seguir avanzando en la misma línea, extendiendo la metodología con nueva funcionalidad y considerando su inclusión en software de mayor nivel que haga uso de ella para conseguir una ejecución optimizada en la resolución de problemas cientí ficos y de ingeniería.

The aim of this Thesis is the development of a hierarchical auto-tuning methodology for linear algebra routines in heterogeneous computational environments. This methodology has been designed to allow obtaining routines executed efficiently from the lowest level of the hierarchy, both hardware and software, to the highest level in each case. In terms of hardware, the components considered at the lowest level are the basic computational elements: multicore CPU, GPU and MIC (Xeon Phi). The parameters to take into account to optimize the routines are different in each of them, but the methodology must be valid in all cases. These computational elements can be grouped into higher level components (nodes), which generally consists of a multicore CPU and one or more coprocessor, in some cases of a different type (GPU or MIC) or with diferent computational power even if they are of the same type. Therefore, the methodology must consider how to combine the auto-tuning information from the basic computational elements to guide the optimization at node level. The nodes, in turn, can be grouped into clusters, either homogeneous or heterogeneous, so the hierarchical methodology must be able to obtain the optimization information at node level to guide the optimization routines at cluster level. As for the software (linear algebra routines), the process starts with basic routines, mainly the matrix multiplication, since it is the basic computational component used for the implementation of other efficient higher-level linear algebra routines. The methodology is then extended to higher level routines, such as the Strassen multiplication or the LU factorization, which will use the previously optimized matrix multiplication routine. Similarly, in the next level of the hierarchy, it could be considered the execution of scienti c codes that call lower level routines, such as simulations in which the resolution of several systems of equations is performed simultaneously. In addition, since there are multiple optimized linear algebra libraries and, in some cases, parallelized for different systems, these routines are used and the application of the hierarchical auto-tuning methodology is analyzed considering different libraries. In this way, the effectiveness of the methodology can be shown independently of the routines and libraries used. The main goal of the auto-tuning process is to obtain efficient routines in the computational systems for which they are designed. Therefore, it is necessary to select the values of the parameters of a set of adjustable parameters that lead to execution times close to the experimental optima. The choice of the set of parameters depend on both the routine and the computational system. Thus, the auto-tuning methodology must ensure its validity for multiple routines, libraries and computing systems, so that it can be easily extended in any dimension. To achieve the main goal established, the working methodology used will begin by analysing the behaviour of the hierarchical auto-tuning methodology by performing a study by levels (both hardware and software), considering different scenarios (systems and routines) and parameters at each level until reaching the highest level considered in each case, so that the conclusions are general and do not depend on the routine or a speci c system. The experiments will be carried out on heterogeneous platforms made up of nodes with di erent number and type of parallel processing elements (CPU, GPU, MIC). Several con gurations of computing units will be considered, e.g. multicores with diferent number of cores or groups of nodes at cluster level, in order to obtain different degrees of heterogeneity. Once the methodology is analyzed at the rst level of hardware, the process moves to the next level of computing elements, analyzing the information from the previous level that can be used to accelerate the decision taken at the current level while maintaining the quality of the optimization process. Similarly, after analyzing the routines at one level, the process will continue to the next level of the software hierarchy, moving through the levels of the hardware hierarchy incrementally. Thus, while at the level of basic routines it is enough to work with the matrix multiplication, in the next level it could consider routines that internally call that routine and use diferent parameters, such as the recursion level in the Strassen multiplication or the block size in matrix factorizations, such as LU. The research work carried out in this Thesis has culminated with the publication of an article in an international journal. This article describes the main ideas developed in the Thesis and shows the main results obtained with the proposed hierarchical auto-tuning methodology. The results are satisfactory and show the e ectiveness of applying a hierarchical approach both in the hardware and software levels. In this way, the validity of the proposed methodology is con rmed, due to its capacity to be adapted to any type of computing system and to be extended with other routines, libraries and techniques for the selection of the values of the algorithmic and system parameters. The goal is to continue advancing in the same direction, extending the methodology with new features and considering its inclusion within higher level software that can make use of it to achieve an optimized execution. It is expected that these advances allow the efficient application of the hierarchical auto-tuning methodology in solving scienti c and engineering problems.