Comment pourriez-vous paralléliser une simulation 2D boids

16

Comment pouvez-vous programmer une simulation de boids 2D de telle manière qu'elle puisse utiliser la puissance de traitement de différentes sources (clusters, GPU).

exemple boids

Dans l'exemple ci-dessus, les particules non colorées se déplacent jusqu'à ce qu'elles se regroupent (en jaune) et s'arrêtent de bouger.

Le problème est que toutes les entités pourraient potentiellement interagir les unes avec les autres bien qu'une entité en haut à gauche n'interagisse probablement pas avec une en bas à droite. Si le domaine était divisé en différents segments, cela pourrait accélérer le tout, mais si une entité voulait traverser un autre segment, il pourrait y avoir des problèmes.

Pour le moment, cette simulation fonctionne avec 5000 entités avec une bonne fréquence d'images, je voudrais essayer avec des millions si possible.

Serait-il possible d'utiliser des arbres quadruples pour optimiser davantage cela? D'autres suggestions?

Sycren
la source
Demandez-vous une optimisation ou comment paralléliser? Ce sont des choses différentes.
bummzack
@bummzack Comment paralléliser, je viens d'ajouter des explications supplémentaires, est-ce que cela aide?
Sycren

Réponses:

7

La thèse de maîtrise Simulation parallèle de fluides de particules par Mattias Linde pourrait offrir un aperçu du partitionnement des données et des algorithmes pour la simulation à grande échelle.

Son article est axé sur l' hydrodynamique des particules lissées , qui pour la solution naïve a tendance à utiliser le hachage spatial avec une taille de seau autour de la taille de l'empreinte du noyau des particules dans la simulation.

Comme la distance d'interaction est fortement limitée dans les noyaux SPH typiques, de telles optimisations de partitionnement sont presque essentielles dans la mise à l'échelle du système.

Lars Viklund
la source
beau papier, mais la partie précise de cette question semble être beaucoup comme la réponse @Fxlll.
Ali1S232
Je dirais que la partie réelle de l'article est de savoir comment il résout les cas marginaux en introduisant un protocole de communication, c'est la partie difficile, le partitionnement quadruple est assez évident et en soi ne résout pas le problème des cas marginaux.
Maik Semder
4

Le terme que j'ai appris il y a longtemps était la vitesse d'information d'un jeu.

Si la vitesse de vos boids est de 1 et qu'ils ne se soucient que de leurs voisins, alors la vitesse des informations est de 3, c'est-à-dire qu'un boid à deux carrés de vous pourrait être dans la plage dont vous vous souciez dans une même trame:

1 mouvement carré par boid dans l'interaction (1 + 1) plus la distance à laquelle vous pouvez remarquer des choses (1) est égale à 3.

Compte tenu de cela, nous apprenons que nous pouvons découper une carte en morceaux, de la taille aussi petite que nous le souhaitons, mais avec cette vitesse d'information se chevauchent dans les morceaux voisins.

Je suppose que vous autorisez vos boids à se déplacer d'un seul carré, mais ils peuvent voir trois

Si vous souhaitez exécuter une simulation parallèle massive, vous vous divisez en grilles de 10 x 10, mais vous vous chevauchez de 5 carrés sur chaque bord. Chaque fois que l'un de vos contacts se trouve à la distance d'informations du bord du bloc local, vous devez mettre à jour le voisin et une fois qu'il a traversé la frontière, il ne vous appartient pas. Si un voisin dit qu'un boid qu'il contrôle s'est déplacé dans votre bloc, vous devez prendre le contrôle de son IA.

Cela signifie que la communication est localisée vers les gestionnaires de blocs voisins et que le trafic est réduit au minimum. Plus vous exécutez de travaux, plus vous pouvez utiliser de processeurs pour alimenter la simulation, mais plus vous exécutez de travaux, plus ils se chevauchent et, par conséquent, plus d'informations passent entre les travaux / blocs à mesure que la simulation progresse. C'est là que vous devez travailler dur et régler la taille des morceaux en fonction de la complexité de l'IA et du matériel dont vous disposez.

