Paral·lelització de métodes de diferències finites: solucions nodals i mimétiques de l'equació d'ona

Estudio del rendimiento de una aplicación que resuelve un problema numérico utilizando el método nodal y mimético. Implementación de nuevas versiones (secuenciales y paralelas).In the present work we analyze two finite difference methods for the propagation of acoustic waves proposed by Córdova et al. to optimize its performance. The computational domain is rectangular. The first of these methods uses a nodal grid and traditional compact finite differences that imply solving tridiagonal systems for numerical differentiation. The second method applies mimetic differential operators in explicit form in a center-distributed grid, avoiding the need to solver linear systems of equations. Starting from a basic MATLAB implementation of both methods, we study their algorithmic complexity and attempt a first optimization of the reference code. Then several optimization strategies are explored. We develop a single--threaded C++ version and then build an OpenMP version to exploit multithread parallelism. Massive parallelization strategies are implemented in a GPU accelerated version using CUDA. Finally, we perform a comparative study of the methods and their behavior towards different optimization strategies. Each optimization technique used is optimal for a certain range of problem sizes. By combining the options developed in this work, it is possible to obtain an execution time speedup between 10-28x (nodal method) and 18-50x (mimetic method) for the whole range of usable problem sizes.En el presente trabajo se analizan dos métodos en diferencias finitas para la propagación de ondas acústicas propuestos por Córdova et al. con el objeto de optimizar su rendimiento. El domino computacional es rectangular, y el primero de estos métodos emplea una malla nodal y diferencias finitas compactas tradicionales que implican la resolución de sistemas tridiagonales para la diferenciación numérica. El segundo método aplica en forma explicita operadores miméticos de diferenciación en una malla centro-distribuida, y así evita la solución de sistemas lineales. Partiendo de una implementación básica para MATLAB de los métodos propuestos, se analiza la complejidad numérica y se intenta optimizar el código original. A partir de esta implementación de referencia se exploran diversas estrategias de optimización. Primeramente se desarrolla una versión en C++ para una sola CPU y a partir de esta implementación se explota el paralelismo mediante una versión multihilo usando la tecnología OpenMP. Seguidamente se exploran las posibilidades de paralelización masiva mediante el cálculo acelerado por GPU con CUDA. Finalmente se presenta un estudio comparativo de los distintos métodos y su comportamiento con las diferentes optimizaciones usadas. Cada técnica de optimización utilizada resulta óptima para un rango de tamaños de problema. Combinando las diferentes opciones desarrolladas en el presente trabajo, es posible obtener una aceleración del tiempo de ejecución de entre 10-20x (método nodal) y 28-50x (método mimético) para todo el rango usable de tamaños de problema.En el present treball s'analitzen dos mètodes en diferències finites per a la propagació d'ones acústiques proposats per Córdova et~al. amb l'objectiu d'optimitzar-ne el rendiment. El domini computacional és rectangular, i el primer d'aquests mètodes fa servir una malla nodal i diferències finites compactes tradicionals que impliquen la resolució de sistemes tridiagonals per la diferenciació numèrica. El segon mètode aplica en forma explícita operadors mimètics de diferenciació en una malla centre-distribuïda, evitant d'aquesta manera la resolució de sistemes lineals. Partint d'una implementació bàsica per MATLAB dels mètodes proposats, s'analitza la complexitat numèrica i s'intenta optimitzar el codi original. A partir d'aquesta implementació de referència explorem diverses estratègies d'optimització. Primerament es desenvolupa una versió en C++ per a una sola CPU i a partir d'aquesta implementació s'explota el paral·lelisme mitjançant una versió multifil emprant la tecnologia OpenMP. Seguidament s'exploren les possibilitats de paral·lelització massiva mitjançant el càlcul accelerat per GPU amb CUDA. Finalment es presenta un estudi comparatiu dels diferents mètodes i el seu comportament enfront de les diferents optimitzacions emprades. Cada tècnica d'optimització resulta òptima per a un rang de mides del problema. Combinant les diferents opcions desenvolupades en el present treball, es possible obtenir una acceleració del temps d'execució entre 10-28x (mètode nodal) i 28-50x (mètode mimètic) per a tot el rang de mides usables