Desarrollo, optimización y autooptimización de algoritmos paralelos para análisis cinemático de sistemas multicuerpo basado en ecuaciones de grupo

Abstract

El modelado es la disciplina que permite analizar y simular el comportamiento de un determinado sistema mediante una representación numérica de sus propiedades. Entre sus áreas de aplicación se encuentran el estudio de sistemas naturales, climáticos, poblacionales o mecánicos. Las técnicas de modelado disponibles en la actualidad permiten abordar el estudio de sistemas cada vez más complejos que requieren del uso eficiente de sistemas computacionales para su resolución en unos tiempos aceptables dentro de los límites de las asignaciones de recursos informáticos. Por este motivo, los científicos plantean los modelos con un enfoque que permite su traducción a algoritmos susceptibles de ser ejecutados por un ordenador. Por ejemplo, en el campo de la ingeniería que estudia los sistemas multicuerpo, una formulación topológica facilita el modelado automático de dichos sistemas y permite una resolución computacional eficiente de su análisis cinemático. La información obtenida de este proceso se puede aplicar al diseño de nuevos mecanismos, y engloba aspectos tales como el análisis de la posición de los elementos que componen el sistema o el rango de desplazamiento de las piezas móviles.

Dado el interés por la implementación computacional de numerosos problemas de naturaleza científica, es posible acceder a paquetes de software elaborados por diversos grupos de investigación que resuelven determinados subproblemas y que se pueden reutilizar en la resolución de problemas de mayor complejidad. Un ejemplo de estos paquetes son las librerías de álgebra lineal, muy usadas habitualmente en este tipo de problemas científicos y que son objeto de estudio continuo para su adaptación a la incesante evolución del hardware.

Las plataformas de hardware actuales incorporan más de una unidad de procesamiento, bien integrando varios procesadores en sus CPUs, bien añadiendo otras unidades de arquitectura masivamente paralela, como las GPUs, para conformar nodos de computación híbridos. La existencia de este tipo de hardware paralelo motiva el interés en explotar la ejecución simultánea de cálculos, con la consiguiente reducción de los tiempos de resolución de modelos complejos. Ahora bien, una aplicación óptima de técnicas paralelas requiere de un conocimiento profundo del hardware y de las librerías de cómputo disponibles, muchas de las cuales requieren un ajuste mediante parámetros para aprovechar todo su potencial. Por este motivo, no es frecuente que investigadores en áreas científicas concretas sean a la vez expertos conocedores de los diversos paradigmas de programación paralela existentes.

Esta tesis investiga un enlace entre la disciplina de la ingeniería mecánica y la computación, ofreciendo a usuarios no expertos en paralelismo un software que incorpora el estudio y optimización de algoritmos mediante una adecuada selección de librerías y su configuración. Partiendo del modelo de un sistema multicuerpo expresado en forma de grafo acíclico de los cálculos (básicamente operaciones de álgebra matricial) y sus dependencias, el software permite a un usuario ajustar los parámetros de paralelismo y librerías, y realizar simulaciones del modelo para analizar la influencia que cada configuración tiene en los tiempos de resolución. Además, una ejecución autooptimizada recomienda al usuario la manera más eficiente de paralelizar los cálculos, la librería a usar y los ajustes teóricos óptimos que se recomiendan para los parámetros algorítmicos en cada etapa de resolución del algoritmo.

Por último, esta metodología se puede aplicar a otras disciplinas ajenas a la ingeniería mecánica, en concreto a aquéllas donde los problemas se pueden plantear con un enfoque similar, es decir, como agrupaciones de cálculos que incluyan operaciones matriciales realizadas en una determinada secuencia. Un ejemplo de aplicación en este sentido lo encontramos en algunas rutinas básicas de álgebra lineal, como la multiplicación de matrices.

Modeling is the discipline that allows the analysis and simulation of the behavior of a certain system through the numerical representation of its properties. Applications include among others the study of natural, climatic, population or mechanical systems. The modeling techniques available nowadays make it possible to afford the study of increasingly complex systems, usually requering the efficient use of computer systems to obtain its numerical resolution in times within the limits fixed by the computer resources. For this reason, scientists develop these models focusing on its subsequent translation into algorithms that can be executed in a computer. For example, in the field of engineering that studies multibody systems, a topological formulation facilitates automatic modeling and allows the efficient computational resolution of the system kinematics. The information obtained from this process can be applied afterwards to the design of new mechanisms, and covers aspects such as the analysis of the position of the elements that make up the system and the range of movement of the moving parts.

Given the growing interest in the computational implementation of many scientific problems, it is possible to access software packages already developed by several research groups aiming to solve certain sub-problems in a particular area. Those can be reused afterwards for solving more complex problems. An example of those packages are the linear algebra libraries, widely used in these types of scientific problems, which have been subject to continuous study for their adaptation to the constant evolution of modern hardware configurations.

The new hardware platforms incorporate more than one processing unit, either by integrating several processors in their CPUs, or by adding other units of massively parallel architecture, such as GPUs, or a combination of them, to make up hybrid computing nodes. The availability of this type of parallel hardware leads to an interest in exploiting the execution of simultaneous calculations, getting the benefit in the reduction of execution times. However, the optimal fit of parallel techniques requires a wide knowledge of the hardware and the available software libraries, many of which require the adjustment of a set of parameters for high performance. For this reason, it is not common for expert researchers in a specific scientific area to also be knowledgeable of the various existing parallel programming paradigms.

This thesis focuses on covering the gap between the discipline of mechanical engineering and computing, providing to non expert users in parallelism a simulator that includes the analysis and optimization of algorithms through the appropriate selection and configuration of libraries. Based on the model of a multibody system in the form of a graph that collects the calculations (basically matrix algebra operations) and their dependencies, this software lets the user to adjust the parallelism and librarie's parameters and then to carry out simulations to analyze the influence of this adjustment on the execution times. A self-optimized execution will also find the most efficient way to group the calculations, as well as the appropriate library to be used and the optimal settings that should be applied in each resolution stage of the algorithm.

Additionally, this thesis shows how this methodology can be applied to other disciplines outside the mechanical engineering field, specifically to those where problems can be posed with a similar approach, that is, as groupings of calculations consisting on matrix operations performed in a certain sequence. An example is the application to some basic linear algebra routines, such as the matrix multiplication.