Richard Fabian
la source
imaginez que le monde est une grille de 1 000 000 x 1 000 000, et qu'il y a 10 000 000 de boids dans le monde, et que chaque boid peut se déplacer exactement d'un carré à chaque tour, pouvez-vous expliquer comment vérifier s'il y a un boid dans le voisinage d'un autre?
Ali1S232
Je suppose que nous pourrions le diviser en 2000 carrés 500x500 ou plus. chaque carré contient une liste de boids ainsi qu'une liste de voisins. Si un boid quitte un carré, il est supprimé de la liste des boids et ajouté à l'autre carré. Le problème avec cette méthode que je peux voir est que si vous ajoutez quelque chose avec un flocage qui est plus grand que le carré. la solution quadtree devrait être dynamique, mais je ne sais pas combien cela coûterait cher
Sycren
@Gajet: il vous suffit de vérifier les boids dans votre bloc ou les frontières gérées par le voisin. N'oubliez pas que la bordure est garantie par la conception pour tenir compte de la distance parcourue par une entité et de la distance que les entités peuvent voir. @Sycren: le flocage, même s'il nous semble être une grande entité, n'est encore qu'un effet à petite échelle. Un banc de poissons ne suit pas le banc, ils suivent leurs voisins observables.
Richard Fabian
2

En lisant votre question, il semble que vous puissiez profiter des arbres quadruples, créer un arbre quadruple et exécuter une simulation pour chaque segment sur une unité de traitement différente. Cela entraînera une vérification uniquement pour les objets proches les uns des autres. mais vous devrez synchroniser vos threads à chaque cycle. Ce qui signifie transférer certains de ces boids d'un groupe de traitement à un autre. en général, chaque cycle comprend 3 étapes:

  1. Déplacez tous les boids d'une unité. (qui peut facilement être traité à l'aide de plusieurs threads)
  2. Affecter chaque boid à un groupe *. Cela signifie qu'en utilisant un algorithme de O (n), vous devez sélectionner les boids les plus susceptibles de faire une collision. Cela peut également être géré à l'aide de plusieurs threads.
  3. À la fin, vous devez vérifier si deux boids dans un même groupe ont fait une collision.

* Pour créer des groupes, vous pouvez utiliser le modèle ci-dessous:

entrez la description de l'image ici

notez que certains boids peuvent faire partie de plus d'un groupe, mais ce modèle vous donne des résultats plus précis. vous pouvez également créer autant de groupes que vous le souhaitez en utilisant ce modèle, c'est juste un nombre que vous devez trouver pour combien de boids et l'écran quelle taille d'écran, quel est le meilleur nombre de groupes que vous devez créer.

--Éditer--

il y a une autre idée sur la segmentation qui est décrite dans le papier @LarsViklund suggéré, de cette façon il y a beaucoup moins de doubles vérifications et il n'est pas nécessaire d'augmenter / diminuer le nombre de threads entre les étapes:

entrez la description de l'image ici

notez que certaines zones font toujours partie de deux groupes. et la largeur de la zone de couverture du groupe est exactement 2*maximum speed. Dans votre cas, si les boids se déplacent d'un pixel par étape de simulation, il vous suffit de partager une zone de largeur de 2 pixels entre chaque groupe de 2. et il y a une petite zone qui fait partie de 4 groupes. mais en général, cette méthode est plus facile à mettre en œuvre et de loin plus rapide si elle est mise en œuvre correctement. et par la façon dont il n'y a pas de mouvement inverse de cette façon, si un objet peut se déplacer, il ne peut plus se déplacer.

