Como você pode paralelizar uma simulação de boids 2D

16

Como você pode programar uma simulação de boids 2D de forma que possa usar o poder de processamento de diferentes fontes (clusters, gpu).

boids exemplo

No exemplo acima, as partículas não coloridas se movem até que se agrupem (amarelo) e parem de se mover.

O problema é que todas as entidades poderiam interagir entre si, embora seja improvável que uma entidade no canto superior esquerdo interaja com uma no canto inferior direito. Se o domínio foi dividido em segmentos diferentes, pode acelerar a coisa toda. Mas, se uma entidade quiser entrar em outro segmento, pode haver problemas.

No momento em que esta simulação trabalha com 5000 entidades com uma boa taxa de quadros, eu gostaria de tentar isso com milhões, se possível.

Seria possível usar árvores quádruplas para otimizar ainda mais isso? Alguma outra sugestão?

Sycren
fonte
Você está pedindo otimização ou como paralelizar? Essas são coisas diferentes.
bummzack
@bummzack Como paralelizar, acabei de adicionar mais explicações, isso ajuda?
Sycren

Respostas:

7

A tese de mestrado Parallel Simulation of Particle Fluids de Mattias Linde pode oferecer algumas dicas sobre particionamento de dados e algoritmos para simulação em larga escala.

Seu artigo é voltado para a Hidrodinâmica de Partículas Suavizadas , que para a solução ingênua tende a usar Hashing Espacial com um tamanho de balde em torno do tamanho da pegada de kernel das partículas na simulação.

Como a distância de interação é rígida nos kernels SPH típicos, essas otimizações de particionamento são quase essenciais na expansão do sistema.

Lars Viklund
fonte
bom artigo, mas a parte atual dessa pergunta parece ser muito parecida com a resposta do @Fxlll.
Ali1S232
Eu diria que a parte real do artigo é como ele resolve os casos extremos, introduzindo um protocolo de comunicação, essa é a parte difícil, o particionamento quad é bastante óbvio e, por si só, não resolve o problema dos casos extremos.
Maik Semder
4

O termo que aprendi há muito tempo era a velocidade da informação de um jogo.

Se a velocidade dos seus boids for 1 e eles se importarem apenas com os vizinhos, a velocidade das informações será 3, ou seja, um boid a dois quadrados de distância de você pode estar dentro do intervalo de seu interesse em um único quadro:

1 movimento quadrado por boid na interação (1 + 1) mais a distância em que você pode notar que as coisas (1) são iguais a 3.

Diante disso, aprendemos que podemos dividir um mapa em pedaços, do tamanho que queremos, mas com essa velocidade de informação se sobrepõe a todos os pedaços vizinhos.

Presumo que você permita que seus lances movam apenas um quadrado, mas eles podem ver três

Se você deseja executar um enorme simulador paralelo, divide-se em grades de 10x10, mas se sobrepõe em 5 quadrados em cada borda. Sempre que um de vocês acabar dentro da distância das informações da borda do bloco local, atualize o vizinho e, uma vez que eles atravessam a fronteira, não pertencem a você. Se um vizinho disser que um boid que ele está controlando mudou para o seu pedaço, você deve assumir o controle da IA.

Isso significa que a comunicação é localizada para os gerenciadores de chunk vizinhos e o tráfego é reduzido ao mínimo. Quanto mais tarefas você executa, mais CPUs você pode usar para alimentar a simulação, mas quanto mais tarefas você executa, mais se sobrepõem e, portanto, mais informações passam entre tarefas / partes à medida que a simulação avança. É aqui que você precisa se esforçar e ajustar o tamanho do pedaço, com base na complexidade da IA ​​e no hardware disponível.

Richard Fabian
fonte
imagine que o mundo tem 1.000.000 x 1.000.000 de grade e existem 10.000.000 boids no mundo, e cada boid pode mover exatamente um quadrado a cada turno. Você pode explicar como verificar se há um boid no bairro de outro?
Ali1S232
Estou supondo que poderíamos dividi-lo em 2000 quadrados 500x500 ou mais. cada quadrado contém uma lista de boids, bem como uma lista de vizinhos. Se um boid sai de um quadrado, ele é removido da lista de boids e adicionado ao outro quadrado. O problema com esse método que posso ver é se você adicionar algo com flocagem maior que o quadrado. a solução quadtree teria que ser dinâmico, mas eu não estou certo o quão caro isso seria
Sycren
@ Gajet: você só precisa verificar boids no seu bloco ou nas fronteiras gerenciadas vizinhas. Lembre-se de que a borda é garantida pelo design para levar em consideração a distância que uma entidade pode se mover mais a distância que as entidades podem ver. @ Sycren: flocagem, mesmo que nos pareça ser uma grande entidade, ainda é apenas um efeito de pequena escala. Um cardume de peixes não segue a escola, eles seguem seus vizinhos observáveis.
Richard Fabian
2

