Simulación de una cantidad arbitraria (n) de cuerpos en el espacio tridimensional. Se simula algún fenómeno físico, como la atracción gravitacional o el electromagnetismo. Para este proyecto se usará atracción gravitacional usando modelos de física clásica.

Debe suponerse que la cantidad de partículas no caben en la memoria principal de una máquina, pero sí en la memoria primaria de un sistema distribuido. Mediante argumentos de línea de comandos, cada proceso creará una cantidad de cuerpos en posiciones aleatorias del espacio. Dado que cada proceso sólo conoce una parte del universo pero no la de otros, debe intercambiar el mínimo de información para que los demás procesos puedan actualizar sus cuerpos y colaborativamente avanzar la simulación. El objetivo no es tanto disminuir el tiempo de ejecución, si no, lograr simular correctamente un universo distribuido por las limitaciones de memoria.

1. Modelo físico

Magnitud de la fuerza de atracción gravitacional (fórmula tradicional de educación secundaria):

\[|\vec{F}| = G \frac{m_1 m_2}{|\vec{r}|^2}\]

La fuerza gravitacional que el cuerpo j ejerce sobre el cuerpo i y mantiene la dirección hacia el cuerpo en estudio i:

\[\vec{F_{i,j}} = -G \frac{m_i m_j}{|\vec{r_{i,j}}|^3} \vec{r_{i,j}}\]

\(\vec{r}\) es el vector distancia entre los cuerpos i y j, que se puede calcular a partir del vector posición \(\vec{x}\) del cuerpo, tomando al cuerpo i como el centro del sistema de referencia:

\[\vec{r_{i,j}} = \vec{x_i} - \vec{x_j}\]

La magnitud o norma de un vector cualquiera \(\vec{C}\) en el espacio es la distancia pitagórica al origen de sus componentes cartesianos x, y, z:

\[|\vec{C}| = \sqrt{C_x^2 + C_y^2 + C_z^2}\]

La fuerza gravitacional total (resultante) ejercida por todos los N - 1 cuerpos j sobre el cuerpo en estudio i es:

\[\vec{F_i} = -G \sum_{i \ne j}^{N} \frac{m_i m_j}{|\vec{r_{i,j}}|^3} \vec{r_{i,j}}\]

Para simular nos interesa obtener el vector posición en cada actualización de la simulación. La aceleración que va a sufrir el cuerpo i debido a la fuerza gravitacional total se puede obtener de \(\vec{F} = m \vec{a} \Rightarrow \vec{a} = \vec{F}/m\):

\[\vec{a_i} = -G \sum_{i \ne j}^{N} \frac{m_j}{|\vec{r_{i,j}}|^3} \vec{r_{i,j}}\]

La velocidad se puede obtener por la relación \(\vec{V} = \vec{V_0} + \vec{a} t\). La velocidad del cuerpo depende del tiempo t. La simulación se actualizará cada \(\Delta t\) segundos, lo cual es una constante:

\[\vec{V_{i,t+1}} = \vec{V_{i,t}} + \vec{a_i} \Delta t\]

De la relación \(\vec{V} = \vec{d}/t \Rightarrow \vec{d} = \vec{V}t\) Finalmente la posición que tendrá el cuerpo i en el tiempo t + 1 será:

\[\vec{x_{i,t+1}} = \vec{x_{i,t}} + \vec{V_{i,t+1}} \Delta t\]

Para efectos de la simulación, la posición de un cuerpo no se puede actualizar mientras se están actualizando otros cuerpos. Por lo tanto cada actualización de la simulación tendrá dos fases. En la primera se actualiza el vector de velocidad de cada cuerpo. En la segunda fase se actualizará la posición de cada cuerpo. En esta segunda fase podría ocurrir que dos cuerpos colisionen, lo cual se detecta cuando la suma de sus radios es mayor que la distancia que los separa:

\[r_i + r_j \gt |\vec{r_{i,j}}|\]