Ali1S232
la source
Cela semble être une bonne idée, mais avant de passer à l'étape 1, je devrais faire une détection de collision pour voir s'ils peuvent se déplacer, n'est-ce pas?
Sycren
Vous pouvez les déplacer puis vérifier si une collision se produit en sens inverse de ce mouvement (pour ce boid exact), sinon laissez la simulation continuer.
Ali1S232
Merci, cela a plus de sens. En dehors des quadtrees, pouvez-vous penser à une autre façon de répartir la charge de travail?
Sycren
Comme vous pouvez le voir, mes segmentations ne sont pas complètement un arbre quadruple lui-même, il a un groupe supplémentaire pour augmenter la précision, le style d'arbre quadruple est beaucoup plus facile à gérer. Selon la taille du monde, vous pouvez ajouter plus de groupes, ce qui signifie moins de vérification à chaque cycle. c'est un compromis entre la consommation de mémoire et la vitesse de calcul. et il ne doit pas nécessairement être un thread pour chaque groupe. vous pouvez avoir des fils pour calculer plus d'un groupe. Vous pouvez également diviser les calculs d'un groupe entre deux ou plusieurs threads.
Ali1S232
@Gajet si je comprends bien votre image, il y aurait beaucoup de doubles calculs, car les zones de chevauchement des groupes sont très grandes. Étant donné que la question demande de simuler jusqu'à quelques millions de points, ce serait un énorme gaspillage.
Maik Semder
2

J'ai abordé ce problème récemment en utilisant certaines de ces réponses comme point de départ. La chose la plus utile à garder à l'esprit est que les boids sont une sorte de simulation simple à n corps: chaque boid est une particule qui exerce une force sur ses voisins.

J'ai trouvé le journal Linde difficile à lire; Je suggère plutôt de regarder les "algorithmes parallèles rapides pour la dynamique moléculaire à courte portée" de SJ Plimpton. , auxquels Linde a fait référence. L'article de Plimpton est beaucoup plus lisible et détaillé avec de meilleurs chiffres:

En résumé, les méthodes de décomposition des atomes attribuent un sous-ensemble d'atomes de façon permanente à chaque processeur, les méthodes de décomposition en force attribuent un sous-ensemble de calculs de force par paire à chaque proc, et les méthodes de décomposition spatiale affectent une sous-région de la boîte de simulation à chaque proc .

Je vous recommande d'essayer AD. C'est le plus simple à comprendre et à mettre en œuvre. FD est très similaire. Voici la simulation à n corps de nVidia avec CUDA à l'aide de FD, qui devrait vous donner une idée approximative de la façon dont la mosaïque et la réduction peuvent aider à dépasser considérablement les performances série.

Les implémentations SD sont généralement des techniques d'optimisation et nécessitent un certain degré de chorégraphie à implémenter. Ils sont presque toujours plus rapides et évoluent mieux.

En effet, AD / FD nécessite la construction d'une "liste de voisins" pour chaque boid. Si chaque boid a besoin de connaître la position de ses voisins, la communication entre eux est O ( n ²). Vous pouvez utiliser des listes de voisins Verlet pour réduire la taille de la zone vérifie chaque Boid, qui vous permet de reconstruire la liste tous les deux au lieu de chaque pas de temps pas, mais il est encore O ( n ²). En SD, chaque cellule conserve une liste de voisins, alors qu'en AD / FD chaque boid a une liste de voisins. Ainsi, au lieu que chaque boid communique entre eux, chaque cellule communique entre elles. Cette réduction de la communication est à l'origine de l'augmentation de la vitesse.

Malheureusement, le problème des boids sabote légèrement SD. Le fait que chaque processeur garde la trace d'une cellule est plus avantageux lorsque les boids sont répartis de manière quelque peu uniforme sur toute la région. Mais vous voulez que les boids se regroupent! Si votre troupeau se comporte correctement, la grande majorité de vos processeurs s'éloigneront, échangeant des listes vides entre eux, et un petit groupe de cellules finira par effectuer les mêmes calculs qu'AD ou FD.

