Laboratorio de ParalelismoIF - EHU
LABORATORIO DE PARALELISMO
2012
Agustin Arruabarrena - Idoia Cearreta
Laboratorio de ParalelismoIF - EHU
1. Computadores Paralelos (resumen). 2. Programación de Sistemas de Memoria
Compartida (SMP): OpenMP.3. Programación de Sistemas de Memoria
Distribuida: MPI.4. Tipos de Problemas Paralelos.
Metodología de Desarrollo de Programas Paralelos.
5. Otras Alternativas: UPC.6. Trabajos Complementarios.
Programa
Laboratorio de ParalelismoIF - EHU
. 1 .COMPUTADORES PARALELOS
(resumen)
Laboratorio de ParalelismoIF - EHU
1. Estructura de los sistemas para-lelos. Máquinas SMP, DSM y MPP. Clusters. Situación actual.
2. Infraestructura de comunicaciones. Protocolos de comunicación de alto rendimiento.
3. Coherencia de los datos. Sincronización de procesos. Modelo de consistencia.
4. Modelos de paralelismo. Análisis de dependen-cias. Optimizaciones.
5. Rendimiento del sistema paralelo.
ÍndiceÍndice
Laboratorio de ParalelismoIF - EHU
C. Par. 51
Procesadores cada vez más eficientes:2-6 Gflop/s
Dos mercados:- gama “alta”
IBM → Power4, 5, PowerPC, CellIntel / HP → Itanium 2 , IA64
- gama “baja”Intel → Pentium 4, XeonAMD → Opteron
Un procesador
Laboratorio de ParalelismoIF - EHU
C. Par. 61Itanium (IA-64)
Laboratorio de ParalelismoIF - EHU
C. Par. 71IBM Power4/5
Laboratorio de ParalelismoIF - EHU
C. Par. 81IBM Power4/5
Laboratorio de ParalelismoIF - EHU
C. Par. 91IBM Power4/5
Laboratorio de ParalelismoIF - EHU
C. Par. 101
La busqueda de paralelismo a nivel de instrucción tiene un límite, marcado en muchas ocasiones por la propia aplicación (+ hard, + soft).Existen múltiples problemas para los que un solo procesador no es suficiente, por más que éste sea cada vez más rápido.
Y en otros muchos casos, es posible reducir sensiblemente el tiempo de ejecución.
Necesidad de Paralelismo
Laboratorio de ParalelismoIF - EHU
C. Par. 111
Ejemplo “simple”: meteorología
atmósfera dividida en “puntos” de 1x1x1 km3 1010 puntos
300 operaciones c.f. / elemento 3 x 1012 fcada 10 minutos (144 veces día) 5 x 1014 funa máquina a 1.000 MF/s 5 x 105 s
simular una interacción ... 6 días.Además, el tamaño de las tareas a ejecutar puede crecer todo lo que queramos.
Necesidad de Paralelismo
Laboratorio de ParalelismoIF - EHU
C. Par. 121
Solución: Paralelismo
Utilizar P (muchos) procesadores que cooperen en la resolución de un problema, para ir P veces más rápido.
+ tolerancia a fallos+ throughput +
entrada/salida
Necesidad de Paralelismo
Laboratorio de ParalelismoIF - EHU
C. Par. 131
ArrayVectorial
MP
P
Cbus
memoria compartida
SMP
MPP/NUMA
Clustersmemoria distribuida
P
C
M
red general
1
1
N
N
SIMD MIMD
SISD
fl. instrucciones
flujo
dat
osClasificación
Laboratorio de ParalelismoIF - EHU
C. Par. 141
Dos arquitecturas básicas:1. Memoria compartida (shared memory):
El espacio de direccionamiento es único. Todos los procesadores pueden acceder a todas las posiciones de memoria. La comunicación entre procesos es a través de variables compartidas.
2. Memoria Distribuida (distributed memory):Cada procesador tiene un espacio de direccionamiento privado. No existen posiciones de memoria comunes. La comunicación entre procesos es mediante paso de mensajes.
Sistemas SIMD
Laboratorio de ParalelismoIF - EHU
C. Par. 151
Espacio de Direccionamiento común privado
centralizada(bus)
distribuida(red)
MemoriaSMP
DSM, NUMA MPP
-
Sistemas SIMD
Laboratorio de ParalelismoIF - EHU
C. Par. 161
Sistemas masivamente paralelos MPPLas mejores prestaciones (velocidad de cálculo): comunicación de baja latencia y elevado ancho de banda, en algunos casos procesadores con diseño específico, software de control muy optimizado, etc. Pero COSTE MUY ELEVADO
Alternativa: clusters
Coste del sistema paralelo
Laboratorio de ParalelismoIF - EHU
C. Par. 171
Clusters
Un sistema paralelo formado por P máquinas de propósito general (bajo coste), unidas mediante una red de comunicación (igualmente de bajo coste?).Se asume que no se trabaja con el último modelo de procesador y que la latencia de las comunicaciones será algún orden de magnitud mayor que en el caso de los supercomputadores MPP. Objetivo: buena relación coste/rendimiento
Clusters
Laboratorio de ParalelismoIF - EHU
C. Par. 181
Clusters
- Alta disponibilidad (high availability): redundancia para mantener siempre la aplicación en funcionamiento.
- Alto rendimiento (high performance)capacidad de “responder” de manera
más rápida
En general: redundancia + rendimiento + escalabilidad
Clusters
Laboratorio de ParalelismoIF - EHU
C. Par. 191
hardware “habitual”- procesador “estándar” (+memoria, disco,
conexiones exterior)- red propia, con conexiones a una red global
(fast) gigabit ethernet... Myrinet, SCI, Inifiniband, Quadrics...
software “habitual”- desarrollo: MPI, OpenMP, HPF (+debuggers,
profilers...)- administración del sistema: instalación,
monitorización, diagnosis...
Clusters
Laboratorio de ParalelismoIF - EHU
C. Par. 201
Itanium / Pentium
IBM 360, PDP-11, VAX
cluster
gridASCI Red
supercomputadores
The GRID
Laboratorio de ParalelismoIF - EHU
C. Par. 211
Tipos de aplicaciones
> grano grueso (high throughput) pocas tareas independientes
simulaciones Montecarlo,procesamiento de banco de imágenes…
> grano fino (high performance) comunicación entre procesos
meteorología, simulaciones astrofísicarealidad virtual…
Niveles de paralelismo
Laboratorio de ParalelismoIF - EHU
C. Par. 221
Evolución del mercado de computadores de alta velocidad.
La lista top500.Noviembre 2011
Laboratorio de ParalelismoIF - EHU
C. Par. 231Top500
Lista de los 500 supercomputadores más rápidos del mundo ejecutando el banco de pruebas LINPACK.
Se mide el valor de Rmax, Nmax y N1/2.También se empieza a medir la potencia consumida.
Sistemas de ecuaciones lineales densos (cálculo matricial). Permite obtener velocidades muy altas (un máximo virtual).
Laboratorio de ParalelismoIF - EHU
C. Par. 241Top500
Cada 6 meses desde 1993 (junio/diciembre).
Lista nº 36 - noviembre 2011
Más o menos aceptado por todos los fabricantes.
Análisis de tendencias / evolución del mercado.
Laboratorio de ParalelismoIF - EHU
C. Par. 251Top500
Evolución de la velocidad de cálculo Top5+ Fabricantes Procesador: arquitectura / familia / número Sistema: arquitectura / red Utilización
Laboratorio de ParalelismoIF - EHU
C. Par. 261Top500
×1,88/año
74.069 TF/s9.192.843 pr.(8,1 GF/s)
1 PF/s → 200810 PF/s → 2011100 PF/s → 2015
Intel ASCI Red Sandia
IBM ASCI White LLNL
NEC Earth Sim.
BlueGene
RoadRunner
JaguarTianhe-1A
K-computer
Laboratorio de ParalelismoIF - EHU
C. Par. 271Top500
Rank Computer
N. Pr.
(cores)
Rmax Rpeak
(Tflop/s)
Power(kW)
Installation site Country/year Type
3mpp
Cray Inc, Jaguar Cray XT5 HE, AMD x86_64 Opteron, 6 core 2,6
GHzCray SeaStar2+ / Infiniband
224.162 1.7591.381 6.951 Oak Ridge N.L.
USA / 2008 -
4cluster
Nebulae, Dawning TC3600 Blade Syst. Intel EM64T Xeon X5650–
2,66 MHz Infiniband QDR120.640 1.271
2.984 2.580 Shenhzen NSCChina / 2010 Research
5cluster
TSUBAME 2.0 HP Cluster P. 3000SL
Intel EM64T Xeon X56xx - 2,93 MHz
Infiniband QDR
73.278 1.1922.288 1.399
GSIC CenterTokyo / 2010 Research
2mpp
Tianhe-1A NUDT-MPPIntel EM64T Xeon X5670 - 2,93
GHzPropietary
186.368 2.5664.701 4.040 Tianjin NSC
China / 2010 Research
1cluster
K computer FujitsuSPARC67 viiifx - 2 GHz
Tofu interc, 6D torus/mesh705.027 10.510
11.280 12.660 RIKEN AICSJapon/ 2011 Research
Laboratorio de ParalelismoIF - EHU
C. Par. 281
VP500
Y-MP C90
CM5Paragon
T3D
SP2
T3E
ASCI Red
Sun HPCCM2
Earth Sim.
Blue Gene
RoadRunnerJaguar
Tianhe-1AK computer
Top500
Laboratorio de ParalelismoIF - EHU
C. Par. 291Top500
Laboratorio de ParalelismoIF - EHU
C. Par. 301Top500
Laboratorio de ParalelismoIF - EHU
C. Par. 311
Problemas a resolver (algunos)¿cómo se reparte un algoritmo en P procesos?
- división y scheduling / load balancing¿son todos los procesos independientes?
- dependencias y sincronización
¿cómo se mantiene la coherencia de los datos?- protocolos de coherencia /
consistencia¿cuál es la arquitectura del sistema? ¿y la red de comunicación? ¿cómo se comunican los procesos?
Problemas - Objetivos
Laboratorio de ParalelismoIF - EHU
Índice
1. Estructura de los sistemas paralelos. Máquinas SMP, DSM y MPP. Clusters. Situación actual.
2. Infraestructura de comunicación. Protocolos de comunicación de alto rendimiento.
3. Coherencia de los datos. Sincronización de procesos. Modelo de consistencia.
4. Modelo de paralelismo. Análisis de dependen-cias. Optimizaciones.
5. Rendimiento del sistema paralelo.
Laboratorio de ParalelismoIF - EHU
C. Par. 331
Tanto para el caso de memoria compartida como el memoria distribuida, necesitamos un soporte de comunicación que nos permita acceder a la memoria común, centralizada o no, transmitir datos de procesador a procesador.
La red de comunicación es por tanto “independiente” del modelo, aunque haya redes adaptadas a cada uno de ellos. Repasemos las principales.
Infraestructura de comunic.
Laboratorio de ParalelismoIF - EHU
C. Par. 341
Los multiprocesadores SMP utilizan básicamente un bus como red de comunicación.
M
P
C
bus
Aunque el bus es una red cuya gestión es “sencilla” y muy conocida, tiene problemas de escalabilidad:
- sólo admite “una” comunicación simultánea.- se satura al crecer el número de procesadores.
La latencia de la memoria es independiente de la posición accedida: todas se encuentran a la misma “distancia” (UMA).
Infraestructura de comunic.
Laboratorio de ParalelismoIF - EHU
C. Par. 351
Para poder utilizar muchos procesadores y mantener un espacio común de memoria, se necesita distribuir físicamente la memoria entre los procesadores y usar otro tipo de red de comunicación.
espacio de memoria común
P
C
M
red generalR
Ahora la latencia de los accesos no es constante: el acceso a los módulos locales de memoria es mucho más rápido que al resto (NUMA).El papel de la red de comunicación puede ser crucial.
Infraestructura de comunic.
Laboratorio de ParalelismoIF - EHU
C. Par. 361
Algunas características básicas que debe cumplir una buena red de comunicación: permitir múltiples “comunicaciones”
simultáneas entre procesadores; es decir permitir comunicación con un alto throughput.
ofrecer comunicaciones de baja latencia. en la medida de lo posible, ser tolerante a
fallos. ser de fácil construcción y ampliación y
tener un routing simple.
Infraestructura de comunic.
Laboratorio de ParalelismoIF - EHU
C. Par. 371
Redes dinámicas- en base a conmutadores (switches)- redes indirectas
Redes estáticas- en base a encaminadores de mensajes (routers)- redes directas/dirigidas
Clasificación
Laboratorio de ParalelismoIF - EHU
C. Par. 381
de distancia (relacionados +/- con la latencia)distancia mediadiámetro
de throughputbisección: enlaces que hay que eliminar para dividir la red en dos partes iguales
de complejidad grado del nodonúmero de enlaces
Parámetros topológicos
Laboratorio de ParalelismoIF - EHU
C. Par. 391
0
4
6
1
3
5
7
0
2
6
1
3
5
7
0
1
23
5
67
44
2
Utilizadas en sistemas SIMD y/o para un número “moderado” de procesadores.
2
4
1
0
0 Crossbar (switch todos con todos)
Red Omega permutación perfect shuffle
Redes dinámicas
Laboratorio de ParalelismoIF - EHU
C. Par. 401
butterfly / fat tree / clos
Redes dinámicas
Laboratorio de ParalelismoIF - EHU
C. Par. 411
Utilizadas en sistemas masivamente paralelos, por su facilidad de expansión. Algunos ejemplos: Hipercubo
+ bajos parámetros topológicos alta densidad y bisección gran tolerancia a fallos- complejidad
grado no constante+ encaminamiento sencillo (xor)
Redes estáticas
Laboratorio de ParalelismoIF - EHU
C. Par. 421
Mallas / Toros (2D / 3D)+ bajo grado y constante
sencillez de construcción- parámetros de distancia
medios
+ encaminamiento sencillo(di - oi) en cada dimensiónpara toros, nunca más de medio anillo en cada
dimensión
Redes estáticas
Laboratorio de ParalelismoIF - EHU
C. Par. 431
Árboles (fat tree)
+ bajo grado y constante parámetros de distancia bajos- cableado más complejo
+ encaminamiento sencillo
Redes estáticas
Laboratorio de ParalelismoIF - EHU
C. Par. 441
Store-and-Forward Tsf = d (tr + L/B)
1234
1234234 1
4 3 124 123
1 1234
34 2 1t
(d = distancia, tr = tiempo de routing en cada nodo, B = ancho banda de los canales, L = longitud de los paquetes)
Tct = d (tr + 1/B) + (L-1)/B
Cut-Through/Wormhole
Paso de mensajes
Laboratorio de ParalelismoIF - EHU
C. Par. 451
Teniendo en cuenta el tráfico de la red
Throughput (b/s)
Tráfico (b/s) Tráfico (b/s)
Latencia (s)
Latencia a tráfico 0
Tráfico máximo
Latencia y Throughput
Laboratorio de ParalelismoIF - EHU
C. Par. 461
Básicamente, un conjunto de búferes asociados a puertos de entrada/salida, más la lógica que permite procesar las cabeceras de los paquetes y asociarles un puerto de salida.
El encaminador (router)
puertos de entrada puertos de salida
procesador localprocesador local
enlaces decomunicación
enlaces decomunicación
búfe
res
búfe
res
func
. enc
am.+
cr
ossb
ar
Laboratorio de ParalelismoIF - EHU
C. Par. 471
Estático en orden de dimensiones (DOR) sencillo y prefijado. permite evitar problemas (tales como
bloqueos). Dinámico
permite adaptarse a condiciones de tráfico local y aprovechar la riqueza topológica de la red.
añade tolerancia a fallos. pero puede implicar problemas de
bloqueos en ciertas topologías.
Encaminamiento
Laboratorio de ParalelismoIF - EHU
C. Par. 481
Mensajes que se autobloquean al consumir los recursos asignados y formar un “ciclo”.El encaminamiento estático DOR soluciona el problema en topologías que no tengan ciclos (mallas).
Deadlock
Laboratorio de ParalelismoIF - EHU
C. Par. 491
Multiplexado de los canales físicos de comunicación entre varios canales virtuales (buffers).
B0
B1 B1
B0CV0
CV1
Objetivos mejorar el rendimiento evitar bloqueos
Deadlock - Canales virtuales
Laboratorio de ParalelismoIF - EHU
C. Par. 501
El uso de canales (o redes) virtuales elimina bloqueos en anillos.
Deadlock - Canales virtuales
0
3
1
2
1→3
2→03→1
0→2 CV1
CV0
Laboratorio de ParalelismoIF - EHU
C. Par. 511
El encaminamiento adaptativo ofrece más problemas, y hay algunas soluciones parciales:
Siempre se puede utilizar una topología que, por diseño, esté libre de este tipo de problemas. Por ejemplo, un árbol (o sus equivalentes topológicos).
limitar los posibles giros: first westpermite cierto tipo de adaptatividad, pero puede
generar desequilibrios de tráfico en la red. temporizar las esperas: “red segura”
ojo con las temporizaciones.
Deadlock
Laboratorio de ParalelismoIF - EHU
C. Par. 521
Atención: el rendimiento del sistema de comuni-cación no depende únicamente del dispositivo físico de comunicación, la red.La comunicación procesador/procesador implica muchos más elementos.
red + encaminadores
interfaz + procesador (+SO?)
P1 P2
Otros elementos
Laboratorio de ParalelismoIF - EHU
C. Par. 531
memoria
usuario
memoria
usuario
Implementación habitual:
1. TCP / IPreliable / connection orientedprotocolo de los primeros clusters (y los de menor rendimiento)
copia m. sistema
copia m. sistema
int SO int SO
Protocolos de comunic.
Laboratorio de ParalelismoIF - EHU
C. Par. 541
El overhead generado por el sistema operativo y las copias van a suponer una parte importante en el tiempo total de comunicación.
overhead del protocolotiempo de transmisión
10 Mb/s 100 Mb/s 1 Gb/s
Lat. paq. corto: 50-60 µsLat. switch: 40 µs
Protocolos de comunic.
Laboratorio de ParalelismoIF - EHU
C. Par. 551
2. Active Messages (Fast Messages)Librería de comunicación de baja latencia del proyecto NOW (Berkeley).
Mensajes cortos: síncronos, request/reply- se crea el mensaje en la memoria de usuario.- el receptor crea un buffer en memoria de usuario y
envía una petición (request).- el hardware de red envía el mensaje desde la
memoria de usuario del emisor a la del receptor. - No se hacen copias en memoria del sistema: 0
copias.
Protocolos de comunic.
Laboratorio de ParalelismoIF - EHU
C. Par. 561
Estándares para clusters 1. VIA: virtual interface architectureEstándar de comunicaciones que combina las principales ideas desarrolladas en las universidades.Consorcio de fabricantes: Intel, Compaq, Microsoft...
-- antes de enviar un mensaje, se reserva en memoria física, emisor y receptor, sitio para el mensaje.
-- las operaciones send/receive consisten en enviar un descriptor del paquete a una cola de proceso de paquetes.
-- puede esperarse confirmación o seguir con el trabajo.
VIA
Laboratorio de ParalelismoIF - EHU
C. Par. 571
Estándares para clusters1. VIA: virtual interface architectureImplementaciones
-- nativa: parte del código se carga en el propio interfaz de red.
-- emulada: todo el proceso lo ejecuta el procesador del nodo (aunque con menor overhead que TCP/IP).
-- no “seguro” (reliable)!-- bajo nivel: usar un interfaz. Por ejemplo, ya hay
versiones de MPICH que soportan VIA.
VIA
Laboratorio de ParalelismoIF - EHU
C. Par. 581
2. InfiniBand (IBA)Objetivo: infraestructura de comunicaciones de altas prestaciones, basada en switches (intra) y routers (inter), para formar redes SAN (sustitución del bus compartido)
- Los nodos se conectan mediante adaptadores especiales: HCA (nodos de cómputo) o TCA (nodos auxiliares).
- Los switches interconectan los nodos de la red local, y los routers las redes locales entre sí.
- Los enlaces operan desde 2,5 Gb/s hasta 3,75 GB/s (x12), unidireccionalmente, punto a punto.
- Latencias < 6 µs para mesajes cortos.
InfiniBand
Laboratorio de ParalelismoIF - EHU
C. Par. 591Cluster Computing
Laboratorio de ParalelismoIF - EHU
C. Par. 601
MYRINET- Infraestructura de comunicaciones de alto
rendimiento (pero “cara”).
- Enlaces a 2+2 Gbit/s (full duplex) fibra ópticaSwitches en crossbar - red de Clos / cut-through
- Software propio de control de mensajes (GM)Implementaciones de Gbit ethernet / Via / Infiniband
- Latencias de paquetes pequeños: 1,2 us (Gigabit, 50 us) Throughput máximo 9,6 Gbit/s
Myrinet
Laboratorio de ParalelismoIF - EHU
C. Par. 611Myrinet
Laboratorio de ParalelismoIF - EHU
C. Par. 621Myrinet
Laboratorio de ParalelismoIF - EHU
C. Par. 631Myrinet
Laboratorio de ParalelismoIF - EHU
C. Par. 641
CUIDADO: si, por ejemplo, utilizamos PCs para formar el cluster, la conexión red/nodo se hará a través del bus PCI.¡Bien pudiera ser que fuera ese elemento el que limitara la velocidad de comunicación!
PCI → 32 bit / 33 MHz --- 64 bit / 66 MHz 110 - 480 MB/s
PCI-X → 1 GB/s (2.0 → 4 GB/s)PCI Express → 200 MB/s por canal
(× 32 → 6,4 GB/s)
Bus del PC
Laboratorio de ParalelismoIF - EHU
C. Par. 651
32 Pentium IV, 3 GHz512 MB RAM, 4 MB cacheGigabit Ethernet (PCI-E)
MPICH2
Laboratorio de ParalelismoIF - EHU
Índice
1. Estructura de los sistemas paralelos. Máquinas SMP, DSM y MPP. Clusters. Situación actual.
2. Infraestructura de comunicación. Protocolos de comunicación de alto rendimiento.
3. Coherencia de los datos. Sincronización de procesos. Modelo de consistencia.
4. Modelo de paralelismo. Análisis de dependen-cias. Optimizaciones.
5. Rendimiento del sistema paralelo.
Laboratorio de ParalelismoIF - EHU
C. Par. 671
El uso de variables compartidas implica la utilización de copias de dichas variables en las caches de cada procesador.
Esto plantea problemas nuevos en la gestión de la memoria. Por ejemplo, ¿cómo nos aseguramos de que todos los procesadores que comparten una variable “ven” en ella el valor “correcto” correspondiente a cada instante? ¿Cómo se mantiene la coherencia de los datos?
(1) Coherencia de los datos
Laboratorio de ParalelismoIF - EHU
C. Par. 681
Un sistema es coherente si los cambios que se producen en una copia de una variable van a aparecer en todas las demás “en algún momento” y en el mismo orden.
Aunque manejando los mismos conceptos, las soluciones son diferentes en función del tipo de arquitectura:
SMP snoopyDSM directorios
Coherencia de los datos
Laboratorio de ParalelismoIF - EHU
C. Par. 691
¿Cómo controlar la escritura distribuida?
A=2 A=2 A=2
mem. pral.
cache
A=2
A=3 ?
coh. no coh.
1 copia E M+ copias S O
I I A=3 M
invalidar las copias actualizar las copias + añadir estados al
bloque de datos
Coherencia: snoopy
Laboratorio de ParalelismoIF - EHU
C. Par. 701
¿Quién controla la cache?
mem. pral. A=2
A=2 A=2 A=2
A=3 ?
INV
I I
¿Y la memoria principal?- según la política de escritura
WT, WB- según el protocolo de coherencia
hardware espía, snoopy
Coherencia: snoopy
Laboratorio de ParalelismoIF - EHU
C. Par. 711
El sistema distribuido es esencialmente asíncrono. ¿Cómo controlar la atomicidad de las operaciones de coherencia? atomicidad del bus + estados transitorios
Atomicidad
Coherencia: snoopy
Laboratorio de ParalelismoIF - EHU
C. Par. 721
Cuando la red no es bus (DSM), el mecanismo de snoopy no sirve para mantener la coherencia de los datos, porque no existe un lugar común en el que aparezcan todos los accesos a memoria.
Si se necesita mantener la coherencia de los datos por hardware, es necesario utilizar algún otro tipo de dispositivo: el directorio.
Coherencia: directorios
Laboratorio de ParalelismoIF - EHU
C. Par. 731
Dispositivo que contiene la información de coherencia referida a cada bloque de memoria: cuántas copias hay, dónde están, en qué estado se encuentran... Es un dispositivo distribuido, bien junto a los módulos de memoria principal asignados a cada procesador, bien en las caches.
El protocolo es de invalidación. Se intercambian mensajes entre los procesos que tienen copia de la variable y el que tiene el trozo de directorio correspondien-te. El bloque de datos se mantiene en estado transitorio (busy) mientras dura la operación.
Coherencia: directorios
Laboratorio de ParalelismoIF - EHU
C. Par. 741Coherencia: ejemplo
1 bit proc. estado
0 ... 1 ... 0 M
L
CC = controlador de comunic.D = directorio de coherenciaL = local H = home R= remote
H
P
CCC
DMP
R
23
45
1
LD A
1 S
Laboratorio de ParalelismoIF - EHU
C. Par. 751
Los directorios de coherencia permiten mantener la coherencia de datos en un sistema DSM.
Pero hay que tener cuidado con:- el tamaño que ocupa el directorio.- el tiempo de respuesta de estas operaciones, que tienen que utilizar la red de comunicación del multiprocesador.- habrá latencias altas en ciertas operaciones
multithreading, prefetch...
Coherencia: resumen
Laboratorio de ParalelismoIF - EHU
C. Par. 761
El proceso de coherencia se aplica a las variables compartidas cuando se modifican. Aunque sea costoso, sólo se aplica a un conjunto (muy) reducido de los accesos a memoria.
Pero, ojo! la coherencia de datos se mantiene por bloques. Los procesadores pueden compartir un bloque de datos aunque no compartan ninguna variable de dicho bloque. la colocación en memoria y el reparto de datos y variables a los procesadores puede tener un efecto muy grande en el rendimiento del sistema.
Coherencia: bloques
Laboratorio de ParalelismoIF - EHU
C. Par. 771
En la mayoría de las aplicaciones es necesario regular el acceso y uso de las variables compartidas
Se necesitan accesos atómicos de tipo RMW
(2) Sincronización de proc.
...LD R1,CONTADDI R1,R1,#1ST CONT,R1...
Pi...LD R1,CONTADDI R1,R1,#1ST CONT,R1...
Pj
LD..ADDI.......STLD....ADDI.....ST CONT = 1!!!
Laboratorio de ParalelismoIF - EHU
C. Par. 781
Dos tipos básicos: - control de acceso a secciones críticas
trozos de código que se ejecutan en estricta exclusión mutua (sólo un procesador cada vez)
- sincronización entre procesos modelo productor /
consumidor: 1 a 1 eventosglobal barreras
Sincronización
Laboratorio de ParalelismoIF - EHU
C. Par. 791
Variables “cerrojo” (abierto/cerrado) para asegurar el acceso secuencial a la sección crítica.
Dos funciones para controlar el acceso a la sección crítica:
...k := k + 1;...
sección críticaLOCK(A);
UNLOCK(A);
A: cerrojo
Secciones críticas
Laboratorio de ParalelismoIF - EHU
C. Par. 801
Operaciones atómicas de lectura/escritura sobre el cerrojo. Ejemplo: Test&Set R1,A R1 := M(A); A := 1;
En un entorno SMP, limitar el tráfico es crucial.La instrucción Test&Set efectúa siempre una escritura, esté el cerrojo abierto o cerrado, y por tanto invalida el bloque en todas las caches genera mucho tráfico.
Secciones críticas
lock: T&S R1,ABNZ R1,lockRET
unlock: ST A,R0 RET
Laboratorio de ParalelismoIF - EHU
C. Par. 811
Soluciones para reducir el tráfico: Test-and-Test&Set
primero mirar y luego intentar entrar
Temporizaciones entre intentos de entrada
Secciones críticas
lock: LD R1,ABNZ R1,lockT&S R1,ABNZ R1,lock
RET
Laboratorio de ParalelismoIF - EHU
C. Par. 821
Soluciones para reducir el tráfico: Load Linked / Store Conditional
Dividir la operación atómica R(M)W en dos operaciones especiales, una de lectura (LL) y una de escritura (SC), que operan junto con un flag hardware.
Secciones críticas
lock: ADDI R2,R0,#1l1: LL R1,A
BNZ R1,l1...SC A,R2BZ R2,lockRET
unlock: ST A,R0RET
Laboratorio de ParalelismoIF - EHU
C. Par. 831
Soluciones para reducir el tráfico:
TicketsUna variable global ordena la entrada a la sección crítica
Vector de eventosLa entrada a la sección crítica se ordena mediante un vector. Cada proceso va dando paso al siguiente.
Secciones críticas
Laboratorio de ParalelismoIF - EHU
C. Par. 841
Eventos: Sincronización habitual entre productor y consumidor.
Sincronización: eventos
P1 (productor) P2 (consumidor)X = F1(Z);
Y = F2(X);
post(A);wait(A);
while (A == 0) {};A = 1;
post(A,i); wait(A,i);
Laboratorio de ParalelismoIF - EHU
C. Par. 851
Sincronización global en base a barreras: flag + contador
BARRERA (BAR, P){ bit_sal = !(bit_sal);
LOCK (BAR.lock);BAR.cont++;mi_cont = BAR.cont;
UNLOCK (BAR.lock)if (mi_cont==P) {
BAR.cont = 0;BAR.flag = bit_sal;
}else
while (BAR.flag != bit_sal) {};}
Sincronización: barreras
Laboratorio de ParalelismoIF - EHU
C. Par. 861
Orden de ejecución de las instrucciones (mem.)
El problema del orden de ejecución de las instruccio-nes de memoria se conoce como consistencia (visión global del sistema de memoria).
N procesadores no se sabe en qué orden se ejecuta el programa global
1 procesador el hardware (desorden/desorden) pero sólo hay una unidad de control (se “sabe” lo que se hace).
(3) Consistencia de la mem.
Laboratorio de ParalelismoIF - EHU
C. Par. 871
La coherencia de los datos también hace referencia al “orden”, pero de una manera más limitada. Indica que los cambios en una determinada variable se reflejarán, en algún momento, en todos los procesadores en el mismo orden.
Pero nada indica sobre el orden relativo de cambios en variables diferentes!
Consistencia de la mem.
Laboratorio de ParalelismoIF - EHU
C. Par. 881
La semántica de un programa paralelo está íntimamente ligada al orden local y al orden global.
Ejemplo (A=B=0):P1 P2A = 1; (wr) print B; (rd)B = 2; (wr) print A; (rd)
Resultados posiblesB,A 0,0 / 0,1 / 2,1 2,0 ??
2,0 es un resultado posible si P1 decide desordenar sus dos instrucciones, que para él son totalmente independientes!
Consistencia: orden de ej.
Laboratorio de ParalelismoIF - EHU
C. Par. 891
La semántica del programa paralelo se suele asegurar mediante operaciones de sincronización. Ejemplo (A=flag=0):P1 P2A = 1; while (flag==0);flag = 1; print A;
dependenciaswr1 rd1
wr2 rd2
Pero P2 puede decidir ejecutar primero rd2, porque para él no hay dependencia alguna con la instrucción anterior: el procesador local no “entiende” la sincronización del programa global!
¿debería escribir P2 A=1?
Consistencia: orden de ej.
Laboratorio de ParalelismoIF - EHU
C. Par. 901
La semántica del programa paralelo se suele asegurar mediante operaciones de sincronización. Ejemplo (A=flag=0):P1 P2A = 1; while (flag==0);flag = 1; print A;
dependenciaswr1 rd1
wr2 rd2
¿debería escribir P2 A=1?
Sólo se respeta la dependencia wr1 rd2 (A) si se respeta el orden local:
wr1 >> wr2 y rd1 >> rd2 +
wr2 rd1entonces wr1 rd2
Consistencia: orden de ej.
Laboratorio de ParalelismoIF - EHU
C. Par. 911
Incluso manteniendo el orden local, la no atomicidad de las operaciones de actualización da lugar a problemas.
Ejemplo (A=flag=0):P1 P2A = 1; while (flag==0);flag = 1; print A;
El mantenimiento de la coherencia indica que los cambios sobre una variable se ven en el mismo orden en todos los procesadores, pero no indica nada sobre el orden de los cambios en diferentes variables.
Puede imprimir A = 0 si P2 ve el cambio en flag antes que el cambio en A.
Consistencia: atomicidad
Laboratorio de ParalelismoIF - EHU
C. Par. 921
Otro ejemplo (A = B = 0)
P1 P2 P3A = 1; while (A==0);
B = 1; while (B==0);C = A;
finalmente, obtenemos C = 0
Consistencia: atomicidad
Laboratorio de ParalelismoIF - EHU
C. Par. 931
El programador de sistemas paralelos necesita saber cuál es el modelo de consistencia que se aplica, es decir, qué tipo de restricciones existen sobre el orden de ejecución de las instrucciones en cada procesador y sobre la atomicidad global de las operaciones de escritura/lectura sobre variables compartidas.
Veamos los modelos principales.
Consistencia: modelos
Laboratorio de ParalelismoIF - EHU
C. Par. 941
Extensión del modelo de orden estricto en un solo procesador.
Un multiprocesador mantiene consistencia secuen-cial si mantiene el orden local de las instrucciones en cada procesador y si el orden global de las instrucciones corresponde a un determinado entrelazado de las instrucciones de cada procesador.
Consistencia secuencial
Laboratorio de ParalelismoIF - EHU
C. Par. 951
Ejemplo:P1 a; b;P2 c; d;
a; d; c;b; c; d; b;a; a; c; b;d;
Global a; b;c; d;
?
si
si
nono
Consistencia secuencial
Laboratorio de ParalelismoIF - EHU
C. Par. 961
Mantener orden local implica no poder desordenar LD y ST, para cualquier dirección.Es decir, mantener estas cuatro ordenaciones:
wr >> rd wr >> wr rd >> rd rd >> wr
Consistencia secuencial
Laboratorio de ParalelismoIF - EHU
C. Par. 971
Mantener orden global implica no poder ejecutar ninguna operación de memoria en ningún procesador hasta que no termine completamente la anterior operación iniciada en cualquier procesador y todas sus consecuencias.
Se necesita, además, que las operaciones de memoria sean todas atómicas.
Consistencia secuencial
Laboratorio de ParalelismoIF - EHU
C. Par. 981
Mantener la consistencia secuencial implica muchas restricciones a las habituales optimizaciones en un procesador
-- no desordenar los accesos a memoria-- no usar búfer de escritura-- no reordenar código en cada procesador-- no usar registros intermedios
P1 P2 P1 P2A = 1 A = 0 r1 = 1 A =
0B = A A = r1
B = r1 ¿Alguna alternativa?
Consistencia secuencial
Laboratorio de ParalelismoIF - EHU
C. Par. 991
El conjunto de restricciones de la CS es un conjunto suficiente, pero no necesario, por lo que es posible relajar alguna de las condiciones anteriores:
+ orden: rd >> rd rd >> wrwr >> rd wr >> wr
+ atomicidad
Pero tiene que ser posible imponer en ciertos casos el orden estricto.
Consistencia relajada
Laboratorio de ParalelismoIF - EHU
C. Par. 1001
1 Total Store Ordering (TSO) / Processor Consistency (PC)
P P P
ST
MEM
LD
Se elimina la restricción wr >> rd
- permite adelantar los LD´s (esconder la latencia de los ST)- un ST no puede adelantar un LD- un LD no puede adelantar un LD
Ojo: T&S, SWAP... son LD y ST a la vez!
Consistencia relajada: TSO
Laboratorio de ParalelismoIF - EHU
C. Par. 1011
2 Partial Store Ordering (PSO)
Se eliminan las restricciones wr >> rd y wr >> wr
3 Weak Ordering (WO)
rd... wr... Sinc
Sinc
rd... wr... rd... wr...
Se permite cualquier reordenamiento de las operaciones de memoria salvo con respecto a las sincronizaciones.
Consistencia relajada: PSO
Laboratorio de ParalelismoIF - EHU
C. Par. 1021
En algunos casos es necesario imponer orden explícito.Para ello, se utilizan instrucciones especiales del lenguaje máquina: MEMBAR, STBAR, SYNC...Estas instrucciones pueden clasificarse como:
write-fence: impone orden a los wrread-fence: impone orden a los rdmemory-fence: impone orden a ambos
Consistencia relajada
Laboratorio de ParalelismoIF - EHU
C. Par. 1031Consistencia: resumen
orden de las instrucciones de memoriamodelo wr>>rd wr>>wr rd>>rd,wr sincr. wr
atom. Fence
SC todas -
TSO todas MEMBARRMWPC todas
PSO todas STBARRMW
WO todas SINC
RCsa>>w/rw/r>>srs>>s
REL,ACQ RMW
Laboratorio de ParalelismoIF - EHU
C. Par. 1041Consistencia: resumen
TSO/PC
= A
B =
sinc_acq
C =
= D
sinc_rel
E =
F =
PSO = A
B =
sinc_acq
C =
= D
sinc_rel
E =
F =
WO = A
B =
sinc_acq
C =
= D
sinc_rel
E =
F =
RC = A
B =
sinc_acq
C =
= D
sinc_rel
E =
F =
SCrd
wr
sinc_a
wr
rd
sinc_r
wr
wr
= A
B =
sinc_acq
C =
= D
sinc_rel
E =
F =
orden
Laboratorio de ParalelismoIF - EHU
Índice
1. Estructura de los sistemas paralelos. Máquinas SMP, DSM y MPP. Clusters. Situación actual.
2. Infraestructura de comunicación. Protocolos de comunicación de alto rendimiento.
3. Coherencia de los datos. Sincronización de procesos. Modelo de consistencia.
4. Modelo de paralelismo. Análisis de dependencias. Optimizaciones.
5. Rendimiento del sistema paralelo.
Laboratorio de ParalelismoIF - EHU
C. Par. 1061Modelos de paralelismo
Tipos de paralelismo (1)
(a) Paralelismo de datos
do i = 1, 1000 do i = 1001, 2000 do i = 2001, 3000A(i) = func(i) A(i) = func(i) A(i) = func(i)
enddo enddo enddo
P0 P1 P2
do i = 1, 3000A(i) = func(i)
enddo
Laboratorio de ParalelismoIF - EHU
C. Par. 1071Modelos de paralelismo
Tipos de paralelismo (1)
(b) Paralelismo de función
P0 P1
F1
F2
F3
F4
Laboratorio de ParalelismoIF - EHU
C. Par. 1081Modelos de paralelismo
Tipos de paralelismo (2)
▪ grano fino (fine grain) tareas “pequeñas” / mucha
comunicación▪ grano medio
▪ grano grueso (coarse grain)tareas “grandes” / poca
comunicación▪ grado de paralelismo
Laboratorio de ParalelismoIF - EHU
C. Par. 1091Modelos de paralelismo
▪ Maestro-esclavoUn thread master genera P threads para ser ejecutados en paralelo, que “mueren” al terminar su tarea.
▪ SPMD (Single-Program-Multiple-Data)Se ejecutan P copias iguales independientes. Las tareas se diferencian mediante el pid del proceso.
▪ MPMD (Multiple-...) Se ejecutan P programas diferentes.
Modelos de paralelismo
Laboratorio de ParalelismoIF - EHU
C. Par. 1101
Las tareas que se ejecutan en paralelo, bien sean iteraciones de un bucle o funciones, deben ser independientes, ya que se va a perder control global sobre la ejecución de las instrucciones.
Análisis de dependencias
Ejemplo:do i = 0, N-1
A(i) = A(i) + 1enddo
P0: L0 +0 S0P1: L1 +1 S1P2: L2 +2 S2… ...
En paralelo
L0 +0 S0 L1 +1 S1 L2 +2 S2 ...
Laboratorio de ParalelismoIF - EHU
C. Par. 1111Análisis de dependencias
¿Dependencias entre tareas?
Sincronización- global (barreras)- punto a punto
(eventos)
P0 P1
F1
F2
F3
F4
Laboratorio de ParalelismoIF - EHU
C. Par. 1121Análisis de dependencias
Salvo casos muy obvios, la paralelización del código (análisis de dependencias, reparto de tareas, etc.) sigue siendo responsabilidad del programador.
El análisis debe ser eficiente, ya que se necesita que una fracción importante del código sea ejecutada en paralelo.
Laboratorio de ParalelismoIF - EHU
C. Par. 1131Análisis de dependencias
dependenciaRAW
i: A =
... j:= A
antidependenciaWAR
i: = A
... j: A =
dependen. de salidaWAW i: A =
... j: A =
i j i j i j
dependencias verdaderas
dependencias de nombre
Laboratorio de ParalelismoIF - EHU
C. Par. 1141Grafos de dependencias
Bucles + Grafo de dependencias+ Distancia de la dependencia
do i = 2, N-21 A(i) = B(i) + 22 C(i) = A(i-2) + A(i+1)enddo
A(2) = B(2) + 2C(2) = A(0) + A(3)
A(3) = B(3) + 2C(3) = A(1) + A(4)
A(4) = B(4) + 2C(4) = A(2) + A(5)
A(5) = B(5) + 2C(5) = A(3) + A(6)
1
2
A, 2
A, 1
Laboratorio de ParalelismoIF - EHU
C. Par. 1151Grafos de dependencias
do i = 2, N-311 A(i) = B(i) + 22 C(i) = A(i-2)3 D(i+1) = C(i) + C(i+1)4 B(i+1) = B(i) + 15 D(i+30) = A(i)enddo
1
2
3
4
5
A, 0
A, 2
C, 0 C, 1
D, 29
B, 1
B, 1
Laboratorio de ParalelismoIF - EHU
C. Par. 1161Grafos de dependencias
+ Espacio de iteraciones
do i = 2, N-1 do j = 1, N-2 1 A(i,j) = A(i,j-1) * 2 2 C(i,j) = A(i-2,j+1) + 1 enddoenddo
1
2A 2,-1
A 0,1
i
j
Laboratorio de ParalelismoIF - EHU
C. Par. 1171Dependencias
Test de dependencias: únicamente para funciones lineales del índice del bucle.
do i = L1, L2 X(a*i+b) = = X(c*i+d)enddo
?
L1 L2
i
a*i+bc*i+d
i1 i2
d - bMCD(c,a)
Z → no hay depend.
Laboratorio de ParalelismoIF - EHU
C. Par. 1181
Paralelizar el código significa repartir tareas (iteraciones de un bucle) a procesadores. Pero hay que respetar las dependencias de datos.El problema principal son las dependencias de distancia > 0, y sobre todo aquellas que forman ciclos en el grafo de dependencias.
Siempre es posible ejecutar un bucle en P procesa-dores, añadiendo sincronización para respetar las dependencias de datos… … lo que no significa que siempre sea sensato hacerlo, pues hay que tener en cuenta el coste global: cálculo + sincronización (comunicación).
Dependencias
Laboratorio de ParalelismoIF - EHU
C. Par. 1191Paralelización de bucles
Objetivos: Repartir las iteraciones de un bucle entre
los procesadores, para que se ejecuten “a la par”.
Siempre que se pueda, que se ejecuten de manera independiente, sin necesidad de sincronizar (dependencias de distancia 0).
En función de las características del sistema (comunicación, reparto de tareas…) intentar que las tareas tengan un cierto tamaño.
Laboratorio de ParalelismoIF - EHU
C. Par. 1201Paralelización de bucles
Objetivos:
Tal vez sólo se pueda utilizar un número limitado de procesadores.
Atención al rendimiento (p. e., problemas en la cache).
Laboratorio de ParalelismoIF - EHU
C. Par. 1211
Objetivos: En los bucles de más de una dimensión,
paralelizar aquella dimensión que minimice la necesidad de sincronización entre procesadores y aumente el tamaño de grano.
Paralelización de bucles
do i = 0, N-1 do j = 1, M-1 A(i,j) = A(i,j-1) + 1enddo
enddo
P0 P1 P2 P3
Laboratorio de ParalelismoIF - EHU
C. Par. 1221Paralelización de bucles
P0
P1
P2
P3
do i = 0, N-1 do j = 1, M-1 A(i,j) = A(i,j-1) + 1enddo
enddo
Objetivos: En los bucles de más de una dimensión,
paralelizar aquella dimensión que minimice la necesidad de sincronización entre procesadores y aumente el tamaño de grano.
Laboratorio de ParalelismoIF - EHU
C. Par. 1231
Si todas las dependencias son de distancia 0, las iteraciones se pueden repartir como se quiera entre los procesadores.
Si no es así: si todas las dependencias son hacia adelante,
sincronizarlas mediante barreras. si van hacia adelante y hacia atrás,
sincronizarlas punto a punto (contadores o vectores de eventos).
intentar alguna transformación del bucle para llevar a distancia 0 las dependencias.
Bucles con y sin sincron.
Laboratorio de ParalelismoIF - EHU
C. Par. 1241Ejemplos
do i = 0, N-1C(i) = C(i) * C(i)A(i) = C(i) + B(i)D(i) = C(i) / A(i)
enddo
doall i = 0, N-1C(i) = C(i) * C(i)A(i) = C(i) + B(i)D(i) = C(i) / A(i)
enddoall
1
2
3
C, 0
A, 0
i=0 1 2 3
Laboratorio de ParalelismoIF - EHU
C. Par. 1251Ejemplos
do i = 1, N-1C(i) = C(i) * C(i)A(i) = C(i) + B(i)D(i) = C(i-1) / A(i)
enddo
forall i = 1, N-1C(i) = C(i) * C(i)A(i) = C(i) + B(i)BARRERA (...)D(i) = C(i-1) / A(i)
endforall
i=1 2 3 4
barrera
1
2
3
C, 0
A, 0
C, 1
Laboratorio de ParalelismoIF - EHU
C. Par. 1261Ejemplos
do i = 1, N-1C(i) = C(i) * C(i)A(i) = C(i) + B(i)D(i) = C(i-1) / A(i)
enddo
i=1 2 3 4
barrera
doall i = 1, N-1C(i) = C(i) * C(i)A(i) = C(i) + B(i)
enddoall[ BARERRA (...) ]doall i = 1, N-1D(i) = C(i-1) / A(i)
enddoall
1
2
3
C, 0
A, 0
C, 1
Laboratorio de ParalelismoIF - EHU
C. Par. 1271
Vectores de eventos
Ejemplos
do i = 2, N-2A(i) = B(i-2) + 1B(i+1) = A(i-2) * 2
enddo
1
2
A,2B,3 1 1 1 . . .
2 2 2 . . . 1 1 1 2 2 2
i=2 3 4 5 6 7
doacross i = 2, N-2 wait (vB,i-3)A(i) = B(i-2) + 1post (vA,i)
wait (vA,i-2)B(i+1) = A(i-2) * 2post (vB,i)
enddoacross
Laboratorio de ParalelismoIF - EHU
C. Par. 1281Ejemplos
do i = 2, N-2A(i) = B(i-2) + 1B(i+1) = A(i-2) * 2
enddo
doacross i = 2, N-2 wait (vB,i-3)A(i) = B(i-2) + 1post (vA,i)
wait (vA,i-2)B(i+1) = A(i-2) * 2post (vB,i)
enddoacross
1
2
A,2B,3
, 3
12 13 14
22 23 24 15 16 17
25 26 27
...
P0 P1 P2
Vectores de eventos no ordena las dependenciasmucho espacio en memoria
Laboratorio de ParalelismoIF - EHU
C. Par. 1291Ejemplos
do i = 2, N-2A(i) = B(i-2) + 1B(i+1) = A(i-2) * 2
enddo
1
2
A,2B,312 13 14
22 23 24 15 16 17
25 26 27
...
P0 P1 P2
doacross i = 2, N-2,3
A(i) = B(i-2) + 1wait (KA, i-1)post (KA)
B(i+1) = A(i-2) * 2
enddoacross
Contadores ordena las dependenciassin problemas de espacio en memoria
Laboratorio de ParalelismoIF - EHU
C. Par. 1301
1 1 1 1 1 1 1 1
2 2 2 2 2 2 2 2
En general, los bucles de dependencias siempre son problemáticos y hay que analizar detenidamente qué se gana y qué se pierde (coste de la sincronización, problemas de acceso a cache...).
1
2
C,1D,2
> Alternativas para el ejemplo-- wait / post ??-- 3 procesos independientes ?? -- ejecución serie ??
Ejemplos
Laboratorio de ParalelismoIF - EHU
C. Par. 1311Optimizaciones
0. Deshacer la definición de constantes y las variables de inducción.
1. Eliminar todas las dependencias que no son intrínsecas al bucle. Por ejemplo:
do i = 0, N-1X = A(i) * B(i) C(i) = SQRT(X)D(i) = X - 1
enddo
doall i = 0, N-1X(i) = A(i) * B(i)C(i) = SQRT(X(i))
D(i) = X(i) - 1enddoall
convertir X en una variable privada
Laboratorio de ParalelismoIF - EHU
C. Par. 1321Optimizaciones
2. Fisión del bucle. Si una parte del bucle hay que ejecutarla en serie, romper el bucle convenientemente y ejecutar lo que sea posible en paralelo.
do i = 1, N-1A(i) = A(i-1) / 2D(i) = D(i) + 1
enddo
do i = 1, N-1A(i) = A(i-1) / 2
enddo
doall i = 1, N-1D(i) = D(i) + 1
enddoall
Laboratorio de ParalelismoIF - EHU
C. Par. 1331Optimizaciones
3. Ordenar las dependencias (hacia adelante).
do i = 1, N-1A(i) = D(i-1) / 2D(i) = C(i) + 1
enddo
forall i = 1, N-1D(i) = C(i) + 1BARRERA (...)
A(i) = D(i-1) / 2endforall
1
2D, 1
2………….12………1 2…….1
1…2.. 1…2.. 1…2..
??
Laboratorio de ParalelismoIF - EHU
C. Par. 1341Optimizaciones
4. Alinear las dependencias: peeling.
do i = 1, N-1A(i) = B(i)C(i) = A(i-1) + 2
enddo
1
2A, 1
doall i = 1, N-2A(i) = B(i)C(i+1) = A(i) + 2
enddoall
C(1) = A(0) + 2
A(N-1) = B(N-1)
Laboratorio de ParalelismoIF - EHU
C. Par. 1351Optimizaciones
do i = 2, N-1A(i) = B(i)C(i) = A(i-1) + A(i-2)
enddo
1
2
A, 2 A, 1
C(2) = A(1) + A(0)C(3) = B(2) + A(1)
doall i = 2, N-3A(i) = B(i)X(i+1) = B(i+1)C(i+2) = X(i+1) + A(i)
enddoall
A(N-2) = B(N-2)A(N-1) = B(N-1)
do i = 2, N-1A(i) = B(i)X(i) = B(i)C(i) = X(i-1) + A(i-2)
enddo
1’
2
A, 2 X, 1
1
Laboratorio de ParalelismoIF - EHU
C. Par. 1361Optimizaciones
5. Generar hilos independientes
do i = 0, N-3A(i+1) = B(i) + 1B(i+2) = A(i) * 3C(i) = B(i+2) - 2
enddo
B(2) = A(0) * 3C(0) = B(2) - 2
doall pid = 0, 2 do i = pid, N-4, 3 A(i+1) = B(i) + 1 B(i+3) = A(i+1) * 3 C(i+1) = B(i+3) – 2 enddoenddoall
A(N-2) = B(N-3) + 1
1
2
3B,0
B,2 A,1 1 1 1 1 1 12 2 2 2 2 23 3 3 3 3 3
Laboratorio de ParalelismoIF - EHU
C. Par. 1371Optimizaciones
6. Minimizar la sincronización
do i = 2, N-1B(i) = B(i) + 1
C(i) = C(i) / 3A(i) = B(i) + C(i-1)D(i) = A(i-1) * C(i-2)E(i) = D(i) + B(i-1)
enddo
1
2
3
B,0
B,1
A,14
5
C,
1C,2
D,0
doacross i = 2, N-1B(i) = B(i) + 1
C(i) = C(i) / 3post (vC,i)
wait (vC,i-1)A(i) = B(i) + C(i-1)post (vA,i)
wait (vA,i-1)D(i) = A(i-1) * C(i-2)E(i) = D(i) + B(i-1)
enddoacross
1 2 3 4 51 2 3 4 51 2 3 4 5
i=234...
Laboratorio de ParalelismoIF - EHU
C. Par. 1381Optimizaciones
7. Tratamiento de bucles: intercambio.
do i do_par j
do_par i do j
do j do_par i
do_par j do i
Laboratorio de ParalelismoIF - EHU
C. Par. 1391Optimizaciones
Ejemplo:
do i = 1, N-1 do j = 0, N-1
A(i,j) = A(i-1,j) + 1
enddoenddo
do i = 1, N-1doall j = 0, N-1
A(i,j) = A(i-1,j) + 1enddoall
enddo
j=0 1 2 3i=1
2
3
4
Laboratorio de ParalelismoIF - EHU
C. Par. 1401Optimizaciones
Ejemplo:
doall j = 0, N-1do i = 1, N-1
A(i,j) = A(i-1,j) + 1enddo
enddoall
do i = 1, N-1 do j = 0, N-1
A(i,j) = A(i-1,j) + 1
enddoenddo
j=0 1 2 3i=1
2
3
4
Laboratorio de ParalelismoIF - EHU
C. Par. 1411Optimizaciones
8. Tratamiento de bucles: cambio de sentido.
j=0 1 2 i=1
2
3
4
do i = 1, 100 do j = 0, 2 A(i,j) = A(i,j) - 1 D(i) = A(i-1,j+1) * 3
enddoenddo
do j = 2, 0, -1
doall i = 1, 100 A(i,j) = A(i,j) - 1 D(i) = A(i-1,j+1) * 3
enddoallenddo
Laboratorio de ParalelismoIF - EHU
C. Par. 1421Optimizaciones
do j = 1, 2N-1 doall i = max(1,j-N+1), min(j,N) A(i,j-(i-1)) = A(i-1,j-(i-1)) + A(i,j-1-(i-1)) enddoallenddo
9. Skew
do i = 1, N do j = 1, N A(i,j) = A(i-1,j) + A(i,j-1) enddoenddo
Laboratorio de ParalelismoIF - EHU
C. Par. 1431Optimizaciones
10. Otras optimizaciones típicas Aumento del tamaño de grano y reduccción del overhead de la paralelización.- Juntar dos bucles en uno (¡manteniendo la semántica!): fusión.- Convertir un bucle de dos dimensiones en otro de una sola dimensión: colapso o coalescencia.…
Laboratorio de ParalelismoIF - EHU
C. Par. 1441Reparto de tareas / iterac.
¿Cómo se reparten las iteraciones de un bucle entre los procesadores?Si hay tantos procesadores como iteraciones, tal vez una por procesador.
Pero si hay menos (lo normal), hay que repartir. El reparto puede ser:
estático: en tiempo de compilación.dinámico: en ejecución.
Laboratorio de ParalelismoIF - EHU
C. Par. 1451Reparto de tareas / iterac.
El objetivo: intentar que el tiempo de ejecución de los trozos que se reparten a cada procesador sea similar, para evitar tiempos muertos (load balancing).
En todo caso, OJO con las dependencias (sincronización), el tamaño de grano, la localidad de los accesos y el coste del propio reparto.
Laboratorio de ParalelismoIF - EHU
C. Par. 1461Reparto de tareas / iterac.
Planificación estática
Qué ejecuta cada procesador se decide en tiempo de compilación. Es por tanto una decisión prefijada.Cada proceso tiene una variable local que lo identifica, pid [0..P-1].Dos opciones básicas: reparto consecutivo y reparto entrelazado.
Laboratorio de ParalelismoIF - EHU
C. Par. 1471Reparto de tareas / iterac.
- No añade carga a la ejecución de los threads.- Pero no asegura el equilibrio de la carga entre los
procesos.- Permite cierto control sobre la localidad de los accesos a
cache.
▪ Consecutivo 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
15 0 0 0 0 1 1 1 1 2 2 2 2 3 3 3 3
▪ Entrelazado 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
0 1 2 3 0 1 2 3 0 1 2 3 0 1 2 3
principio = pid * N/Pfin = (pid+1) * N/P – 1do i = principio, fin
...enddo
do i = pid, N, P...
enddo
Laboratorio de ParalelismoIF - EHU
C. Par. 1481Reparto de tareas / iterac.
Equilibrio en el reparto de carga
1-2021-4041-6061-80
estático (fijo)
Tej
asignación dinámica de
una nueva tarea
1-10
21-3011-20
31-40Tej
do i = 1, 80if (A(i) > 0) calcular()
enddo
Laboratorio de ParalelismoIF - EHU
C. Par. 1491Reparto de tareas / iterac.
Planificación dinámica
Para intentar mantener la carga equilibrada, las tareas se van escogiendo en tiempo de ejecución de un cola de tareas. Cuando un proceso acaba con una tarea (un trozo del bucle) se asigna un nuevo trozo. Dos opciones básicas: los trozos que se van repartiendo son de tamaño constante o son cada vez más pequeños.
Laboratorio de ParalelismoIF - EHU
C. Par. 1501Reparto de tareas / iterac.
Las iteraciones se reparten una a una o por trozos
Self / Chunk scheduling
Añade carga a la ejecución de los threads. Hay que comparar ejecución y reparto.
LOCK (C); mia = i; i = i + Z; Z = 1 selfUNLOCK (C);while (mia <= N-1)
endwhile
do j = mia, min(mia+Z-1, N-1) ...enddoLOCK (C) mia = i; i = i + Z;UNLOCK (C)
Laboratorio de ParalelismoIF - EHU
C. Par. 1511Reparto de tareas / iterac.
Los trozos de bucle que se reparten son cada vez más pequeños según nos acercamos al final.
Guided / Trapezoidal
▪ Guided : parte proporcional de lo que queda por ejecutar:
Zs = (N – i) / P (entero superior)
que equivale a: Zi = Zi-1 (1 - 1/P)
Laboratorio de ParalelismoIF - EHU
C. Par. 1521Reparto de tareas / iterac.
▪ Trapezoidal: reduciendo el trozo anterior en una constante: Zi = Zi-1 - k
op. de planificación
Z1
Zn
1 n2 i
kZ2
)(21
22 1
22111
1
1
n
nnnn
s
ns ZZN
ZZkNkZZZZnZZZ
Laboratorio de ParalelismoIF - EHU
C. Par. 1531Reparto de tareas / iterac.
En general, el reparto dinámico busca un mejor equilibrio en el reparto de carga, pero:
- hay que considerar la carga que se añade (overhead), en relación al coste de las tareas que se asignan.- hay que considerar la localidad en los accesos a los datos y los posibles problemas de falsa compartición.
Laboratorio de ParalelismoIF - EHU
C. Par. 1541Reparto de tareas / iterac.
Ejemplo de reparto (1.000 iteraciones, 4 procesadores):▪ chunk (Z = 100)
100 100 100 100 100 100 100 100 100 100 (10)
▪ guided quedan: 1000 750 562 421 … 17 12 9 6 4 3 2 1 se reparten: 250 188 141 106 … 5 3 3 2 1 1 1 1(22)
▪ trapezoidal (Z1 = 76, Zn = 4 >> k = 3)76 73 70 67 … 16 13 10 7 4 (25)
Laboratorio de ParalelismoIF - EHU
C. Par. 1551Paralelismo de función
Paralelismo a nivel de procedimiento o función:
F2
F3
F1
F4
F5
- modelo Fork / Join
- Parallel sectionsFork
F1F2
JoinFork
F3F4
JoinF5
doall k = 0, 1if (pid = 0) then F1if (pid = 1) then F2
endoall[barrera]doall k = 0, 1
if (pid = 0) then F3if (pid = 1) then F4
endoallF5
Laboratorio de ParalelismoIF - EHU
Índice
1. Estructura de los sistemas paralelos. Máquinas SMP, DSM y MPP. Clusters. Situación actual.
2. Infraestructura de comunicación. Protocolos de comunicación de alto rendimiento.
3. Coherencia de los datos. Sincronización de procesos. Modelo de consistencia.
4. Modelo de paralelismo. Análisis de dependen-cias. Optimizaciones.
5. Rendimiento del sistema paralelo.
Laboratorio de ParalelismoIF - EHU
C. Par. 1571
El objetivo de un sistema de P procesadores es ejecutar el código P veces más rápido.
Problemas (algunos):- ¿puede ejecutarse todo el código en paralelo? ¿está bien repartida la carga?- ¿dónde están los datos? ¿cuál es el coste de la transmisión de datos?- ¿cuál es el coste de la sincronización?- ¿es eficiente el uso de la memoria cache?
Rendimiento
Laboratorio de ParalelismoIF - EHU
C. Par. 1581
Ejecución en un procesador (código serie, no la versión paralela de 1 procesador) TsEjecución en P procesadores Tp
fa = Ts / Tp límite Pideal: crecer linealmente con P
efic = fa / P límite 1ideal: constante
Rendimiento
Laboratorio de ParalelismoIF - EHU
C. Par. 1591
La parte más lenta (serie) en la ejecución de un pro-grama marcará la velocidad de ejecución del mismo.
Serie Ts Paralelo Ts / PParte en paralelo (f), pero parte en serie
(1-f)fa (speed-up) = Ts / Tp = Ts / (f*Ts/P + (1-f)Ts)
= 1 / (1-f) (máximo)= independiente de P!
¿Es todo el código paralelizable? En general, no.- Ley de Amdahl (tamaño constante)
Rendimiento
Laboratorio de ParalelismoIF - EHU
C. Par. 1601
0
20
40
60
80
100
0 20 40 60 80 100
fact
or d
e ac
eler
ació
n
número de procesadores
f = 0,8 f = 0,9 f = 0,95
factor de aceleracion lineal (p)
Rendimiento
Laboratorio de ParalelismoIF - EHU
C. Par. 1611
- Ley de Gustafson (tiempo constante)En muchos casos, se utiliza el paralelismo no para ir más rápido, sino para ejecutar tareas de mayor tamaño.
0
10
20
30
40
0 10 20 30 40 fa
ctor
de
acel
erac
ión
número de procesadores
f constante
ideal t constante
fa = (1-f) + f*p f*Ts
(1-f)*Ts
f*Ts*p(1-f)*Ts
(1-f)*Ts
mayor tamaño
p procesadores
f*Ts
Rendimiento
Laboratorio de ParalelismoIF - EHU
C. Par. 1621
A la fracción de código en paralelo, hay que añadirle una serie de overheads; por ejemplo, la comunicación debida al reparto o recolección de datos en unos casos y a la sincronización de procesos en otros.
T_ej T_com
n. de procesadores
T_total
Tp = Ts / P + Tcom(P)
Rendimiento
Laboratorio de ParalelismoIF - EHU
C. Par. 1631
Load balancingOtra fuente típica de perdida de eficiencia en la ejecución en paralela es el reparto no equilibrado de tareas.
Ejemplo: 6 tareas independientes, de peso equivalente,
▪ entre 3 procesadores Tp = Ts/3▪ entre 4 procesadores Tp = Ts/3
Rendimiento
Laboratorio de ParalelismoIF - EHU
C. Par. 1641
No podemos olvidarnos de la memoria cache. Para que su uso sea eficiente, se necesita reutilizar los datos que se cargan (un bloque o line).Por ejemplo, si A(1) y A(2) están en posiciones consecutivas de memoria, tal vez sea conveniente que se procesen en el mismo procesador para aumentar la tasa de aciertos de la cache. Por otra parte, todos los overheads que añada la ejecución paralela hay que valorarlos en función del tamaño de grano, es decir en relación al tiempo de ejecución.
Rendimiento
Laboratorio de ParalelismoIF - EHU
fin del resumen