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

espanolEl modelado es la disciplina que permite analizar y simular el comportamiento de un determinado sistema mediante una representacion numerica de sus propiedades. Entre sus areas de aplicacion se encuentran el estudio de sistemas naturales, climaticos, poblacionales o mecanicos. Las tecnicas de modelado disponibles en la actualidad permiten abordar el estudio de sistemas cada vez mas complejos que requieren del uso eficiente de sistemas computacionales para su resolucion en unos tiempos aceptables dentro de los limites de las asignaciones de recursos informaticos. Por este motivo, los cientificos plantean los modelos con un enfoque que permite su traduccion a algoritmos susceptibles de ser ejecutados por un ordenador. Por ejemplo, en el campo de la ingenieria que estudia los sistemas multicuerpo, una formulacion topologica facilita el modelado automatico de dichos sistemas y permite una resolucion computacional eficiente de su analisis cinematico. La informacion obtenida de este proceso se puede aplicar al diseno de nuevos mecanismos, y engloba aspectos tales como el analisis de la posicion de los elementos que componen el sistema o el rango de desplazamiento de las piezas moviles. Dado el interes por la implementacion computacional de numerosos problemas de naturaleza cientifica, es posible acceder a paquetes de software elaborados por diversos grupos de investigacion que resuelven determinados subproblemas y que se pueden reutilizar en la resolucion de problemas de mayor complejidad. Un ejemplo de estos paquetes son las librerias de algebra lineal, muy usadas habitualmente en este tipo de problemas cientificos y que son objeto de estudio continuo para su adaptacion a la incesante evolucion del hardware. Las plataformas de hardware actuales incorporan mas de una unidad de procesamiento, bien integrando varios procesadores en sus CPUs, bien anadiendo otras unidades de arquitectura masivamente paralela, como las GPUs, para conformar nodos de computacion hibridos. La existencia de este tipo de hardware paralelo motiva el interes en explotar la ejecucion simultanea de calculos, con la consiguiente reduccion de los tiempos de resolucion de modelos complejos. Ahora bien, una aplicacion optima de tecnicas paralelas requiere de un conocimiento profundo del hardware y de las librerias de computo disponibles, muchas de las cuales requieren un ajuste mediante parametros para aprovechar todo su potencial. Por este motivo, no es frecuente que investigadores en areas cientificas concretas sean a la vez expertos conocedores de los diversos paradigmas de programacion paralela existentes. Esta tesis investiga un enlace entre la disciplina de la ingenieria mecanica y la computacion, ofreciendo a usuarios no expertos en paralelismo un software que incorpora el estudio y optimizacion de algoritmos mediante una adecuada seleccion de librerias y su configuracion. Partiendo del modelo de un sistema multicuerpo expresado en forma de grafo aciclico de los calculos (basicamente operaciones de algebra matricial) y sus dependencias, el software permite a un usuario ajustar los parametros de paralelismo y librerias, y realizar simulaciones del modelo para analizar la influencia que cada configuracion tiene en los tiempos de resolucion. Ademas, una ejecucion autooptimizada recomienda al usuario la manera mas eficiente de paralelizar los calculos, la libreria a usar y los ajustes teoricos optimos que se recomiendan para los parametros algoritmicos en cada etapa de resolucion del algoritmo. Por ultimo, esta metodologia se puede aplicar a otras disciplinas ajenas a la ingenieria mecanica, en concreto a aquellas donde los problemas se pueden plantear con un enfoque similar, es decir, como agrupaciones de calculos que incluyan operaciones matriciales realizadas en una determinada secuencia. Un ejemplo de aplicacion en este sentido lo encontramos en algunas rutinas basicas de algebra lineal, como la multiplicacion de matrices. EnglishModeling 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.