Compiler and runtime support for the execution of scientific codes with unstructured datasets on heterogeneous parallel architectures

Las simulaciones computacionales basadas en la discretización temporal y espacial para la resolución de sistemas de ecuaciones en derivadas parciales se utilizan hoy en día en sectores industriales de gran relevancia económica. Un ejemplo significativo de dichas aplicaciones son las simulaciones de dinámica de fluidos. Estas simulaciones se utilizan constantemente en industrias tales como la aeronáutica o la automoción. Más recientemente, se han identificado nuevos campos de aplicación como la simulación del torrente sanguíneo para el diagnóstico médico, o el diseño de turbinas eólicas para la generación de energía. La complejidad de dichas simulaciones y el propio tamaño de los conjuntos de datos usados hacen que requieran de una capacidad de procesamiento considerable si se quieren obtener resultados en un tiempo razonable. En los últimos años, la optimización de estas aplicaciones se ha convertido en una prioridad para diversos organismos, hasta el punto de considerar aplicaciones en tiempo real como un objetivo a largo plazo. Estas simulaciones han venido usando recursos de Computación de Altas Prestaciones (HPC, por sus siglas en inglés), los cuales obtienen aceleraciones razonables mediante el particionado de datos y su ejecución en múltiples procesadores. Aún así, la necesidad de ejecutarlas en el menor tiempo posible, el crecimiento de los conjuntos de datos para incrementar la exactitud de los resultados, y las limitaciones de escalabilidad de los códigos de CFD, han motivado la aparición de iniciativas conjuntas entre varios países, con el objetivo de conseguir los objetivos de rendimiento y tamaño, siempre en crecimiento, a través de tecnologías novedosas e incluso disruptivas. La presente tesis aborda el tema de la optimización de dichos códigos con la ayuda de sistemas heterogéneos de altas prestaciones. Dichos sistemas se diferencian de los sistemas homogéneos en el hecho de que las arquitecturas de sus elementos de procesamiento son distintas entre sí. Se pone un especial énfasis en el análisis de viabilidad en el uso de FPGAs en dichos sistemas como aceleradores para simulaciones científicas. Al estar estos dispositivos basados en hardware reconfigurable, permiten un grado más fino de paralelismo que los procesadores de propósito general, lo cual se traduce en un incremento del rendimiento de las porciones de código más relevantes cuando éstas se asignan a la FPGA. Por otra parte, las FPGAs obtienen unos niveles de eficiencia energética muy por encima de cualquier otro dispositivo de cómputo disponible hoy en día. Por desgracia, la novedad de este tipo de propuestas también significa que el esfuerzo de desarrollo requerido para implementarlas es todavía significativamente superior a otras tecnologías más establecidas, como por ejemplo las GPUs de propósito general (GPGPUs, por sus siglas en inglés). Las FPGAs también muestran limitaciones a la hora de manejar datos procedentes de memorias externas. Debido a las características de las dependencias en los conjuntos de datos utilizados en muchas de las aplicaciones CFD, este problema podría suponer la no idoneidad de las FPGAs como alternativa para optimizar dichas aplicaciones. Por ello, es de vital importancia asegurarse de optimizar las transferencias de datos en profundidad, de forma que la alta capacidad de cómputo de la FPGA no se vea limitada por sus capacidad de transferencia, relativamente pobre si se compara con otros dispositivos de procesamiento. Los algoritmos, metodologías y librerías de software presentados a lo largo de la Tesis están enfocadas a la mejora de la transferencia de datos de códigos CFD en arquitecturas paralelas heterogéneas con aceleradores FPGA, tratando de reducir al mismo tiempo el coste de implementación de dichos sistemas. Específicamente, se propone una metodología de reducción del tamaño de los conjuntos de datos y de transferencia desde y hacia la FPGA, así como dos propuestas de automatización para la paralelización de códigos enfocada a sistemas heterogéneos y basadas en compiladores con la asistencia de librerías de comunicación, la primera de las cuales está basada en la distribución del flujo de control, mientras que la segunda se basa en el pipelining de secuencias de bucles. Éstas últimas son técnicas a nivel de sistema, y por tanto son independientes de las arquitecturas presentes en el sistema heterogéneo. A pesar de que el propósito original del trabajo era la optimización de simulaciones de dinámica de fluidos, se ha observado que las técnicas propuestas son aplicables a un conjunto de problemas más general. En el futuro, muchos sistemas HPC podrían beneficiarse de la tecnología disponible en las FPGAs de la misma forma en la que se benefician actualmente de las GPUs, con los beneficios adicionales de rendimiento y consumo energético que ofrece el hardware reconfigurable. ----------ABSTRACT---------- Simulation codes based in the discretization of time and space for solving systems of partial differential equations are used nowadays in relevant industrial sectors. These include, for example, finite volumes and finite element methods typically used in Computational Fluid Dynamics (CFD). These simulation applications are widely used various industries such as aeronautics, automotive or weather prediction. More recently, they have been used in novel applications such as the simulation of blood streams for medical diagnosis, or the design of wind turbines for energy generation. The complexity of these simulations and the sheer size of the datasets used often require a considerable amount of computing power in order to obtain results in a reasonable time. In the last years, the optimization of these applications has been a priority for many companies, and even real time performance is now often considered as a stretch goal for optimization attempts. High Performance Computing (HPC) systems have been used for some time now to run these simulations, achieving reasonable speedups by partitioning the datasets and running the simulation in several processors. However, the need to run them in as little time as possible, the increase in the dataset sizes to allow for higher accuracy, and limitations in the multi-process scalability of CFD simulations, have resulted in joint worldwide efforts to achieve the ever-increasing performance and problem size objectives by means of newer, disruptive technologies. This thesis approaches the problem of optimizing the execution of these codes with the help of Heterogeneous HPC systems. These systems differ from standard, homogeneous HPC systems in that the architectures of the processing elements used as building blocks differ from each other. A special interest of this work is to analyze the feasibility of using Field-Programmable Gate Arrays (FPGAs) in these systems as accelerators to scientific simulations. Because these devices are essentially reconfigurable hardware, they allow a finer-grain parallelism than general-purpose processors, which translates into a higher throughput when computational kernels are ported to them. Additionally, FPGAs achieve levels of power efficiency that are currently unparalleled by any existing mainstream computing device. Unfortunately, the novelty of this approach implies that the programming effort required to implement such solutions is still high compared to other well-known accelerating technologies such as General-Purpose Graphics Processing Units (GPGPUs). FPGAs also show limitations with external memory throughput. Due to the characteristics of data dependencies in the datasets used for these codes, this problem might render FPGAs useless for the optimization of such applications. A deep optimization of the data transfer mechanisms is vital to ensure that the high-performance capabilities of these reconfigurable devices are not shadowed by their lower input/output capabilities as compared to other existing processing devices. The algorithms, methodologies and software libraries introduced throughout this Thesis improve data transfer of the aforementioned codes in FPGA-based parallel heterogeneous systems, while also reducing the development effort required to implement these. Specifically, we propose a methodology to reduce the size of the datasets and transfer them efficiently to the FPGA, as well as two compiler and runtime techniques to automate the parallelization of the codes suitable for heterogeneous systems, one focused on control flow distribution and another one based on pipelining of loop sequences. The latter are techniques at the system level, therefore they are independent from the architectures used in the heterogeneous system. Although the original purpose of this work was to optimize CFD simulations, it has become clear that the techniques proposed are applicable to a more general set of applications. In the future, HPC systems could use FPGAs in the same way that they now benefit from GPGPU tecnologies, but with the added benefits of reconfigurable hardware