An Algorithm for the lattice Boltzmann method adapted to sparse geometries and distributed memory systems

Dans cette thèse, une modification de l’algorithme de la méthode de Boltzmann sur réseau est effectuée pour obtenir de meilleures performances et par conséquent moins de temps d’exécution. L’objectif principal du projet est d’améliorer les algorithmes de Boltzmann sur réseau actuels et d’en créer un qui fonctionnera efficacement sur des systèmes à mémoire distribuée ainsi qu’avec un seul processeur, et ce, pour simuler de grands systèmes avec des géométries irrégulières. L’idée suivie dans la thèse est d’éviter d’emmagasiner les données des noeuds solides. L’autre amélioration de l’algorithme de Boltzmann sur réseau consiste à parcourir en une seule passe toutes les fonctions de distribution de probabilité afin d’effectuer les étapes de collision et de propagation en même temps. Ainsi, comme une des boucles principales est sur les fonctions de distribution de probabilité, il est possible d’utiliser un tableau de structures pour simplifier la mise en oeuvre de l’étape de propagation. En considérant les difficultés d’implémentation des conditions aux limites avec la méthode de Boltzmann sur réseau, un nouvel environnement est développé pour simplifier la mise en oeuvre des conditions limites. Une autre idée dans cette thèse est de concevoir un nouvel algorithme pour la communication de l’interface de passage de messages (MPI en anglais) de telle manière qu’au niveau de la programmation, il serait possible de cacher la couche de programmation parallèle des parties du code en série. Cependant, toute l’implémentation et la vérification sont faites pour des cas bidimensionnels. En suivant les idées mentionnées pour atteindre les objectifs du projet, un nouvel algorithme de Boltzmann sur réseau a été introduit qui utilise une disposition de mémoire simple. Comme les étapes de collision et de propagation sont effectuées en même temps, la localité des données est augmentée. Par conséquent, un simple décalage des données est utilisé pour effectuer l’étape de propagation. En évitant d’emmagasiner les noeuds solides, l’algorithme proposé est adapté aux systèmes à faible taux de vide. De cette manière, outre la diminution de l’utilisation de la mémoire, comme aucun calcul n’est effectué pour les noeuds solides, les ressources de calcul sont également utilisées efficacement. Pour vérifier le code implémenté et basé sur l’algorithme mentionné, plusieurs cas tests académiques sont simulés, notamment l’écoulement de Poiseuille, l’écoulement dans une cavité et l’écoulement autour d’un cylindre. L’algorithme proposé utilise la même quantité de mémoire que l’algorithme à deux réseaux, mais plus que l’algorithme à deux étapes. Puisqu’il utilise un schéma d’adressage indirect, il est néanmoins plus efficace en termes d’utilisation de la mémoire, en particulier pour les géométries à faible taux de vide. Comme les données des noeuds solides ne sont pas emmagasinées dans cette méthode, il n’y a pas de calcul pour ces types de noeuds, ce qui entraîne par conséquent de meilleures performances pour les géométries irrégulières avec de faibles taux de vide. En tenant compte des difficultés de mise en oeuvre des conditions limites, un nouvel environnement est introduit pour mettre en oeuvre de nouvelles conditions limites. Dans cet environnement, une condition limite est mise en oeuvre pour un seul côté/coin d’un domaine, puis appliquée aux autres côtés/coins de manière automatique. Ainsi, comme les formulations habituelles d’une condition limite dépendent de l’orientation des noeuds frontière, l’utilisation de cet environnement réduit le nombre d’implémentations, ce qui facilite l’implémentation des conditions limites typiques de la méthode de Boltzmann sur réseau. L’une des principales contributions de ce travail est le concept d’application de l’opération de décalage circulaire et de retournement de données sur un tableau de structure pour projeter les fonctions de distribution de probabilité de n’importe quel bord/coin vers le noeud frontière gauche/inférieur-gauche. Pour vérifier l’environnement, plusieurs des conditions limites communes de la méthode Boltzmann sur réseau ont été mises en oeuvre, puis vérifiées à l’aide de références bien connues dans le domaine de la méthode de Boltzmann sur réseau.

Abstract

In this thesis, a modification of the Lattice Boltzmann Method (LBM) algorithm is done to achieve better performance and consequently less execution time. The main objective of the project is to improve upon the current LBM algorithms and create one that will work efficiently with distributed memory systems as well as with a single processor to simulate large systems with irregular geometries. The idea followed in the thesis is to avoid storing the solid node data. The other improvement on the LBM algorithm is to traverse all the Probability Distribution Functions (PDF) to perform both the streaming and collision steps at the same time. So, as the loop is on the PDFs it is possible to use a structure-of-array memory layout to simplify the streaming step implementation. By considering the difficulties of the Boundary Condition (BC) implementation, a new framework is provided to simplify the BC implementation. Another idea that is followed in this thesis is designing a new algorithm for Message Passing Interface (MPI) communication in such a way that, at the programming level, it would be possible to hide the parallel programming layer from serial parts of the code. However, all the implementation and verification are done for 2D. By following the mentioned ideas to reach the objectives of the project, a new LBM algorithm was introduced to use a simple memory layout. As the streaming and collision steps are done at the same time, the data locality is increased. Hence, a simple shift is used to do the streaming step. By avoiding storing the solid nodes the proposed algorithm is suitable for low void fraction systems. In this way, apart from the decrease in memory usage, as no computation is done for solid nodes the computational resources are used efficiently also. To verify the implemented code based on the mentioned algorithm several academic benchmarks, including Poiseuille flow, Cavity flow, and Cylinder flow, are simulated. Then the performance of the code is investigated by simulation of dense and sparse systems. This algorithm uses the same amount of memory as the two-lattice but more than the two-step algorithm. Since it uses an indirect addressing scheme, it is nevertheless more efficient in terms of memory usage, particularly for low void fraction geometries. As the data of the solid nodes are not stored in this method, there is no computation for these kinds of nodes, which consequently results in better performance for irregular geometries with low void fractions. By considering the difficulties of BC implementation a framework is introduced to implement new BCs. In this framework, a BC is implemented for only one side/corner of a domain and then applied to the other sides/corners. So, as the usual formulations of a BC are dependent on the orientation of the boundary nodes, using this framework reduces the number of implementations, making it easier to implement typical LBM BCs. One of the core contributions of this work is the concept of applying the circular shift and flip operation over an AoS data layout to map the PDFs of any edge/corner to the left/bottom-left boundary node. To verify the framework, several of the common BCs in the LBM were implemented, then verified using well-known benchmarks in the LBM field.