Pour y faire face, vous pouvez soit ajuster mathématiquement la taille des cellules (qui est constante) pour minimiser le nombre de cellules vides à un moment donné, soit utiliser l'algorithme Barnes-Hut pour les quadruples arbres. L'algorithme BH est incroyablement puissant. Paradoxalement, il est extrêmement difficile à mettre en œuvre sur des architectures parallèles. En effet, un arbre BH est irrégulier, donc les threads parallèles le traversent à des vitesses très variables, ce qui entraîne une divergence de thread. Salmon et Dubinski ont présenté des algorithmes de bissection récursive orthogonaux pour répartir équitablement les quadruples entre les processeurs, qui doivent être retraités de manière itérative pour la plupart des architectures parallèles.

Comme vous pouvez le voir, nous sommes clairement dans le domaine de l'optimisation et de la magie noire à ce stade. Encore une fois, essayez de lire l'article de Plimpton et voyez si cela a un sens.

mauvaise blague
la source
1

Je suppose que le vôtre est un système toroïdal, vous pouvez partitionner l'espace afin que chaque unité ait sa sous-zone.

A chaque étape, les particules sont déplacées, les particules qui sortent de la sous-zone sont envoyées au processeur concerné; une étape de communication synchronisera les processeurs et un dernier post-pas sera effectué pour élaborer la position des particules étrangères (le cas échéant).

Ici, il y a trois problèmes ici:

  • 1) la forme de la sous-zone:

On peut opter pour des rectangles mais ils affichent un petit rapport surface / périmètre par rapport aux cercles. Plus la bordure est grande, plus il y aura de particules. Bien que les cicles présentent le meilleur rapport A / p, ne peuvent pas être utilisées pour la tessellation, vous devez donc indaguer pour certaines tessellations (éventuellement semi-régulières) avec un bon rapport A / p moyen. Évidemment, le calcul de l'indice de gland par coordonnées de cellule doit être simple, alors pensez-y avant d'essayer une gland très exotique.

  • 2) le protocole de communication:

En fonction du type d'infrastructure de communication dont vous disposez, vous pouvez réfléchir à la manière de diffuser les informations de passage des frontières entre les processeurs. Diffusion vs reconstruction peer-to-peer vs communication peer-to-peer sont toutes des options.

  • 3) l'allocation de sous-zone:

Vous devez garder votre élaboration équilibrée car il y a une syncronizzation à chaque étape. Vous pouvez choisir d'allouer des zones de manière statique ou dynamique aux processeurs. Ce n'est pas un gros problème si votre espace est uniformément couvert de particules actives, mais je crois que cela peut être faux dans ce cas, car les collisions désactivent les particules.Le changement d'allocation nécessite une étape de communication plus lourde; certains raccourcis peuvent être pris si tous les processeurs partagent les informations transfrontalières mais vous devez y réfléchir

FxIII
la source
@Fxlll Je ne sais pas ce que vous entendez par système toroïdal, ce n'est pas en forme de beignet. Voulez-vous dire que si une particule sort du côté droit, elle réapparaît à gauche? Si tel n'est pas le cas, si une particule frappe du côté droit, elle essaie de se déplacer dans une direction différente.
Sycren
@Sycren ok dans ce cas, vous devez prendre en compte la glandage et le traitement de la zone sur le bord d'une manière spéciale
FxIII
-1

Essayez ma simulation d'indices https://github.com/wahabjawed/Boids-Simulation

J'ai développé ça sur XNA

user106369
la source
Un simple lien vers un projet complet n'est pas une bonne réponse. Le lecteur est obligé de fouiller dans votre source jusqu'à ce qu'il trouve la partie pertinente à la question et doit encore comprendre comment cela résout le problème. Pouvez-vous décrire en anglais simple comment vous avez abordé le problème et quels avantages il présente par rapport aux solutions décrites dans les autres réponses? Vous pouvez copier et coller des extraits de code abrégés dans votre réponse s'ils aident à comprendre votre description.
Philipp