MPI – Estandar de Paso de Mensaje
MPI tiene un estandar para paso de mensaje en C y Fortran. No es necesario conocer MPL, PVM, etc.
MPI es grande y pequeño:
MPI es grande, ya que contiene 125 funciones las cuales dan al programador control fino sobre las comunicaciones
MPI es pequeño, ya que los programas de paso de mensaje pueden ser escritos usando sólo seis funciones
PE 0 llama a MPI_SEND para pasar la variable real x hacia PE 1.
PE 1 llama a MPI_RECV para recibir la variable real y desde PE 0
if(myid.eq.0) then
call MPI_SEND(x,1,MPI_REAL,1,100,MPI_COMM_WORLD,ierr)
endif
if(myid.eq.1) then
call MPI_RECV(y,1,MPI_REAL,0,100,MPI_COMM_WORLD,
status,ierr)
endif
MPI Ejemplos – Send y Receive
Los mensajes en MPI son de doble dirección: ellos requieren un send y un correspondiente receive:
MPI Ejemplo – Operaciones Globales
PE 6 collects the single (1) integer value n from all other processors and puts the sum (MPI_SUM) into into sum
call MPI_REDUCE(n,allsum,1,MPI_INTEGER,MPI_SUM,6,
MPI_COMM_WORLD,ierr)
MPI también tiene operaciones globales para hacer broadcast y reduce (collect) de información
PE 5 broadcasts the single (1) integer value n to all other processors
call MPI_BCAST(n,1,MPI_INTEGER,5,
MPI_COMM_WORLD,ierr)
MPI Implementaciones
MPI está implementado para todas las máquinas de memoria distribuida.
MPI es el modelo natural para máquinas de memoria distribuida (MPPs, clusters)
MPI ofrece alto rendimiento para DSMs
MPI es útil en sistemas SMPs que forman clusters
MPI puede ser usado sobre máquinas de memoria compartida
MPI vs. OpenMP
No existe la mejor aproximación para escribir códigos paralelos. Cada una tiene sus ventajas y desventajas:
MPI – poderoso, general, y universal, compuesto de rutinas de paso de mensaje las cuales proveen un control muy fino sobre las comunicaciones, pero obliga al programador a operar en un relativo bajo nivel de abstracción.
OpenMP – conceptualmente es una sencilla aproximación para desarrollar códigos paralelos sobre máquinas de memoria compartida, pero no es aplicable a plataformas de memoria distribuida.
MPI vs. OpenMP
MPI es más general y portable (plataformas, aunque no es eficiente en sistemas SMPs)
La arquitectura y el problema a resolver frecuentemente hacen que la decisión sea suya!!!.
Librerías Paralelas
Finalmente, existen librerías matemáticas paralelas que capacitan al usuario a escribir códigos (serial), que tienen rutinas que llaman a solvers paralelos :
ScaLAPACK es para resolver sistemas lineales densos, autovalores y problemas de minimos cuadrados. También ver PLAPACK.
PETSc es para resolver ecuaciones diferenciales en derivadas parciales lineales y no lineales (incluye varios solvers iterativos para matrices dispersas).
UCSparseLib es para resolver sistemas lineales dispersos (incluye varios solvers iterativos, directos y técnicas multinivel).
Computación Paralela: Tips
Los códigos paralelos rápidos requieren un eficiente uso del escalamiento del hardware
No todos los algoritmos escalares pueden ser paralelizados bien, puede ser necesario repensar el problema
Comunicación: Necesidad de minimizar el gasto del tiempo de comunicación
Balanceo de Carga: Todos los procesadores deben hacer aprox. el mismo trabajo
Ley de Amdahl’s: Limite fundamental de la computación paralela
Rendimiento Escalar
Un código paralelo bien entendido es un buen código escalar.
Si un código escala a 256 procesadores pero sólo se obtiene un 1% de rendimiento pico, éste es un mal código paralelo.
Noticia buena: Cada cosa que usted sabe acerca de la computación serial es útil en la computación paralela!
Noticia mala: Es difícil obtener un buen rendimiento de procesadores y memoria en máquinas paralelas. Se necesita un uso efectivo de caché.
En este caso, el código paralelo ejecuta un perfecto escalamiento, pero es a partir de 32 proc. cuando se supera al serial.
Rendimiento Serial
main memory
cache
CPU
Una jerarquía de
memoria simplificada
pequeña
y rápida
grande
y lenta
La cache de datos fue diseñada con dos conceptos claves:
Localidad espacial – la cache es cargada con una linea entera (4-32 palabras) para tomar ventaja del hecho de que si un posición de memoria es requerida, posiciones cercanas probablemente también serán requeridas.
Localidad Temporal – una vez que una palabra es cargada en cache, ésta probablemente será utilizada muy pronto.
Uso efectivo de la cache
Aspectos a considerar
Existen otros aspectos a considerar para obtener un buen rendimiento serial:
Reducciones, ej., reemplazar divisiones por multiplicaciones inversas
Evaluar y reemplzar expresiones comunes
Colocar bucles en subrutinas para minimizar llamadas a subrutinas
Opciones de compilación
Ejecutar análisis interprocedimientos para eliminar operaciones redundantes
Algoritmos Paralelos
El algoritmo debe ser naturalmente paralelo!
Ciertos algoritmos seriales no se paralelizan bien. El desarrollo de nuevos algoritmos paralelos para reemplazar un algoritmo serial puede ser una de las tareas más dificiles en la computación paralela.
Mantener en mente que el algoritmo paralelo puede envolver más trabajo o más operaciones.
Algoritmos Paralelos
Mantener en mente que el algoritmo deberá:
Mínima comunicación
Balance de carga
Afortunadamente, muchos investigadores han desarrollado algoritmos paralelos, particularmente en el área de algebra computacional. No hay que reinventar la rueda, hay que tomar ventaja del trabajo hecho por otra gente:
Usar librerías paralelas desarrolladas, si es posible!
usar ScaLAPACK, PETSc, UCSparseLib, etc. cuando sea aplicable
La figura abajo, muetsra el tiempo de ejecución para un código paralelo usando dos procesadores. En ambos casos, la cantidad total de trabajo hecho es el mismo, pero en el segundo caso el trabajo está distribuido más efectivamente entre los dos procesadores resultando un tiempo más corto para obtener la solución.
(Gp:) Tiempo trabajando
(Gp:) Tiempo ocioso
t ?
PE 0
PE 1
(Gp:) PE 0
(Gp:) PE 1
Puntos de
sincronización
Balanceo de Carga
Comunicaciones
Dos parámetros claves en las redes de comunicación son:
Latencia: tiempo requerido para inicializar un mensaje. Este es un parámetro critico en los códigos grano fino, el cual requiere mucha comunicación entre procesadores.
Ancho de Banda: porcentaje de sostenibilidad el cual los datos pueden ser enviados a través de la red. Este es un parámetro critico en códigos grano grueso, el cual requiere comunicación de grandes cantidades de datos.
Sequential: t = t(comp) + t(comm)
Overlapped: t = t(comp) + t(comm) – t(comp) ? t(comm)
Más sobre Comunicaciones
El tiempo que se gasta ejecutan una comunicación es considerado overhead. Minimizar el impacto de la comunicación:
Minimizar el efecto de la latencia combinando grandes números de pequeños mensajes dentro de pequeños números de grandes mensajes.
Comunicación y cálculo no tiene que hacerse secuencialmente, se pueden solapar.
dial
“Hola máma”
hang up
dial
“Como están las cosas?”
hang up
dial
“en Venezuela.?”
hang up
dial
……
dial
“Hola máma. Como están las cosas en Venezuela.?. Bla ..Bla…”
hang up
Transmitiendo un mensaje grande, se
Tiene que pagar el precio de la latencia
Una sóla vez. Se transmite más
Información en menos tiempo.
El siguiente ejemplo de “teléfono” ilustra la importancia de combinar muchos mensajes pequeños en una más grande.
Combinando pequeños mensajes dentro de uno más grande
En el siguiente ejemplo, una operación es ejecutada sobre un arreglo 10 x 10 que ha sido distribuido en dos procesadores. Asumiendo condiciones periódicas en la frontera.
Elementos frontera – requieren datosdel procesador vecino
Elementos internos
Inicializar comunicación
Ejecutar cálculo en los elementos internos
Esperar que las comunicaciones finalicen
Ejecutar cálculo en los elementos frontera
operación:
y(i,j)=x(i+1,j)+x(i-1,j)+x(i,j+1)+x(i,j-1)
PE0
PE1
Solapando Comunicación y Cálculo
La Ley de Amdahl’s coloca un limite estricto a la aceleración que puede ser alcanzada usando multiples procesadores. Dos expresiones equivalentes para la Ley de Amdahl’s son dadas a continuación:
tN = (fp/N + fs)t1 Efecto de multiples proc. en el tiempo de ejecución
S = 1/(fs + fp/N) Efectos de múltiples proc. en la aceleración
donde:
fs = fracción serial
fp = fracción paralela = 1 – fs
N = número de procesadores
Ley de Amdahl’s
La fracción serial contenida en un código paralelo degrada el rendimiento. Esto esencialmente determina el escalamiento del código paralelo.
Ilustración de la Ley de Amdahl’s
La Ley de Amdahl’s provee un limite teórico de la aceleración asumiendo que no hay costos de comunicación. En realidad, la comunicación (y I/O) degradan el rendimiento.
Ley de Amdahl’s Vs. Realidad
Ley de Gustafson’s
La Ley de Amdahl’s predice que existe un máximo de escalabilidad para una aplicación, determinada por la fracción paralela, y este limite, generalmente, no es muy grande.
Existe un manera de solucionar esto: el tamaño del problema crezca
los problemas más grandes tienen mallas más grandes o más particulas: arreglos más grandes.
El número de operaciones seriales generalmente permanece constante; el número de operaciones paralelas crecen: crece la fracción paralela
La 1ra. Pregunta a Responder antes de Paralelizar
Detenerse a pensar
La cantidad de CPU disponibles justifican la paralelización?
Se necesita una máquina paralela para obtener suficiente memoria agregada?
El código va aser usado una sóla vez o se usará para una mayor producción?
El tiempo es valioso, se puede consumir mucho tiempo para escribir, depurar, y probar un código paralelo. Mucho tiempo se gasta en escribir un código paralelo.
La 2da. Pregunta a Responder antes de Paralelizar
Cómo se debe descomponer el problema?
Los computos consisten de un gran número de pequeños e independientes problemas – trayectorias, parámetros del espacio estudiado, etc? Se puede considerar un esquema en el cual cada procesador realiza el cálculo para diferentes conjuntos de datos
Cada computo requiere mucha memoria y CPU? Probablemente hay que distribuir un simple problema hacia multiples procesadores
 Página anterior | Volver al principio del trabajo | Página siguiente  |