Técnicas de modelado y optimización del tiempo de ejecución de rutinas paralelas de álgebra lineal

Resumen

En este trabajo se describe una metodología de modelado del tiempo de ejecución de rutinas de álgebra lineal implementadas mediante los paradigmas de pasos de mensajes y de memoria compartida, que refleja las características del software y del hardware de la plataforma en la que se ejecuta la rutina y que permite abordar su ajuste automático. El modelo de tiempo de ejecución se construirá a partir del estudio teórico de complejidad de la rutina, cuando se disponga de información sobre el algoritmo implementado, o a partir de funciones matemáticas en las que aparecen el tamaño del problema y los parámetros ajustables de las rutinas de álgebra lineal. En ambos casos el modelo será de aplicación en la selección de diferentes ajustes, tales como el número de procesadores a utilizar, el tamaño del bloque de cálculo, la selección de la mejor librería de entre las disponibles o de la selección del mejor algoritmo con el que resolver un problema. En plataformas heterogéneas se propone una metodología que permita ejecutar el software desarrollado para plataformas homogéneas de forma óptima, y se introduce en el proceso de selección la asignación de procesos a procesadores. Se utilizarán técnicas heurísticas, junto con el modelo que aproxima el tiempo de ejecución de la rutina, en la búsqueda de una solución a la mejor selección de procesos, asignación de procesos a procesadores, y selección de los parámetros ajustables de la rutina homogénea. En rutinas de álgebra lineal que utilicen el paradigma de programación de memoria compartida, se considerará también como parámetro ajustable la versión del ejecutable de la rutina generada por los compiladores disponibles en la plataforma multicore. El modelo de tiempo de ejecución nos proporcionará información sobre la mejor selección de los parámetros ajustables de la rutina y sobre la versión compilada que se ejecutará en el menor tiempo. ABSTRACT: This work describes a methodology for modelling the execution time of linear algebra routines implemented with the programing paradigms of message-passing and shared memory. The methodology reflects the characteristics of the software and the hardware in the execution platform, and in this way the automatic tuning of the routine is achieved. A theoretical model of the execution time of the routine is built when information about the algorithm is available. If this information is unavailable a model is obtained experimentally as a function of the problem size and the adjustable parameters in the routine. In both cases, the model is aplicable for selection of differents parameters, such as the number of processors to be used, the block size, the best basic library or the best available algorithm to solve a specific problem. We propose a methodology to run efficiently on heterogeneous platforms the software designed for homogeneous platforms. The mapping of processes to processors is included in the selection process. To select the best number of processes, the processes to processors mapping and the selection of the adjustable parameters of the homogeneous routine, an heuristic approach is considered in combination with the theoretical model of the execution time. An additional parameter is considered for shared-memory linear algebra routines: the executable version of the routine generated by the different available compilers on the multicore platform. The model provides information about the best selection of the adjustable parameters of the routine and about the compiled ersion with which the problem is solved in the shortest time. PALABRAS CLAVE: ajuste automático, álgebra lineal, optimización, modelado del rendimiento, computación heterogénea, multicore. TÉRMINO TESAURO: 120300 CLASIFICACIÓN UNESCO: 120300 KEY WORDS: auto-tuning, linear algebra, optimization, performance modelling, heterogeneous computing, multicore.