¿Cómo podría programar una simulación de boids 2D de tal manera que pudiera usar la potencia de procesamiento de diferentes fuentes (clusters, gpu)?
En el ejemplo anterior, las partículas no coloreadas se mueven hasta que se agrupan (amarillo) y dejan de moverse.
El problema es que todas las entidades podrían interactuar entre sí, aunque es poco probable que una entidad en la parte superior izquierda interactúe con una en la parte inferior derecha. Si el dominio se dividió en diferentes segmentos, puede acelerar todo, pero si una entidad quisiera cruzar a otro segmento puede haber problemas.
En este momento, esta simulación funciona con 5000 entidades con una buena velocidad de cuadros, me gustaría probar esto con millones si es posible.
¿Sería posible utilizar árboles quad para optimizar aún más esto? ¿Cualquier otra sugerencia?
Respuestas:
La tesis de maestría Simulación paralela de fluidos de partículas por Mattias Linde podría ofrecer una idea de la partición de datos y algoritmos para la simulación a gran escala.
Su artículo está dirigido a la Hidrodinámica de Partículas Alisadas , que para la solución ingenua tiende a usar Spatial Hashing con un tamaño de cubo alrededor del tamaño de la huella del grano de las partículas en la simulación.
Como la distancia de interacción está fija en los núcleos SPH típicos, estas optimizaciones de partición son casi esenciales para ampliar el sistema.
fuente
El término que aprendí hace mucho tiempo era la velocidad de información de un juego.
Si la velocidad de sus boids es 1 y solo se preocupan por sus vecinos, entonces la velocidad de la información es 3, es decir, un boid que está a dos cuadrados de distancia de usted podría estar dentro del rango que le interesa dentro de un marco:
1 movimiento cuadrado por boid en la interacción (1 + 1) más la distancia en la que puedes notar cosas (1) es igual a 3.
Dado esto, aprendemos que podemos dividir un mapa en pedazos, del tamaño que sea tan pequeño como queramos, pero con esta velocidad de información superpuesta en cualquier fragmento vecino.
Asumiré que estás permitiendo que tus boids se muevan solo un cuadrado, pero pueden ver tres
Si desea ejecutar un simulador paralelo masivo, se divide en cuadrículas de 10x10, pero se superpone en 5 cuadrados en cada borde. Siempre que uno de tus miembros se encuentre dentro de la distancia de información desde el borde del fragmento local, debes actualizar al vecino, y una vez que atraviesan el límite, no te pertenecen. Si un vecino dice que un boid que están controlando se ha movido a tu trozo, debes asumir su IA.
Esto significa que la comunicación se localiza a los administradores de fragmentos vecinos y el tráfico se reduce al mínimo. Cuantos más trabajos ejecute, más CPU podrá utilizar para alimentar la simulación, pero cuantos más trabajos ejecute, más se superpondrán y, por lo tanto, más información pasará entre trabajos / fragmentos a medida que avanza la simulación. Aquí es donde tienes que ser duro y ajustar el tamaño del fragmento en función de la complejidad de la IA y el hardware que tienes disponible.
fuente
Al leer su pregunta, parece que puede aprovechar los árboles cuádruples, crear un árbol cuádruple y ejecutar la simulación para cada segmento en una unidad de procesamiento diferente. Esto hará que la verificación solo suceda a objetos cercanos entre sí. pero necesitarás sincronizar tus hilos en cada ciclo. Lo que significa transferir algunos de esos boids de un grupo de procesamiento a otro. en general cada ciclo constará de 3 pasos:
* Para crear grupos, puede usar el siguiente patrón:
tenga en cuenta que algunos boids pueden ser parte de más de un grupo, pero este patrón le brinda resultados más precisos. También puede crear tantos grupos como desee usando este patrón. Es solo un número que tiene que encontrar para cuántos boids y la pantalla, qué tamaño de pantalla, cuál es el mejor número de grupos que necesita crear.
--editar--
Hay otra idea sobre la segmentación que se describe en el documento @LarsViklund sugerido, de esta manera hay muchas menos comprobaciones dobles y no hay necesidad de aumentar / disminuir el número de hilos entre los pasos:
Tenga en cuenta que algunas áreas todavía son parte de dos grupos. y el ancho del área, la cobertura de ambos grupos es exactamente
2*maximum speed. En su caso, si las plataformas se mueven un píxel por paso de simulación, solo necesita compartir un área de 2 píxeles de ancho entre cada grupo 2. y hay una pequeña área que forma parte de 4 grupos. pero en general este método es más fácil de implementar y mucho más rápido si se implementa correctamente. y, por cierto, no hay movimiento inverso de esta manera, si algún objeto puede moverse, puede moverse, no se requiere más comprobación.fuente
Recientemente abordé este problema utilizando algunas de estas respuestas como punto de partida. Lo más útil a tener en cuenta es que los boids son una especie de simulación simple de n cuerpos: cada boid es una partícula que ejerce una fuerza sobre sus vecinos.
Encontré el papel de Linde difícil de leer; Sugiero en cambio mirar a SJ Plimpton "Algoritmos paralelos rápidos de para la dinámica molecular de corto alcance" , a los que Linde hizo referencia. El artículo de Plimpton es mucho más legible y detallado con mejores cifras:
Te recomiendo que pruebes AD. Es lo más fácil de entender e implementar. FD es muy similar. aquí está la simulación de n-cuerpos de nVidia con CUDA usando FD, que debería darle una idea aproximada de cómo el mosaico y la reducción pueden ayudar a superar drásticamente el rendimiento en serie.
Las implementaciones de SD generalmente son técnicas de optimización y requieren cierto grado de coreografía para implementarse. Casi siempre son más rápidos y escalan mejor.
Esto se debe a que AD / FD requiere la creación de una "lista de vecinos" para cada boid. Si cada boid necesita conocer la posición de sus vecinos, la comunicación entre ellos es O ( n ²). Puede usar las listas de vecinos de Verlet para reducir el tamaño del área que comprueba cada boid, lo que le permite reconstruir la lista cada pocos pasos en lugar de cada paso, pero sigue siendo O ( n ²). En SD, cada celda mantiene una lista de vecinos, mientras que en AD / FD cada boid tiene una lista de vecinos. Entonces, en lugar de que cada boid se comunique entre sí, cada célula se comunica entre sí. Esa reducción en la comunicación es de donde viene el aumento de velocidad.
Lamentablemente, el problema de Boids sabotea ligeramente SD. Hacer que cada procesador realice un seguimiento de una celda es más ventajoso cuando los boids están distribuidos de manera uniforme en toda la región. ¡Pero quieres que las boids se agrupen! Si su bandada se comporta correctamente, la gran mayoría de sus procesadores se irán, intercambiando listas vacías entre sí, y un pequeño grupo de celdas terminará realizando los mismos cálculos que AD o FD.
Para lidiar con esto, puede ajustar matemáticamente el tamaño de las celdas (que es constante) para minimizar el número de celdas vacías en un momento dado, o usar el algoritmo Barnes-Hut para árboles cuádruples. El algoritmo BH es increíblemente poderoso. Paradójicamente, es extremadamente difícil de implementar en arquitecturas paralelas. Esto se debe a que un árbol BH es irregular, por lo que los hilos paralelos lo atravesarán a velocidades muy variables, lo que provocará una divergencia del hilo. Salmon y Dubinski han presentado algoritmos de bisección recursiva ortogonal para distribuir los cuadrúteros de manera uniforme entre los procesadores, que deben reestablecerse iterativamente para la mayoría de las arquitecturas paralelas.
Como puede ver, estamos claramente en el ámbito de la optimización y la magia negra en este momento. Nuevamente, intente leer el artículo de Plimpton y vea si tiene algún sentido.
fuente
Supongo que el suyo es un sistema toroidal, puede dividir el espacio para que cada unidad tenga su subárea.
En cada paso, las partículas se mueven, las partículas que salen del área secundaria se envían al procesador correspondiente; un paso de comunicación sincronizará los procesadores y se tomará un último paso para elaborar la posición de las partículas extrañas (si corresponde).
Aquí hay tres problemas aquí:
Uno puede optar por rectángulos, pero muestra una pequeña relación Área / perímetro en comparación con los círculos. Cuanto más grande sea el borde, más partículas saldrán. Si bien los ciclos exhiben la mejor relación A / p, no se pueden usar para la teselación, por lo que debe indagar para alguna teselación (posiblemente semi regular) con una buena relación A / p promedio. Obviamente, calcular el índice de borla por coordenada de celda debería ser simple, así que considere esto antes para probar una tasación muy exótica.
Dependiendo del tipo de infraestructura de comunicación que tenga, puede pensar cómo dispersar la información que cruza la frontera entre los procesadores. La transmisión frente a la reconstrucción entre pares frente a la comunicación entre pares son todas las opciones.
Debe mantener su elaboración equilibrada ya que hay una sincronización sincronizada en cada paso. Puede elegir asignar áreas estáticas o dinámicas a los procesadores. Este no es un gran problema si su espacio está cubierto de manera uniforme por partículas activas, pero creo que puede ser falso en este caso, ya que las colisiones desactivan las partículas. Cambiar la asignación requiere un paso de comunicación más pesado; se puede tomar algún atajo si todos los procesadores comparten la información transfronteriza, pero debe tener en cuenta al respecto
fuente
Pruebe mi simulación para obtener pistas https://github.com/wahabjawed/Boids-Simulation
Desarrollé esto en XNA
fuente