En esta práctica tendréis que implementar una verión paralela del problema de N-cuerpos. Este problema implica simular el movimiento de N cuerpos moviéndose bajo las fuerzas gravitatorias que ejerce cada cuerpo sobre todos los demás. El cómputo debería discretizarse en el tiempo, es decir, la simulación implica varios pasos de tiempo. En cada paso de tiempo, el programa calcula las fuerzas gravitatorias que se ejercen sobre cada estrella por todas las demás y actualiza la posición y velocidad de la estrella.

La fuerza gravitatoria se calcula con la siguiente fórmula:

F = K * m1 * m2 / ( r * r )

donde m1 y m2 son las masas de los dos cuerpos y r es la distancia que las separa.

La fuerza gravitatoria se usa para actualizar la nueva posición y velocidad de los cuerpos de la siguiente forma: para cada cuerpo i, la fuerza F se calcula y descompone en sus componentes Fxi y Fyi. Estas componentes se suman, obteniendose la fuerza gravitatoria total que se aplica a un cuerpo, Fx y Fy. A partir de estos valores se calculan las correspondientes aceleraciones, ax y ay, y velocidades, vx y vy, a lo largo de los ejes X e Y (ax = fx / m y vx = ax * t), donde t es el paso de tiempo.

La simulación se realiza en un espacio bidimensional. Los valores de entrada de la simulación se proporcionan en un fichero que consiste de dos partes:

• Una cabecera que contiene los parámetros globales:
  • n: el número de cuerpos.
  • k: la constante gravitatoria K.
  • t: el tamaño del paso de tiempo.
  • nsteps: el número de pasos de tiempo de la simulación.
  • d: el umbral de distancia mínimo (explicado abajo).
  • xmax: X máxima (explicado abajo).
  • ymax: Y máxima (explicado abajo).
• Una región de datos que consiste de la lista de los cuerpos, cada uno descrito por los siguientes parámetros:
  • x: la posición inicial en el eje X.
  • y: la posición inicial en el eje Y.
  • vx: la velocidad inicial en la dirección del eje X (puede ser negativa).
  • vy: la velocidad inicial en la dirección del eje Y (puede ser negativa).
  • m: la masa del cuerpo.

Suposiciones:

• Dos cuerpos que estan cerca, por debajo de un umbral d, no se atraen mutuamente (se asume así para simplificar el tratamiento de la colisión de los cuerpos). Por tanto, el cuerpo continuará moviéndose con la misma velocidad que antes.
• El espacio es finito: la esquina inferior izquierda es (0, 0) y la superior derecha es (xmax, ymax). Si la posición actualizada del cuerpo está fuera del espacio, consideraremos que colisiona con el borde exterior y cambia la dirección con el mismo ángulo que el ángulo de impacto.

Deberéis implementar un programa paralelo en MPI que realice eficientemente los cálculos. Se os proporciona una versión secuencial del programa, que toma como parámetro un fichero que contiene los parámetros de la simulación y una lista de atributos de cuerpos como se explicó anteriormente.

Deberéis implementar dos versiones del programa con diferentes estrategias de asignación:

• Mismo número de cuerpos: cada procesador recibe el mismo número de cuerpos.
• Misma carga de trabajo: la carga de trabajo se distribuye entre los procesadores.

El programa recibirá exactamente 4 argumentos:

./nbody <fichero_entrada> <fichero_salida> <X11_0|1> <tipo_reparto>

Siendo:

• <fichero_entrada> El fichero con la distribución inicial de cuerpos.
• <fichero_salida> El fichero resultante con la distribución final de cuerpos.
• <X11_0|1> 0 si el funcionamiento es en modo texto y 1 si es gráfico.
• <tipo_reparto> 0 si el reparto es por cuerpos y 1 si es por carga de trabajo.

Por ejemplo, la siguiente orden lanza 16 procesos del programa tomando como fichero de entrada ‘example’, guardará el resultado en el fichero ‘salida’, no mostrará interfaz gráfica y usará reparto por carga de trabajo:

mpiexec -n 16 ./nbody example salida 0 1

El programa (nbody.c) se entregará electrónicamente y se corregirá mediante un corrector automático, por tanto, es ESENCIAL que el tratamiento de los argumentos sea exactamente el que se pide en los Requisitos de Programación.

