Quels sont les avantages et les inconvénients des algorithmes de décomposition de particules et de parallélisation de décomposition de domaine?

J'exécute des simulations de dynamique moléculaire (MD) en utilisant plusieurs progiciels, comme Gromacs et DL_POLY.

Gromacs prend désormais en charge les algorithmes de décomposition des particules et de décomposition de domaine. Par défaut, les simulations Gromacs utilisent la décomposition de domaine, bien que pendant de nombreuses années, jusqu'à récemment, la décomposition des particules était la seule méthode mise en œuvre dans Gromacs. Dans l'un des articles de Gromacs (DOI 10.1002 / jcc.20291), les auteurs expliquent leur choix initial de décomposition des particules:

"Une décision de conception précoce a été le choix de travailler avec la décomposition des particules plutôt que la décomposition des domaines pour répartir le travail sur les processeurs. Dans ce dernier cas, les domaines spatiaux sont attribués aux processeurs, ce qui permet de trouver rapidement des voisins spatiaux uniquement par communication locale, mais des complications dues aux particules qui se déplacent au-delà des limites spatiales sont considérables. La décomposition de domaine n'est un meilleur choix que lorsque la taille du système linéaire dépasse considérablement la plage d'interaction, ce qui est rarement le cas en dynamique moléculaire. Avec la décomposition des particules, chaque processeur calcule les forces et les mises à jour de coordonnées / vitesses pour une fraction assignée des particules, en utilisant une liste de voisins précalculée également répartie sur les processeurs. résultant de l'interaction de paire entre les particules i et j , qui est nécessaire pour la mise à jour de la vitesse des particules i et $F_{ij}$$i$$j$$i$$j$, est calculé une seule fois et communiqué aux autres processeurs. Chaque processeur conserve dans sa mémoire locale l'ensemble complet de coordonnées du système plutôt que de limiter le stockage aux coordonnées dont il a besoin. Ceci est plus simple et économise les frais de communication, tandis que la revendication de mémoire n'est généralement pas un facteur limitant du tout, même pour des millions de particules. La liste de voisins, en revanche, qui peut contenir jusqu'à 1000 fois le nombre de particules, est répartie sur les processeurs. La communication est essentiellement limitée à l'envoi de coordonnées et de forces une fois par pas de temps autour de l'anneau du processeur. Ces choix se sont révélés robustes dans le temps et facilement applicables aux clusters de processeurs modernes. "

Que signifient-ils par "taille du système linéaire" dans la phrase "La décomposition de domaine est un meilleur choix uniquement lorsque la taille du système linéaire dépasse considérablement la plage d'interaction, ce qui est rarement le cas en dynamique moléculaire"? Du paragraphe ci-dessus, j'ai l'idée que la décomposition des particules a l'avantage de ne pas avoir à faire face à des particules se déplaçant à travers les limites du domaine; il vous suffit plutôt d'avoir suffisamment de mémoire pour chaque processeur pour stocker la configuration totale du système. La décomposition des particules semble donc très favorable, tandis que la décomposition du domaine semble très défavorable.

Je suis sûr que c'est une question très compliquée (et probablement le sujet de nombreux livres), mais simplement, si la décomposition des particules semble si favorable, pourquoi quelqu'un aurait-il besoin d'utiliser la décomposition de domaine? La décomposition de domaine est-elle juste favorable si la taille du système est très grande (ce qui rend difficile ou impossible de stocker la configuration totale dans chaque processeur)? Sur la base du paragraphe cité ci-dessus, je ne sais pas pourquoi la décomposition de domaine est maintenant, tout récemment, l'algorithme de parallélisation par défaut dans Gromacs.

Il semble que DL_POLY maintenant (version 4) utilise également la décomposition de domaine. Du manuel de la version 4:

"La division des données de conguration de cette manière est basée sur l'emplacement des atomes dans la cellule de simulation, une telle allocation géométrique des données du système est la marque des algorithmes DD. Notez que pour que cette stratégie fonctionne efficacement, la simulation Le système doit posséder une densité raisonnablement uniforme, de sorte que chaque processeur se voit allouer presque autant de données atomiques (autant que possible). Grâce à cette approche, le calcul des forces et l'intégration des équations de mouvement sont partagés (raisonnablement) également entre les processeurs et dans une large mesure, peut être calculé indépendamment sur chaque processeur.La méthode est conceptuellement simple mais difficile à programmer et est particulièrement adaptée aux simulations à grande échelle, où l'efficacité est la plus élevée.

...

Dans le cas de la stratégie DD, l'algorithme SHAKE (RATTLE) est plus simple que pour la méthode des données répliquées de DL_POLY Classic), où des mises à jour globales des positions des atomes (fusion et épissage) sont nécessaires. "

Cela donne l'impression que la décomposition de domaine est bonne car elle peut être plus efficace, même si elle est peut-être plus difficile à implémenter.

D'un autre côté, une version précédente (DL_POLY Classic) utilisait la parallélisation des données répliquées, ce qui semble être un autre nom pour la décomposition des particules. Du manuel de cette version:

$\textbf{r}_i$$\textbf{v}_i$$\textbf{f}_i$$N$atomes dans le système simulé, sont reproduits sur chaque nœud de traitement). Dans cette stratégie, la plupart des forces de calcul et d'intégration des équations de mouvement peuvent être partagées facilement et également entre les nœuds et dans une large mesure être traitées indépendamment sur chaque nœud. La méthode est relativement simple à programmer et est raisonnablement efficace. De plus, il peut être «réduit» pour fonctionner sur un seul processeur très facilement. Cependant, la stratégie peut être coûteuse en mémoire et avoir des frais généraux de communication élevés, mais dans l'ensemble, elle s'est avérée efficace sur une large gamme d'applications.

