6.2.5 : Sur quelles architectures

Il est usuel de dire que la méthode brute force est plus efficace sur GPU que la méthode qui utilise les octree sur CPU. Il est tout de même important de rappeler un élément essentiel : cela dépend du nombre de particules que l'on simule.

Pour que la parallélisation (en terme de coeurs CPU ou de coeurs GPU) soit efficace tous les coeurs disponibles doivent être utilisés le plus souvent possible. Ce qui implique qu'ils doivent avoir quelque chose à calculer.

Si on traite $N$ particules avec $M$ coeurs :

  • Si $N < M$ on est bien embété car on a trop de coeurs pour traiter pas assez de particules. Dans ce cas il est possible de paralléliser le calcul en temps et non en espace. Une présentation du Forum ORAP du 26/11/2020 aborde le sujet. La video Prix EDF Paul Caseau : Space-Time Parallel Strategies for the Numerical Simulation of Turbulent Flows (10'') Thibaut Lunet (University of Geneva) (c'est la présentation juste après l'introduction de 5 minutes)
  • Si $N = M$ la méthode brute force résoudra le problème en $N^2$ opération tandis que la méthode à base d'octree le fera en $\log_8 N$ opérations (la encore il convient de préciser que cette dernière estimation de la complexité du calcul par du principe que les particules sont réparties équitablement dans l'espace, si ce n'est pas le cas, la méthode brute force peut, dans certains cas, être plus efficace)
  • Si $N > M$ dans ce cas, la complexité ne change pas, $N^3$ pour le force brute et $N\log_8 N$ si les particules sont equi-réparties dans l'espace.
  • Si $N >> M$ la complexité de la méthode force brute la rend completement inutilisable et il convient de découper l'espace avec des octree et ensuite dispatcher les calculs sur tous les coeurs disponibles (en découpant plus ou moins en fonction de la mémoire disponibe des CPU et des GPU à disposition)


Note : une chose importante est de dire qu'il est préférable de paralléliser les calculs de manière asynchrone, car, même si le traitement d'une particule prend a priori toujours le même temps avec la méthode brute force il sera très différent avec la méthode par octree, un thread lent ne doit donc pas être attendu par les autres tant qu'il reste des particules à traiter.