Como você pode programar uma simulação de boids 2D de forma que possa usar o poder de processamento de diferentes fontes (clusters, gpu).
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?
Respostas:
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.
fonte
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.
fonte
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:
* Para criar grupos, você pode usar o padrão abaixo:
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:
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.fonte
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:
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.
fonte
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:
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.
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.
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
fonte
Tente minha simulação para obter pistas https://github.com/wahabjawed/Boids-Simulation
Eu desenvolvi isso no XNA
fonte