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

Resumen

El objetivo principal de esta Tesis es el desarrollo de una metodología de auto-optimizació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 eficiente 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 eficientes 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án internamente la rutina de multiplicación de matrices previamente optimizada. Del mismo modo, en un siguiente nivel de la jerarquía se podrá considerar la ejecución de códigos científicos 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ía 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 auto-optimizació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 eficientes 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á 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án 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án varias configuraciones de unidades de cómputo, por ejemplo, multicores con distinto número de cores o agrupaciones de nodos a nivel de cluster, con el fin de obtener diferentes grados de heterogeneidad. Una vez analizada la metodología en el primer nivel hardware, se pasará 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á 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 suficiente 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án 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ífico 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.