Le Galerkin discontinu est-il vraiment plus parallélisable que le Galerkin continu?

J'ai toujours entendu que la parallélisation facile était l'un des avantages des méthodes DG, mais je ne vois pas vraiment pourquoi aucune de ces raisons ne s'applique également à Galerkin continu.

Une raison pour laquelle les méthodes DG peuvent recevoir plus d'attention en tant que méthode parallèle est qu'il est facile de voir que la méthode est intrinsèquement locale à un élément. Le couplage dans les méthodes DG est faible, car il ne se produit que par les bords adjacents (ou les faces en 3D). Ainsi, pour les triangles ou les quads, DG communiquera à trois ou quatre processeurs au maximum, respectivement. Alors que les méthodes CG incluront les coins des éléments, la valence du coin d'un élément devient donc importante. Selon le générateur de maillage utilisé, cette valence peut être de huit processeurs (éventuellement plus élevée). Ainsi, le coût d'assemblage de la dérivée temporelle peut être considéré comme "plus élevé" pour les méthodes CG. Cela est particulièrement préoccupant pour les méthodes spectrales, où le volume d'informations à communiquer peut être assez important (et le masquage de la latence peut devenir plus difficile à mesure que la taille de chaque partition diminue).

Mais ce coût supplémentaire pour CG d'assembler son dérivé temporel pourrait être compensé par une stratégie d'équilibrage de charge différente. Différentes stratégies de partitionnement de maillage (je suis le plus familier avec METIS) permettent à l'utilisateur d'équilibrer la charge à travers diverses mesures, par exemple, en s'assurant que chaque partition possède approximativement le même nombre d'éléments ou en limitant la quantité de communication entre les partitions. Je pense que le colloquisium de DG étant facilement parallélisable est qu'une division naïve du problème en morceaux égaux peut donner une implémentation parallèle très efficace, même en présentant une accélération super linéaire dans certains cas en raison des effets de cache (voir par exemple Baggag et al. . ou Altmann et al..). Alors que CG peut nécessiter une méthode de partitionnement plus intelligente. Il se peut donc que le changement de discrétisation spatiale de DG en CG, par exemple, nécessite de reconsidérer également la manière de diviser le maillage en sous-problèmes.

D'après mes nombreuses années à écrire des logiciels FEM, je pense que l'affirmation selon laquelle les schémas DG sont mieux adaptés à la parallélisation que les schémas CG est apocryphe. Il est fréquemment utilisé dans les introductions de documents DG pour justifier les méthodes DG, mais je ne l'ai jamais vu corroboré par une référence qui a réellement enquêté sur la question. Il est similaire à chaque proposition de la NSF sur un projet de théorie des nombres faisant référence à la "cryptographie" en tant que domaine d'impact plus large, une déclaration qui, dans cette généralité, n'est également jamais étayée.

En fait, je pense qu'à l'exception des schémas de progression de temps explicites et, éventuellement, des problèmes où vous devez inverser une matrice de masse, les schémas DG ne sont ni meilleurs ni pires que les schémas CG si l'on examine le coût de la communication impliqué dans l'un ou l'autre. Je veux dire que cela a un sens pratique: bien sûr, il se peut que l'on doive communiquer moins de données, mais j'imagine que la différence de temps d'horloge murale est négligeable par rapport à tous les autres programmes d'exploitation sur ces données.

Bien sûr, je serais ravi si quelqu'un relevait le défi de me prouver le contraire!

Tout comme c'est le cas avec la plupart des déclarations générales sur les schémas numériques, la réponse dépend des circonstances exactes que vous regardez. Tout d'abord, les avantages de la DG en matière de parallélisation sont principalement payants dans le cas de schémas explicites d' intégration

• La matrice de masse cellule-locale des schémas DG (vous n'avez donc pas à appliquer l'inverse de la matrice de masse globalement)
• Un rapport favorable du travail CPU-local (intégrales de volume) au travail lié à la communication (intégrales de bord), en particulier pour les commandes plus élevées

Bien que ces déclarations s'appliquent aux discrétisations génériques DG, les applications HPC réelles (par exemple, en utilisant plusieurs milliers de processeurs) nécessitent un effort supplémentaire concernant la stratégie de parallélisation afin de maintenir une bonne mise à l'échelle. Cet article montre, par exemple, comment on peut obtenir une mise à l'échelle presque parfaite jusqu'à une cellule par processeur . C'est certainement quelque chose que vous ne pouvez pas attendre d'un MEF continu, mais comme mentionné précédemment, les schémas implicites sont une chose totalement différente.

Lors de l'assemblage d'une matrice de rigidité, les données stockées dans un élément en FEM continue (nodale) doivent être communiquées à tous ses voisins nodaux. En revanche, DGFEM exige que les données d'élément soient communiquées à tous ses voisins de face. En 1D, les voisins nodaux et de face sont identiques, mais en 3D, la différence peut être assez grande: pour un maillage hexaédrique régulier, il y a 26 voisins nodaux mais seulement 6 voisins de face. Pour les maillages irréguliers avec de nombreux sommets à haute valence, la situation empire pour CG, alors qu'elle reste la même pour DG.

La DG pour l'EDP hyperbolique peut être utilisée en remplacement des schémas de volumes finis. En volume fini comme en différence finie, lorsque vous augmentez l'ordre du schéma, votre pochoir augmente. Cela rend la parallélisation plus difficile, car pour chaque ordre de schéma, vous avez un gabarit différent. Aux limites de la partition, vous devez vous assurer que toutes les cellules requises de la partition voisine pour l'ordre particulier du schéma sont disponibles. Mais avec DG, quel que soit l'ordre du schéma, chaque cellule ne communique qu'avec ses voisins de visage. Donc, comparé entre volume fini / différence et DG, on peut dire que le DG est plus facile à paralléliser.