Optimization and parallelization of the boundary element method for the wave equation in time domain

La méthode des éléments frontières pour l’équation des ondes (BEM) est utilisée en acoustique eten électromagnétisme pour simuler la propagation d’une onde avec une discrétisation en temps(TD). Elle permet d’obtenir un résultat pour plusieurs fréquences à partir d’une seule résolution.Dans cette thèse, nous nous intéressons à l’implémentation efficace d’un simulateur TD-BEM sousdifférents angles. Nous décrivons le contexte de notre étude et la formulation utilisée qui s’exprimesous la forme d’un système linéaire composé de plusieurs matrices d’interactions/convolutions.Ce système est naturellement calculé en utilisant l’opérateur matrice/vecteur creux (SpMV). Nousavons travaillé sur la limite du SpMV en étudiant la permutation des matrices et le comportementde notre implémentation aidé par la vectorisation sur CPU et avec une approche par bloc surGPU. Nous montrons que cet opérateur n’est pas approprié pour notre problème et nous proposonsde changer l’ordre de calcul afin d’obtenir une matrice avec une structure particulière.Cette nouvelle structure est appelée une matrice tranche et se calcule à l’aide d’un opérateur spécifique.Nous décrivons des implémentations optimisées sur architectures modernes du calculhaute-performance. Le simulateur résultant est parallélisé avec une approche hybride (mémoirespartagées/distribuées) sur des noeuds hétérogènes, et se base sur une nouvelle heuristique pouréquilibrer le travail entre les processeurs. Cette approche matricielle a une complexité quadratiquesi bien que nous avons étudié son accélération par la méthode des multipoles rapides (FMM). Nousavons tout d’abord travaillé sur la parallélisation de l’algorithme de la FMM en utilisant différentsparadigmes et nous montrons comment les moteurs d’exécution sont adaptés pour relâcher le potentielde la FMM. Enfin, nous présentons des résultats préliminaires d’un simulateur TD-BEMaccéléré par FMM .The time-domain BEM for the wave equation in acoustics and electromagnetism is used to simulatethe propagation of a wave with a discretization in time. It allows to obtain several frequencydomainresults with one solve. In this thesis, we investigate the implementation of an efficientTD-BEM solver using different approaches. We describe the context of our study and the TD-BEMformulation expressed as a sparse linear system composed of multiple interaction/convolutionmatrices. This system is naturally computed using the sparse matrix-vector product (SpMV). Wework on the limits of the SpMV kernel by looking at the matrix reordering and the behavior of ourSpMV kernels using vectorization (SIMD) on CPUs and an advanced blocking-layout on NvidiaGPUs. We show that this operator is not appropriate for our problem, and we then propose toreorder the original computation to get a special matrix structure. This new structure is called aslice matrix and is computed with a custom matrix/vector product operator. We present an optimizedimplementation of this operator on CPUs and Nvidia GPUs for which we describe advancedblocking schemes. The resulting solver is parallelized with a hybrid strategy above heterogeneousnodes and relies on a new heuristic to balance the work among the processing units. Due tothe quadratic complexity of this matrix approach, we study the use of the fast multipole method(FMM) for our time-domain BEM solver. We investigate the parallelization of the general FMMalgorithm using several paradigms in both shared and distributed memory, and we explain howmodern runtime systems are well-suited to express the FMM computation. Finally, we investigatethe implementation and the parametrization of an FMM kernel specific to our TD-BEM, and weprovide preliminary results