Ce paragraphe semble généralement cohérent avec le premier paragraphe de cette question, sauf qu'il dit que la décomposition des données / particules répliquées a des «frais généraux de communication élevés». Le paragraphe de l'article de Gromacs semble dire le contraire - que la décomposition des particules est préférable car elle a une surcharge de communication inférieure à la décomposition du domaine.

Avez-vous des pensées?

La décomposition des particules et des domaines est directement liée aux deux principales méthodes d'accélération des calculs de force pour les systèmes avec des interactions à portée limitée - les listes de voisins Verlet et les listes liées aux cellules. Si vous souhaitez entrer dans les détails, il y a un très joli livre d'Allen et Tildesley, intitulé Computer Simulation of Liquids , considéré par beaucoup comme la "bible" des études de dynamique moléculaire et de Monte Carlo. Ensuite, il y a la simulation numérique en dynamique moléculaire de Griebel, Knapek et Zumbusch, qui approfondit les différentes techniques d'implémentation parallèle de la DM.

$O(N^2)$$O(N)$

$O(N)$$O(N)$ $N$il évolue mieux. D'où l'argument de la taille linéaire. La méthode de décomposition de domaine est une extension simple de la méthode des listes liées de cellules - les cellules sont divisées entre différents CPU.

Le problème avec la décomposition de domaine est qu'il doit communiquer lorsque les particules se déplacent d'une cellule à une autre qui est prise en charge par un autre CPU. Cela pourrait devenir problématique à des températures de simulation plus élevées où les particules ont tendance à s'éloigner plus que leur position d'équilibre, ou lorsqu'il y a un flux de particules. De plus, les informations des cellules situées à la frontière du domaine doivent être transférées à chaque itération vers le ou les domaines voisins. Mais tout cela est une communication localement synchrone et pourrait être fait très efficacement.

Les données répliquées sont l'approche la plus simple, mais malheureusement, à chaque étape, toutes les informations de position et de vitesse doivent être synchronisées globalement. Cela n'évolue vraiment pas bien et pour un très grand système, la quantité globale de mémoire est la taille de la structure de données multipliée par le nombre de processeurs utilisés, tandis que l'un des objectifs du traitement parallèle est la distribution de données de telle sorte que chaque processeur détient moins que la quantité globale de données.

En résumé, il n'existe pas de méthode «taille unique», adaptée à tous les systèmes simulés. La plupart du temps, la meilleure stratégie de parallélisation peut être déduite de la géométrie du système et le code MD approprié pour ce cas peut être choisi - ils implémentent tous plus ou moins les mêmes champs de force sous-jacents et intégrateurs après tout.

Par "La décomposition de domaine n'est un meilleur choix que lorsque la taille du système linéaire dépasse considérablement la plage d'interaction, ce qui est rarement le cas en dynamique moléculaire", les auteurs de ce (très ancien) article GROMACS signifient que si la taille spatiale de la liste des voisins est de l'ordre de 1 nm, et la cellule de simulation n'est que de plusieurs nanomètres, alors le surcoût lié à la décomposition de domaine est trop élevé. Vous pouvez également accepter une distribution d'informations de tout-à-tout dans la décomposition des particules, et ne pas avoir besoin de passer du temps sur toute la comptabilité pour la décomposition de domaine.

Le problème de la décomposition des particules lors de la mise en œuvre de GROMACS était que, au fil du temps, les particules attribuées à chaque processeur diffusaient dans l'espace. La responsabilité du calcul de chaque interaction étant fixée par leur emplacement initial, la diffusion augmente progressivement le volume de l'espace total que chaque processeur doit connaître pour construire sa liste de voisins, même si le calcul total décrit par la liste de voisins est constant. En pratique, vous devez relancer périodiquement la simulation pour réinitialiser la localité de données et de communication.

Votre supposition selon laquelle "la décomposition des particules a l'avantage de ne pas avoir à traiter avec des particules se déplaçant à travers les limites du domaine" ne tient pas si la diffusion est significative sur l'échelle de temps de la simulation.

La décomposition de domaine gère ce "front" en migrant la responsabilité de l'interaction avec la diffusion, améliorant ainsi la localisation des données sur chaque processeur et minimisant le volume de communication.

Avertissement: j'aide au développement de GROMACS, et j'arracherai probablement la mise en œuvre de la décomposition des particules la semaine prochaine ;-)

Je voudrais compléter la réponse de Hristo Iliev. Alors que son article parle principalement de la complexité de calcul , en ce qui concerne la parallélisation, la complexité de la communication est au moins aussi importante - et que c'est la principale raison de la décomposition du domaine.

Les machines parallèles modernes ont généralement une sorte de topologie en tore. Cela signifie que chaque CPU possède un certain nombre de CPU "voisins" avec lesquels elle peut communiquer très rapidement. Communiquer avec un CPU qui n'est pas un voisin est plus coûteux. Par conséquent, il est toujours avantageux d'avoir un algorithme qui n'a besoin que de communiquer avec les CPU voisines.

$P$$\mathcal{O}(P^2)$

$P$$\mathcal{O}(P)$

$\mathcal{O}(P)$

Notez, cependant, que les systèmes non uniformes ne sont pas aussi courants que cela puisse paraître, ils ne se produisent que lors de la simulation de quelque chose dans le vide, ou lors de l'utilisation d'un solvant implicite. Les densités de cristaux et de liquides sont suffisamment proches pour permettre la décomposition du domaine.