PDF de programación - Parte II: Introducción al Paralelismo - Técnicas de Computación Científica

Técnicas de Computación Científica

Parte II: Introducción al Paralelismo

      FIM ­  2008/9

Vicente Martín
        v0.1a

Temario

● Ideas Generales Sobre Paralelismo.
● Herramientas de Programación Paralela.

– OpenMP.
– MPI: Message Passing Interface.
– UPC: Unified Parallel C
– HPF: High Performance Fortran.

Arquitecturas Paralelas

● Varios procesadores cooperan simultáneamente 

en la ejecución de un proceso.
– Pueden compartir un único espacio de direcciones.
– Cada procesador puede tener acceso exclusivo a su 

propio espacio de direcciones. Si otro procesador 
requiere una posición determinada su contenido es 
enviado a través de algún tipo de red. No hay acceso 
directo.

Arquitecturas: Taxonomía

● Muchas clasificaciones. Una de las más típicas es la 

de Flynn:
– Clasificación según el número de flujos de 

datos/instrucciones.

● SISD: Flujo de instrucciones/datos únicos (eg: ordenador 

secuencial. Vectoriales... según opiniones )

● SIMD: Único de instrucciones/múltiple de datos (eg: ordenador 

vectorial, conjuntos de instrucciones SSE o Altivec. CM­1)
● MISD: Múltiple de instrucciones/único de datos (C.mmp, 

procesadores sistólicos. Todos experimentales)

● MIMD: Múltiple de instrucciones y datos (eg: La gran mayoría 

de ordenadores paralelos y la más importante desde nuestro 
punto de vista)

Clasificación de 
Arquitecturas 

paralelas

Ejemplo: cc­NUMA

Silicon Graphics Origin 2000: Cada placa 
contiene dos procesadores que comparten una 
memoria jerarquizada local. Las caches de todos 
los procesadores se mantienen coherentes (cc). 
El espacio global de toda la máquina es único. 
El acceso a bancos de memoria situados 
físicamente en procesadores remotos se hace a 
través de una red de interconexión. El peor 
tiempo de acceso a la memoria local es de 318 
ns, en el peor caso de una máquina con 64 
nodos es de 1067 ns. 

Ejemplo: Multicomputador

En la IBM SP2 cada nodo es una estación de trabajo con su propio espacio de direcciones 
bajo el control exclusivo de su propio sistema operativo. El acceso a una posición de memoria
perteneciente a otro nodo requiere la comunicación de dos SO independientes con un paso de
 mensajes explícito, en este caso ayudado por HW específico: el High Performance Switch

Redes de Interconexión/Topologías

Las conexiones de los 
procesadores con los 
bancos de memoria se 
pueden realizar de 
muy diversos modos.
Siempre acaban siendo 
un compromiso entre 
el número de conexiones
(coste), el ancho de 
banda y el número
máximo de saltos 
(diámetro) que se 
pretende obtener/tolerar. 

Steen 03

Más sobre Topologías

Anchura de bisección: 
número mínimo de 
conexiones a cortar
para obtener dos
sistemas iguales 
(+/­ un nodo).
Ancho de banda en 
bisección: Ancho de 
banda a través de los
nodos cortados al 
obtener la anchura 
de bisección. 

El número de CPUs en 
esta gráfica esta referida
a una SGI Origin 2000
(4 CPUs por nodo)

Ammon 98

Algunos ejemplos.

Ambos multiprocesadores: Memoria compartida

SGI Origin 2000 [Laudon 98]

Cray T3D

Algunas Redes Típicas.

● SCI: Scalable Coherent Interface. Estándar ANSI 

en 1992. Estructura en anillo de 1, 2 o 3 
dimensiones. Es capaz de mantener la coherencia 
entre las caches de los procesadores que conecta, 
de manera que podría sustituir a un bus de un 
multiprocesador, aunque su uso en clusters es 
sólo como conexión entre nodos. Puede ser la 
base para implementar una memoria compartida 
virtual. 320 MB/s ping­pong, latencias de 1­2 
microsegundos. mensajes cortos.

● QsNet: Quadrics. Evolución de las redes de 

interconexión de las Meiko Computing Surface. 
Usadas despues en las Alphaserver SC. Fat tree. Se 
compone de un switch (de 16 o 128 puertos) y 
tarjetas adaptadoras PCI­X. QsNet II (2003) alcanza 
hasta 1.3 GB/s (300 MB/s QsNet I). Latencias de 3­5 
microsegs.

● Myrinet: Myricom. Switch de 8 a 256 puertos (hasta 

16 crossbar completos, después red Clos) y tarjetas 
PCI­X en los nodos. 230 MB/s (ping­pong). 7 
microsegs. en mensajes cortos. 

● Infiniband. Especificación de 2001. Puede ser 
usada para conexiones entre subsistemas o entre 
procesadores. Precio alto, pero se espera que, por su 
versatilidad y al ser no propietario, se extienda y 
abarate. Especificaciones para conexiones de cobre 
y fibra óptica. Define un link básico de 312.5 MB/s 
y otros dos de velocidad 4x y 12x (3.75GB/s). Dos 
tipos de adaptadores (que se pueden conectar 
directamente) y switches de 8­128 puertos y 4x. 
Ping­pong a 850MB/s, 7 microsegundos en 
mensajes cortos.

Parámetros típicos.

RDMA: Remote Direct
Memory Access