Ao ler seu quesiton, parece que você pode se beneficiar de árvores quádruplas, criar uma árvore quádrupla e executar simulação para cada segmento em uma unidade de processamento diferente. Isso fará com que a verificação ocorra apenas em objetos próximos um do outro. mas você precisará sincronizar seus threads a cada ciclo. O que significa transferir alguns desses boids de um grupo de processamento para outro. em geral, todo ciclo consiste em 3 etapas:

  1. Mova todos os boids por uma unidade. (que pode ser facilmente processado usando vários threads)
  2. Atribuindo cada boid a um grupo *. Isso significa que, usando um algoritmo O (n), é necessário selecionar quais boids têm maior probabilidade de colisão. Isso também pode ser tratado usando vários threads.
  3. No final, você deve verificar se dois boids em um mesmo grupo fizeram colisão.

* Para criar grupos, você pode usar o padrão abaixo:

insira a descrição da imagem aqui

observe que alguns boids podem fazer parte de mais de um grupo, mas esse padrão fornece resultados mais precisos. você também pode criar quantos grupos quiser usando esse padrão. É apenas um número que você precisa encontrar para quantos boids e a tela com qual tamanho de tela, qual é o melhor número de grupos que você precisa criar.

--editar--

existe outra idéia sobre segmentação descrita no artigo sugerido por @LarsViklund, dessa forma há muito menos verificações duplas e não há necessidade de aumentar / diminuir o número de threads entre as etapas:

insira a descrição da imagem aqui

note que algumas áreas ainda fazem parte de dois grupos. e a largura da área em que a cobertura de ambos os grupos é exata 2*maximum speed. No seu caso, se os boids moverem um pixel por etapa de simulação, você precisará compartilhar apenas uma área de 2 pixels de largura entre cada 2 grupos. e há uma pequena área que faz parte de 4 grupos. mas, em geral, esse método é mais fácil de implementar e muito mais rápido se implementado corretamente. e, a propósito, não há movimento inverso dessa maneira, se algum objeto puder se mover, ele poderá se mover, não será mais necessário verificar.

Ali1S232
fonte
Parece uma boa idéia, mas antes de avançar na etapa 1, eu precisaria fazer uma detecção de colisão para ver se eles podem se mover, não?
Sycren
Você pode movê-los e verificar se alguma colisão acontece ao contrário do movimento (para esse boid exato), se não deixar a simulação continuar.
#
Obrigado, isso faz mais sentido. Além dos quadríceps, você pode pensar em outra maneira de dividir a carga de trabalho?
Sycren
Como você pode ver, minhas segmentações não são completamente uma árvore quádrupla, ele tem mais um grupo extra para aumentar a precisão, o estilo de árvore quádrupla é apenas muito mais fácil de manusear. Dependendo do tamanho do mundo, você pode adicionar mais grupos, o que significa menos checagem em cada ciclo. é uma troca entre consumo de memória e velocidade de computação. e não precisa necessariamente ter um segmento para cada grupo. você pode ter alguns threads para calcular mais de um grupo. Você também pode dividir os cálculos de um grupo entre dois ou mais threads.
Ali1S232 01/07
@ Gajet, se eu entendi bem sua foto, haveria muitos cálculos duplos, já que as áreas sobrepostas dos grupos são muito grandes. Dado que a pergunta pede para simular alguns milhões de pontos, isso seria um grande desperdício.
Maik Semder
2

Lidei com esse problema recentemente usando algumas dessas respostas como ponto de partida. A coisa mais útil a ter em mente é que os boids são uma espécie de simulação simples do corpo n: cada boid é uma partícula que exerce força sobre seus vizinhos.

Achei o jornal Linde difícil de ler; Sugiro, em vez disso, olhar para os "Algoritmos rápidos paralelos de SJ Plimpton para dinâmica molecular de curto alcance" , que Linde referenciou. O artigo de Plimpton é muito mais legível e detalhado com melhores números:

Em poucas palavras, os métodos de decomposição de átomos atribuem um subconjunto de átomos permanentemente a cada processador, os métodos de decomposição de força atribuem um subconjunto de cálculos de força em pares a cada proc e os métodos de decomposição espacial atribuem uma sub-região da caixa de simulação a cada proc .

Eu recomendo que você tente o AD. É o mais fácil de entender e implementar. FD é muito semelhante. Aqui está a simulação de corpo n da nVidia com CUDA usando FD, que deve fornecer uma idéia aproximada de como a telha e a redução podem ajudar a superar drasticamente o desempenho em série.

As implementações de SD geralmente são técnicas de otimização e requerem algum grau de coreografia para serem implementadas. Eles são quase sempre mais rápidos e escalam melhor.