Cuando dos cuerpos colisionan, supóngase que se fusionan. El cuerpo más grande absorbe al más pequeño. El más pequeño deja de existir para efectos de la simulación, y el más grande continúa su movimiento con su masa incrementada y su velocidad se afecta por la cantidad de movimiento (momentum). Es una colisión inelástica donde las masas \(a\) y \(b\) se fusionan y continúan a una velocidad \(\vec{V}\) que conserva la cantidad de movimiento con la relación \(m_a \vec{V_a} + m_b \vec{V_b} = (m_a + m_b)\vec{V}\), por lo que la nueva velocidad del cuerpo incrementado sería

\[\vec{V} = \frac{m_a \vec{V_a} + m_b \vec{V_b}} {m_a + m_b}\]

Para efectos de la simulación, si colisionan dos cuerpos de igual masa, supóngase que el cuerpo con el índice más pequeño (el que se creó primero) absorbe al segundo.

El volumen del cuerpo que absorbe se incrementa en el volumen del cuerpo absorbido. Dado que todos los cuerpos en la simulación son esferas, su volumen V (no confundir con velocidad) se obtiene por la relación \(V = 4/3 \pi r^3\). Si dos cuerpos \(a\) y \(b\) se fusionan en un cuerpo \(c\), el volumen del nuevo cuerpo sería \(V_c = V_a + V_b\), y su radio puede inferirse como

\[r_c = \sqrt[3]{r_a^3 + r_b^3}\]

2. Problema a resolver

n Título Video

1

Simulación de n-cuerpos. Fuerza gravitacional

📹

2

Archivo de cuerpos. Archivo de trabajo

📹

3

Modelo físico de fuerzas gravitacionales

📹

4

Cálculo de la aceleración, velocidad, y posición

📹

5

Detalles técnicos de la simulación. Colisiones de masas

📹
Important
 Para esta versión del proyecto, su solución no debe implementar los archivos de trabajo explicados en el video 2. Basta con archivos de cuerpos textuales (archivos binarios tampoco son requeridos).

Su programa podría invocarse de dos modos de acuerdo a sus argumentos de línea de comandos, con las siguientes sintaxis:

nbody bodies.txt delta_t max_time
nbody body_count delta_t max_time min_pos max_pos min_vel max_vel

En el primer modo, llamado modo universo de archivo, recibirá un archivo de cuerpos (universo) en el primer argumento de línea de comandos, seguido por los parámetros de la simulación. El programa realizará la simulación y la salida se escribirá un archivo de universo textual que incluye en su nombre el tiempo en segundos en que se detuvo la simulación, tal como se indica en el video 2, por ejemplo bodies-7200.txt si la simulación se detuvo en el segundo 7200. Este modo permite probar su programa contra casos de prueba manuales para asegurar que resuelva el problema correctamente.

En el segundo modo, llamado modo universo aleatorio, no se provee un archivo de trabajo, sino que se proveen siete argumentos de línea de comandos, todos numéricos:

  1. La cantidad de cuerpos del universo (size_t)

  2. La cantidad \(\Delta t\) de segundos en que dura cada actualización de la simulación (double).

  3. La duración máxima de la simulación en segundos (double).

  4. La posición mínima inicial (en metros) en el universo para los tres ejes del espacio tridimensional (double).

  5. La posición máxima inicial (en metros) en el universo para los tres ejes del espacio tridimensional (double).

  6. La velocidad mínima inicial (en metros por segundo) para los tres ejes del espacio tridimensional (double).

  7. La velocidad máxima inicial (en metros por segundo) para los tres ejes del espacio tridimensional (double).

En el modo de universo aleatorio, el programa generará un universo con la cantidad de cuerpos indicada en el primer argumento. Los cuerpos serán ubicados en posiciones aleatorias del espacio tridimensional con velocidades iniciales también aleatorias, pero dentro de los rangos indicados por los límites de los argumentos de línea de comandos. Es decir, la diferencia entre el modo archivo y el modo de generación aleatoria es en el cargado de los cuerpos. Una vez que estos se tengan en las colecciones respectivas, el resto de la simulación es idéntica en ambos modos.

