PDF de programación - Computación Cluster y Grid - Práctica de Equilibrado de Datos

Computación Cluster y Grid
Computación Cluster y Grid

Computación Cluster y Grid

Práctica de Equilibrado de Datos

1
1

Práctica: Equilibrado de Datos
Objetivo: Reducir el tiempo total de cómputo de una
aplicación Master/Slave basada en MPI utilizando
técnicas de equilibrado de datos.

Para ello se espera:

Repartir proporcionalmente la carga entre los esclavos.
Mejorar el rendimiento de la solución paralela

proporcionada.

Presentación del speed-up conseguido respecto a la

solución secuencial proporcionada.

2
2

Computación Cluster y Grid
Computación Cluster y Grid

Información para su realización
La práctica se realizará de la siguiente forma:

Grupos de hasta 2 personas
Código de apoyo:

Implementación del problema de simulación (como una biblioteca).
Implementación secuencial de referencia.
Implementación de dos solución paralelas.

Herramienta: Código desarrollado con MPI para C.
Máquina para su desarrollo:

Supercomputador Magerit

Fecha de entrega: (11-Junio) Último día de clase
Entregables:

Código.
Memoria con los resultados experimentales.

3

Computación Cluster y Grid

Aplicación: Sistema de Partículas
Se dispone de un espacio bi-dimensional en el que

residen dos tipos de objetos:
Partículas: Sujetas a diversas fuerzas que determina su

movimiento.

Repulsores: Partículas que no se ven afectadas por otras

partículas pero que sí ejercen un efecto de repulsión de
las partículas.

La aplicación simula la dinámica de un conjunto de

partículas después de N instantes de tiempo.

4

Computación Cluster y Grid

Aplicación: Sistema de Partículas
Modelo modificado de dinámica de objetos autónomos

de Craig Reynolds:
Dinámica de movimiento independiente:

Rotación: En torno al centro de coordenadas y proporcional al radio
Repulsión: Fuerza de repulsión contraria a ciertas partículas

independientes.

Dispersión: Factor aleatorio.

Dinámica de movimiento de grupo: (Steering Forces)
Entropía (distancia entre pares de partículas por su velocidad)

Si el número de partículas es bajo: Frena las partículas.
Si el número de partículas es alto: Acelera a las partículas.
Separación: Fuerza de repulsión entre cada par de partículas,

proporcional al inverso de la distancia.

Cohesión: Fuerza que tiende hacia el centro de masas del grupo de

partículas.

5

Computación Cluster y Grid

Aplicación: Sistema de Partículas
Las partículas tienden a formar pequeños grupos y a

huir de los repulsores.

La complejidad de los cálculos en el punto más pesado

es O(n3)

6

Computación Cluster y Grid

Mejora de Rendimiento
Para mejorar el rendimiento:

No se debe alterar la biblioteca de cálculo proporcionada.
Se deben plantear diferentes estrategias de división del

trabajo.

Hay que considerar:

Que el movimiento de una partícula se ve afectado por el
resto, pero sólo dentro del rango de acción (distancia 5).

La densidad en número de partículas (y el coste

computacional de su cómputo) no es igual en todas las
regiones del espacio.

La complejidad del cómputo de una partícula data

también es dependiente de cuántas partículas están en su
vecindario, así que no es constante.

7

Computación Cluster y Grid

Presentación de Resultados
Debido a que el sistema presenta dos elementos

variantes:
Determinación aleatoria de las partículas (si se altera la

semilla)

La propia ejecución paralela.

Las pruebas se realizarán:

Sobre 10 ejecuciones de cada configuración
Promediando los resultados
Las pruebas se harán con 8 y con 16 procesadores para

las configuraciones:
Partículas={400,800,1600}
Iteraciones={100,500}

8

Computación Cluster y Grid

Material de Apoyo y Referencias
Código:

http://laurel.datsi.fi.upm.es/docencia/asignaturas/ccg

“Steering Behaviors for Autonomous Characters” Craig

Reynolds

“Data-Parallel Load Balancing Strategies” Cyril Fonlupt,

Philippe Marquet, Jean-Luc Dekeyser

“Integrating Load Balancing and Locality in the

Parallelization of Irregular Problems” F. Baiardi, S. Chiti,
P. Mori, L. Ricci

Programación MPI:

http://mpi.deino.net/mpi_functions
http://www.mpi-forum.org/docs

9

Computación Cluster y Grid