La versión paralela del programa consistirá de los siguientes pasos:

• Los procesos deben leer la cabecera del fichero y ponerse de acuerdo en la asignación de los cuerpos.
• Cada proceso lee sus correspondientes cuerpos del fichero de forma independiente.
• Cada proceso calcula las componentes de las fuerzas Fx y Fy para sus cuerpos asignados.
• Las fuerzas totales se calculan a través de operaciones de reducción colectivas.
• Cada proceso calcula las nuevas velocidades y posiciones par sus cuerpos asignados.
• Las nuevas posiciones se distribuyen al resto de procesos a través de una operación colectiva allgather.
• Al final los procesos deben escribir enun fichero de salida con el mismo formato que el de entrada los parametros de la simulación y los atributos de los nuevos cuerpos.

Deberéis tomar medidas para 1, 4, 8, 12 y 16 procesadores: unas con igual número de cuerpos y otras con igual carga de trabajo.

Deberéis entregar:

1. El programa comentado (¡AVISO! sólo se entrega un único fichero: nbody.c).
2. Una descripción de la metodología de paralelización basada en cuatro fases: descomposición, asignación, orquestración y reparto.
3. Gráficas de las medidas de tiempo y speedup.
4. Gráficas del reparto del tiempo total de la versión paralela en cómputo y comunicación.
5. Histogramas de la carga de trabajo de los procesadores al ejecutar las versiones paralelas del programa (sin incluir comunicaciones).
6. Interpretación de las gráficas.
7. Interpretación de los análisis de rendimiento a partir de la visualización con la herramienta jumpshot (para un subconjunto de medidas que consideréis relevante).
8. Vuestras conclusiones.

• Un programa que no compile o no funcione (ver pista número 2) recibirá 0 puntos.
• Un programa no comentado (documentado) recibirá también 0 puntos.
• El programa se entregará electrónicamente y se corregirá mediante un corrector automático, por tanto, es ESENCIAL que el tratamiento de los argumentos sea exactamente el que se pide en los Requisitos de Programación.

• Para tomar tiempos usad la funcion MPI_Wtime() de la siguiente forma:

      double tstart = MPI_Wtime();
              code to be timed
      double tfinish = MPI_Wtime();
      double TotalTime = tfinish - tstart;

• Para asegurarse del correcto funcionamiento de la versión paralela, en comparación con la versión secuencial, seguid los siguientes pasos:
  1. Ejecutar la versión secuencial con un conjunto de datos de entrada.
  2. Ejecutar las diferentes versiones paralelas con el mismo conjunto de datos de entrada que la versión secuencial.
  3. Comparar los conjuntos de datos de salida de cada versión paralela con el obtenido en la versión secuencial usando el comando diff (man diff).
  4. Si el comando diff detecta diferencias entre el fichero de salida de la versión secuencial y alguno de los ficheros de salida de las versiones paralelas se considerará que el programa no funciona correctamente y, por tanto, habrá que revisar el algoritmo paralelo.

Las prácticas se corregirán en las aulas informáticas usadas durante el curso (f1XX y f2XX). La forma de corregir la práctica será la siguiente:

Se descarga y se descomprime el código de partida inicial y se copia el nbody.c entregado a dicho directorio:

tar zxvf iiac2_2008.tar.gz
cd iiac2_2008
cp /ruta/a/nbody.c .

mpicc -c nbody.c -o nbody.o
mpicc -c video.c -o video.o
mpicc nbody.o video.o -o nbody -lm -lX11 -llmpe -lmpe

mpdboot -n 16 -f maquinas

Para cada <fichero_entrada>
  Para cada <tipo_reparto>="0 1"
    Para cada <num_procesos>="1 2 4 8 12 16"
      mpiexec -n <num_procesos> ./nbody <fichero_entrada> salida-<tipo_reparto>-<num_procesos> 0 <tipo_reparto>

mpdallexit

Para cada <fichero_entrada>
  ./nbody <fichero_entrada> salida-secuencial 0
  diff --from-file=salida-secuencial salida-0-1 salida-0-4 ... salida-0-16
  diff --from-file=salida-secuencial salida-1-1 salida-1-4 ... salida-1-16

• Código de partida