En cualquiera de los dos modos de ejecución, si su programa se ejecuta de forma distribuida, es decir, se crea un equipo de procesos de su programa, cada proceso se encargará de una parte de los cuerpos del universo. En el modo archivo, cada proceso cargará una fracción de los cuerpos del archivo a su colección. En el modo al azar, cada proceso creará una fracción de la cantidad de cuerpos indicada en el primera argumento de línea de comandos. Esta estrategia permite a las personas investigadoras simular universos más realistas con grandes cantidades de cuerpos, que no caben en la memoria principal de una computadora, pero sí en la de un clúster de computadoras. En el otro extremo, si la cantidad de cuerpos es menor que la cantidad de procesos creados, finalice su programa con un mensaje de error, de tal manera que todo proceso tenga que encargarse de al menos un cuerpo en la simulación.

Los demás procesos no conocerán los cuerpos de otros procesos, pero los necesitarán para poder aplicar la fuerza gravitacional a los propios. Su solución debe enviar el mínimo de información a través de paso de mensajes (MPI) para que los demás procesos puedan actualizar sus cuerpos y avanzar la simulación.

Una vez que la simulación inicie, los cuerpos pueden moverse a posiciones o velocidades que sobrepasen los límites indicados en los argumentos de línea de comandos en la versión de universo aleatorio. Es decir, estos límites son sólo para las posiciones y velocidades iniciales. Estos límites permiten a las personas investigadoras controlar el universo, de tal forma que en un universo muy reducido se espera que haya más colisiones entre masas que uno más extendido.

Una vez que la simulación termine: (a) en el modo archivo se generará un archivo de texto con el estado de los cuerpos, (b) en el modo de universo aleatorio no debe crear ningún archivo. En ambos modos, las personas investigadoras esperan un resumen en la salida estándar con los siguientes datos:

  1. La cantidad de cuerpos que se mantienen vigentes en la simulación.

  2. La distancia promedio entre los cuerpos vigentes (en sus tres componentes).

  3. La desviación estándar de las distancias entre los cuerpos vigentes.

  4. La velocidad promedio de los cuerpos vigentes (en sus tres componentes).

  5. La desviación estándar de las velocidades de los cuerpos vigentes.

El siguiente es un ejemplo de salida hipotética:

Remaining bodies: 729
Distance (mean) : <3.81403, 5.11032, 0>
Distance (stdev): <21.28, 4.21999, 0>
Velocity (mean) : <-77.77499, 0.83828, 0>
Velocity (stdev): <103.38048, 5.39262, 0>

3. Evaluación

En todos los rubros se evalúan las buenas prácticas.

  1. [10%] Repositorio (commits equilibrados, ignores, tags). Directorios. Modularización de código y archivos (.hpp/.cpp). Construcción (Makefile).

  2. [10%] Análisis (readme.ext): problema, modelo físico (fórmulas, no imágenes), construcción, manual de usuario con ejemplos de ejecución.

  3. [10%] Casos de prueba manuales pequeños.

  4. [10%] Diseño: documento de diseño, clases en UML o pseudocódigo.

  5. [10%] Carga de archivo o genera el universo. Distribuye universo entre procesos.

  6. [10%] Envía y recibe el mínimo de información para actualizar la partición del universo en cada proceso (MPI).

  7. [10%] Implementa el modelo físico y lo paraleliza con hilos de ejecución (OpenMP).

  8. [10%] Detecta colisiones. Las masas afectadas se actualizan en ambos procesos. Detiene la simulación cuando sólo queda un cuerpo o se acaba el tiempo.

  9. [10%] Reporta estadísticas de datos distribuidos en la salida estándar. Escribe el archivo de cuerpos en modo universo de archivo.

  10. [10%] Apego a una convención de estilos (lint). Documentación de interfaces (doxygen) y de implementaciones (algoritmos).

Sugerencia: Use sobrecarga de operadores para facilitar la legibilidad del código que trabaja con vectores físicos.

Referencias:

  1. https://fisquiweb.es/Apuntes/Apuntes2Fis/LeyGravitacion.pdf