¿Cómo se puede resolver el problema del cuerpo n gravitatorio en paralelo?

Respuestas:

27

Existe una amplia variedad de algoritmos; Barnes Hut es un método popular , y el método Fast Multipole es un O ( N ) mucho más sofisticadoO(norteIniciar sesiónnorte)O(norte) alternativa .

Ambos métodos hacen uso de una estructura de datos de árbol donde los nodos esencialmente solo interactúan con sus vecinos más cercanos en cada nivel del árbol; puede pensar en dividir el árbol entre el conjunto de procesos a una profundidad suficiente, y luego hacer que cooperen solo en los niveles más altos.

Puede encontrar un artículo reciente sobre FMM en máquinas petascale aquí .

Jack Poulson
fuente
2
BH, también llamado código de árbol, parece preferible con baja precisión. Aquí hay un documento donde los métodos se combinan de forma adaptativa, pero aún no he visto este trabajo en la práctica.
Matt Knepley
8

Como fuente alternativa, también puede mirar métodos basados ​​en mallas de tipo Ewald. La génesis de los métodos de "malla de partículas" (como PPPM y Ewald de malla de partículas suavizadas) radica en las simulaciones de galaxias para astrofísica; la conexión con los cargos fue un efecto secundario no intencional (que eventualmente superó el uso original).

Más recientemente, también ha habido cierta literatura sobre métodos de suma multinivel que son similares en espíritu a los métodos multipolares rápidos y al Barnes-Hut, pero que pueden ofrecer ventajas en diferentes circunstancias (geometrías más generales y flexibles, algunas ganancias de eficiencia, etc.).

aeismail
fuente
8

Para el clásico problema del cuerpo n gravitacional , creo que los siguientes dos documentos hacen un buen trabajo al analizar las entrañas de la implementación paralela para el paso de evaluación de la fuerza. Aunque los documentos discuten una implementación de GPU, hacen un buen trabajo al discutir el paralelismo y proporcionan detalles de los algoritmos:

Este papel de Nyland, Harris y Prins presenta el algoritmo directo de n cuerpos en CUDA para GPU.

Este otro papel de Yokota y Barba tiene una buena discusión sobre el código de árbol y el algoritmo multipolar rápido también en el contexto de la computación GPU

Sus preguntas sobre la precisión de las simulaciones numéricas de n cuerpos son un poco más complicadas y hay tantos detalles importantes que una respuesta puede generar varios libros. Creo que lo mejor es darle un par de referencias de libros. Yo sugiero:

Simulaciones gravitacionales de N cuerpos por Sverre J. Aarseth

Simulaciones por computadora utilizando partículas de Hockney y Eastwood. (Lo siento, no hay versión pdf)

fcruz
fuente
4

Si necesita un enfoque de implementación simple que no sea óptimo en el sentido asintótico, es posible que desee considerar el uso de operaciones de comunicación integradas. Dado que cada uno de los N cuerpos necesita conocer el efecto gravitacional de los otros cuerpos, es importante que cada procesador conozca todo el conjunto de datos. Esto es lo que hacen todas las operaciones de recolección. Hay un buen libro: Programación paralela en C con MPI y OPENMP por Michael J. Quinn (2004) que analiza exactamente este tema en la página 82. Puede valer la pena mirarlo para comenzar.

Paul
fuente
3
O(norte2)
Es verdad. Aunque, como dije antes, esta es una implementación fácil, no necesariamente eficiente.
Paul
De alguna manera, +1 todas las demás respuestas suponen que el OP está buscando un rendimiento de tera o petascale. FMM y akin tienen sentido solo opuestos a enfoques más ingenuos.
Stefano M
1

Vea Google Scholar y busque referencias a HACC y GADGET, entre otros códigos.

Jeff
fuente
2
¿Podría agregar un poco más de detalles sobre por qué recomienda HACC y GADGET?
Paul
1
Ambos son códigos de cosmología de alto perfil que incluyen solucionadores de gravedad.
Jeff