VAPI: Verb­Based API, 
interfaz SW para Infiniband
GM: (Glenn's Messages?) 
Capa de bajo nivel de paso 
de mensajes en Myrinet.
ElanLib: librería de 
comunicaciones para Quadrics 

Liu et al.  “Microbenchmark Performance comparison of High­Speed Cluster Interconnects”, IEEE Micro, 
Jan­Feb. 2004, pag. 42.

900 MB/seg. límite por PCI­X
Infiniband permite bastante más

Liu et al.  “Microbenchmark Performance comparison of High­Speed Cluster Interconnects”, IEEE Micro, 
Jan­Feb. 2004, pag. 42.

Top500 network family

GRID 

Computing

● Capability computing
vs. Capacity computing

Dongarra 04

Grid Computing

Thompson

Cloud Computing

● Is not grid computing: as defined by some sort of “virtual 

supercomputer”

● Is not Utility computing: As defined by offering a 

computing resource as if it was a common utility (e.g.: 
electricity)

● Is not autonomic computing:As defined by  self managed 

resources.

But it shares characteristics from the three. some examples: 

BitTorrent, Skype, volunteer computing (Seti@home is 
now seen as cloud computing...)

See: http://en.wikipedia.org/wiki/Cloud_computing

Ideas Generales Sobre Paralelismo

● Ya conocemos la taxonomía de máquinas 

paralelas. Desde nuestro punto de vista sólo nos 
importa:
– Si el sistema es un multiprocesador o un 

multicomputador (espacio de direcciones compartido 
o distribuido)

– Si los tiempos de acceso a memoria son uniformes o 

no (UMA vs. NUMA)

Multiprocesador vs. Multicomputador
● La tendencia es intentar proveer al usuario con un 

entorno que esconda en la medida de lo posible las 
diferencias arquitecturales: Número de CPU, tiempos 
de acceso a memoria, existencia o no de varios espacios 
de direcciones...

● Está distante el momento en que ésto pueda conseguirse 
sin mermas importantes en el rendimiento, de momento 
hay algunas consideraciones (aproximadas) que 
diferencian el comportamiento de un multicomputador 
del de un multiprocesador. 

● Los multiprocesadores manejan mejor el cambio de 

proceso. Esto es importante si los procesos son grandes 
y están ejecutándose en varias CPUs.
– Un Multicomputador es más adecuado para correr un sólo 

trabajo grande hasta su finalización o para correr multitud de 
trabajos más pequeños que quepan bien en la memoria local 
(throughput)

– Un nodo de un multiprocesador tiene acceso sin problemas a 

toda la memoria de la máquina (i.e. procesos de cualquier 
tamaño), no ocurre lo mismo con un nodo de un 
multicomputador.

● Un multicomputador necesitará paso explícito de 

mensajes, aunque alguna capa SW lo oculte.
● Es más difícil particionar un multiprocesador.

Top 5 del 

Multicomp. 
Con 32768 
procesadores 
PPC a 0.7GHz 
incluidos en un
ASIC  que 
integra casi 
todo. Red propia
(Toro  3D +
árbol). Linux

 

Multicomputador de 20 
multiprocesadores NUMA
de 512  CPUs (Itanium 2) cada 
uno. Infiniband. Linux.

 Top 500
Multicomp.
 con 640 nodos
multiprocs
de 8 CPUS 
vectoriales 
NEC SX8 por
cada. Red 
propietaria
(12.3 GB/s
entre nodos)

Multicomputador de 2268 nodos
biprocesadores SMP (PPC970).
Myrinet. Linux (config. con 1781 nodos) 

Multicomputador de 1024  nodos 
tetraprocesadores SMP (Itanium 2).
 Quadrics. Linux.

Rendimiento: Generalidades

● La importancia de la velocidad de acceso a memoria 

viene expresada por el hecho de que la principal división 
de máquinas sea UMA­NUMA: La localidad de datos 
será un factor clave en el rendimiento. Así que 
analizaremos primero el efecto de las comunicaciones:

● Definiciones (débiles):

–        Tiempo típico requerido para una operación genérica 

–         Tiempo típico requerido para comunicar una palabra 

t calc
(eg.: a=b∙c)
t com
entre dos nodos 

●         : Tiempo de cálculo empleado por un paso 

T calc
completo de un algoritmo en un nodo (Ej.: 
Actualización de todos los pixels asociados a un 
procesador en un algoritmo gráfico). En general:

T calc= x t calc

   donde x dependerá del algoritmo y del número de elementos, n, 
asignados al procesador por la descomposición del subdominio 
(granularidad)
T com
mismo paso.

●          : Tiempo de comunicaciones usado durante el 

T com=y t com

   de nuevo, y depende del algoritmo y del número de elementos n.

●     : Carga fraccional de comunicaciones 

f c
(communication overhead). Cociente entre el tiempo 
dedicado a las comunicaciones y el empleado en cálculo.

f c=

T com
T calc

= y
x

t com
t calc

f c
–       Depende del HW a través de la razón                  que es un 
número fijo para un HW dado. Valores típicos entre 1 y 200.
f c
lo hace indirectamente a través de n.

–       No depende directamente del número de procesadores: 

t com/tcalc

● La carga fraccional de comunicaciones tiene una relación 
directa con la topología del problema/algoritmo. Para una 
dimensión topológica d, tenemos típicamente:

f c= C

n1/ d ×

tcom
tcalc

  C depende del algoritmo, valores típicos entre 0.1 y 10.
● Ejemplos de d:

– Problemas unidimensionales, problemas físicos con fuerzas de 

largo alcance: d=1.

– Inversión de matrices, autovalores, convoluciones: d=2
– Matrices dispersas en problemas de elementos finitos  2D: d=3
– FFT: 

×

f c~ C
log n

t com
t calc

Además de las comunicaciones hay otras cargas por las 
que no se obtienen los valores de rendimiento ideales:
● Algoritmo no óptimo: puede no haber un algoritmo 

paralelo tan eficiente com