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).
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?
Réponses:
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.
la source
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.
la source
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:
* Pour créer des groupes, vous pouvez utiliser le modèle ci-dessous:
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:
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.la source
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:
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.
la source
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:
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.
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.
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
la source
Essayez ma simulation d'indices https://github.com/wahabjawed/Boids-Simulation
J'ai développé ça sur XNA
la source