Isso ocorre porque o AD / FD requer a criação de uma "lista de vizinhos" para cada boid. Se todo boid precisa conhecer a posição de seus vizinhos, a comunicação entre eles é O ( n ²). Você pode usar as listas de vizinhos do Verlet para reduzir o tamanho da área que cada boid verifica, o que permite reconstruir a lista a cada poucos intervalos de tempo em vez de cada etapa, mas ainda é O ( n ²). No SD, cada célula mantém uma lista de vizinhos, enquanto no AD / FD todo boid possui uma lista de vizinhos. Então, em vez de todo boid se comunicar, cada célula se comunica. Essa redução na comunicação é a origem do aumento da velocidade.

Infelizmente, o problema dos boids sabota ligeiramente o SD. Ter cada processador monitorando uma célula é mais vantajoso quando os boids são distribuídos de maneira uniforme por toda a região. Mas você quer que os boids se agrupem! Se seu rebanho estiver se comportando adequadamente, a grande maioria dos seus processadores estará passando, trocando listas vazias entre si e um pequeno grupo de células acabará realizando os mesmos cálculos que o AD ou o FD faria.

Para lidar com isso, você pode ajustar matematicamente o tamanho das células (que é constante) para minimizar o número de células vazias em um determinado momento ou usar o algoritmo Barnes-Hut para árvores quad. O algoritmo BH é incrivelmente poderoso. Paradoxalmente, é extremamente difícil de implementar em arquiteturas paralelas. Isso ocorre porque uma árvore BH é irregular, portanto, os threads paralelos o atravessam em velocidades muito variadas, resultando em divergência de thread. Salmon e Dubinski apresentaram algoritmos ortogonais de bissecção recursiva para distribuir quadríceps uniformemente entre processadores, que devem ser atualizados iterativamente para a maioria das arquiteturas paralelas.

Como você pode ver, estamos claramente no campo da otimização e da magia negra neste momento. Mais uma vez, tente ler o artigo de Plimpton e veja se isso faz algum sentido.

piada ruim
fonte
1

Estou assumindo que o seu é um sistema toroidal, você pode particionar no espaço para que cada unidade tenha sua subárea.

A cada passo, as partículas são movidas, as partículas que saem da subárea são enviadas ao processador relevante; uma etapa de comunicação sincroniza os processadores e uma última etapa é executada para elaborar a posição das partículas estranhas (se houver).

Aqui há três problemas aqui:

  • 1) a forma da subárea:

Pode-se optar por retângulos, mas mostra uma pequena relação Área / perímetro em comparação com cirlces. Quanto maior a borda, mais partículas deixarão. Enquanto os ciclos exibem a melhor relação A / p, não podem ser usados ​​para mosaico, portanto, você deve indicar alguns mosaicos (possivelmente semi-regulares) com uma boa proporção média de A / p. Obviamente, o cálculo do índice de borla pela coordenada da célula deve ser simples; considere isso antes para tentar uma borla muito exótica.

  • 2) o protocolo de comunicação:

Dependendo do tipo de infraestrutura de comunicação que você possui, você pode pensar em como dispersar as informações de passagem de fronteira entre os processadores. Transmissão versus reconstrução ponto a ponto e comunicação ponto a ponto são todas as opções.

  • 3) a alocação da subárea:

Você deve manter sua elaboração equilibrada, pois há uma sincronização a cada etapa. Você pode optar por alocar áreas estaticamente ou dinamicamente aos processadores. Este não é um grande problema se o seu espaço estiver coberto uniformemente por partículas ativas, mas acredito que pode ser falso nesse caso, pois as colisões desativam as partículas. Alterar a alocação requer uma etapa de comunicação mais pesada; algum atalho pode ser usado se todos os processadores compartilharem as informações transfronteiriças, mas você tiver que fazer alguma consideração sobre isso

FxIII
fonte
@Fxlll Não tenho certeza do que você quer dizer com sistema toroidal, não está na forma de um donut. Você quer dizer que se uma partícula sai do lado direito, ela reaparece à esquerda? Nesse caso, não é esse o caso, se uma partícula atinge o lado direito, ela tenta se mover em uma direção diferente.
Sycren
@Sycren ok, neste caso, você tem que fazer alguma consideração sobre tasselation e tratar a área na borda de uma maneira especial
FXIII
-1

Tente minha simulação para obter pistas https://github.com/wahabjawed/Boids-Simulation

Eu desenvolvi isso no XNA

user106369
fonte
Apenas vincular um projeto completo não é uma boa resposta. O leitor é forçado a procurar na sua fonte até encontrar a parte que é relevante para a pergunta e ainda precisa entender como resolve o problema. Você pode descrever em inglês simples como abordou o problema e quais vantagens ele tem sobre as soluções descritas nas outras respostas? Você pode copiar e colar alguns trechos de código curto na sua resposta se eles ajudarem a entender sua descrição.
Philipp