TEMA 5: PARALELISMO A NIVEL DE HILOS, TAREAS Y PETICIONES (TLP, RLP) (primera parte). SISTEMAS PARALELOS Y DISTRIBUIDOS. 3º GIC www.atc.us.es Dpto. de Arquitectura y Tecnología de Computadores. Universidad de Sevilla 1

INDICE • 5.1. Conceptos básicos. • 5.2. Taxonomía y modelos de procesamiento paralelo. – 5.5. – 5.6.

Multiprocesadores con memoria centralizada. Multiprocesadores con memoria distribuida.

• 5.3. Caracterización de las aplicaciones y Modelos de programación paralela. • 5.4. Redes y topologías de interconexión. • 5.7. Sincronización y consistencia de memoria. • 5.8. Sistemas multicomputadores para HPC. • 5.9. Sistemas distribuidos para servicios y almacenamiento de datos (WSC). SPD. Tema 5. 2

ESQUEMA DE MULTIPROCESADOR Multiprocesador: término general

Remoto

Local

SPD. Tema 5. 3

Componentes del tiempo de ejecución

Hallar Areal, Aideal

SPD. Tema 5 . 4

Argumentos a favor de Multiprocesadores Single Processor Performance Move to multi-processor

RISC

CISC

SPD. Tema 5 . 5

Puntos débiles de Multiprocesadores (I) – Recordar Ley de Amdahl Ej: queremos conseguir una aceleración de 80, con 100 procesadores ¿Qué fracción del programa debe ser paralela?

F

99,75

EJ : Un compilador intenta paralelizar un código, y lo consigue en la mitad del programa

A

1 1 F

1 F N

1 2

1 2* N

2N N 1

2

SPD. Tema 5 . 6

Puntos débiles de Multiprocesadores (II) • Difícil extracción de paralelismo: – “Artesanal” – Automática sólo si es evidente – Difícil analizar si una aplicación es paralelizable.

• Lentitud en las comunicaciones – Si un procesador necesita un dato remoto alta latencia, del orden de microsegundos (Latencia a memoria local es del orden de pocos ns)

SPD. Tema 5 . 7

5.2. Taxonomía y modelos de procesamiento paralelo • Clasificación de Flynn (años 60) – Single / Multiple – Instruction / Data (flows) • • • •

SISD SIMD MISD MIMD

• PUNTOS CLAVE EN EL DISEÑO: – Red de interconexión – La forma de organizar la jerarquía de memoria SPD. Tema 5. 8

5.2. Taxonomía y modelos de procesamiento paralelo • Según Organización de la memoria principal Disposición lógica Espacio direcc. Espacio Disposición compartido disjunto de direcc. física Memoria centralizada

Memoria distribuida

UMA

No tiene sentido

NUMA MPM

Igual software, Procesos distinto hardware. en Paralelo Threads en Paralelo

SPD. Tema 5. 9

UMA (Uniform Memory Access) –Tiempo de acceso uniforme para toda dirección –Tb .llamados SMP’s (Multiprocesadores simétricos) –Ej: casi todos los multicore actuales –Cuello de botella: acceso a memoria principal : •Grandes cachés en cada procesador •AB solicitado por cada procesador crece cada vez más •Número de procesadores no puede ser alto. Hoy N 32. P1

P2

P3

P4

Caché: 1 ó más niveles

Caché: 1 ó más niveles

Caché: 1 ó más niveles

Caché: 1 ó más niveles

Subsistema de interconexión simple: latencia baja y constante Memoria Principal

E/S SPD. Tema 5. 10

NUMA (NonUniform Memory Access) • Tiempo de acceso a memoria No uniforme • Ventaja: compatibles con UMA (se aprovecha el código) – Hace 10 años poco habituales: supercomputadores investigación – Hoy: Intel Core con QuickPath Interconnect, AMD Opteron con HyperTransport

• Otros diseños posibles: COMA (Caché Only Memory Architecture) y mixtos (investigación) P1

P2

P3

P4

Cachés y memoria

Cachés y memoria

Cachés y memoria

Cachés y memoria

Subsistema de interconexión complejo: latencia alta SPD. Tema 5. 11

Coherencia entre cachés • Comunicación implícita (variables compartidas) • Una misma línea replicada en varios procesadores Hard adicional para solucionarlo.

• En UMA: Protocolos de husmeo (snooping): – Protocolo ISX (y otros): similar al de Copy Back • Línea Inválida (Invalid) 2 cores ejecutan: P1 P2 • Línea Compartida (Shared) a[0]++; a[0]++; • Línea eXclusiva (eXclusive) a[1]++; a[2]++;

• En NUMA: coherencia más difícil de mantener en hard: directorios • CUIDADO: falsas comparticiones (false sharing). SPD. Tema 5. 12

MPM (Message Passing Machines) – Espacio de direcciones de memoria distribuido – Cada procesador es un computador independiente del resto: “multicomputador” – Fácilmente escalable (excepto AB red) – Comunicación explícita a través de mensajes (igual que la comunicación entre procesos del S.O.). P1

P2

P3

P4

Cachés y memoria

Cachés y memoria

Cachés y memoria

Cachés y memoria

Subsistema de interconexión complejo: paso de mensajes (latencia muy alta) SPD. Tema 5. 13

Herramientas de programación • Muchos intentos (y siguen…) • Lenguaje de programación paralelo: – No es factible: Difícil de imponer

• Espacio de direcciones compartido – OpenMP: estándar (varios fabricantes importantes: HP, IBM, SUN, SG...) de directivas del precompilador.

• Espacio de direcciones disjuntos: clusters de computación. – Librería Message Passing Interface (MPI): especificación para librerías de paso de mensajes SPD. Tema 5 . 14

OpenMP: descripción (I) • Espacio de direcciones compartido • Permite paralelismo “incremental” • Modelo de programación paralela SPMD (Single Program Multiple Data) – Todos los threads ejecutan la misma copia del código. – A cada thread se le asigna un identificador (tid) – Para diferenciar lo ejecutado por cada thread: • if (tid == 0) then ... else ... • constructores específicos de reparto de tareas (work sharing). SPD. Tema 5. 15

OpenMP : descripción (II) • No es un nuevo lenguaje, sino API con: – directivas para el compilador • facilita la portabilidad y • la “paralelización incremental”.

– unas pocas funciones de biblioteca – algunas variables de entorno • Un programa puede ser compilado por compiladores que no soportan OpenMP – Las directivas son tratadas como comentarios e ignoradas. – ATENCIÓN: No olvidar “Compatibilidad OpenMP” en el compilador SPD. Tema 5. 16

Sintaxis de OpenMP • Pragma en C y C++: #pragma omp construct [clause [clause]…]

• En Fortran, directivas : C$OMP construct [clause [clause]…] !$OMP construct [clause [clause]…] *$OMP construct [clause [clause]…]

SPD. Tema 5. 17

Claves del diseño de una aplicación (I) 1. directivas que especifican una región paralela (código replicado) 2. reparto de tareas (específicas para cada thread) 3. sincronización entre threads • Fácil para bucles (paralelizables directa o indirectamente) – Sólo paso 1 (2 y 3 los introduce el compilador) SPD. Tema 5. 18

Claves del diseño de una aplicación (II) 1. Partiendo de un programa serie, buscar partes del código paralelizables: – estructuras de control paralelo (bucles for) – reparto de tareas

2. Incluir la comunicación entre hilos – a través de variables compartidas (Cuidado con ámbito de las variables)

3. Sincronizar – exclusión mutua – barreras SPD. Tema 5. 19

Programa sencillo Programa Secuencial void main() { double a[1000],b[1000],c[1000]; for (int i = 0; i< 1000; i++){ a[i] = b[i] + c[i]; } }

Programa Paralelo void main() { double a[1000],b[1000],c[1000]; #pragma omp parallel for for (int i = 0; i< 1000; i++){ a[i] = b[i] + c[i]; } } SPD. Tema 5. 20

Programa sencillo: explicación (I) void main() { double a[1000],b[1000],c[1000]; /*Un único pragma, pero el compilador debe previamente crear tantos hilos P como permita en paralelo el procesador */ /* debe decidir que hacer con las variables a[],b[],c[],i: ¿crea copias y las replica?¿no crea copias:son compartidas?*/ #pragma omp parallel for /*aquí debe trocear en bucle en P hilos */ for (int i = 0; i< 1000; i++){ a[i] = b[i] + c[i]; } } 0 250 500 750 1000 SPD. Tema 5. 21

Programa sencillo: explicación (II) #pragma omp parallel for /*Troceado por defecto (existen otros)*/ //Supongamos P=4 //Hilo 0 for (int i = 0; i< 250; i++){ a[i] = b[i] + c[i]; } //Hilo 1 for (int i = 250; i< 500; i++){ a[i] = b[i] + c[i]; } //Hilo 2 for (int i = 500; i< 750; i++){ a[i] = b[i] + c[i]; } //Hilo 3 for (int i = 750; i< 1000; i++){ a[i] = b[i] + c[i]; } SPD. Tema 5. 22

Regiones paralelas y críticas • El modelo de programación paralela es Fork - Join. – El master thread genera P threads que se ejecutan en paralelo. Critical regions

SPD. Tema 5. 23

OpenMP runtime library omp_get_num_threads() • devuelve el número actual de threads omp_get_thread_num() • devuelve el identificador de ese thread omp_set_num_threads(n) • activa el número de threads ¿Qué parte le corresponde al hilo 0 de este bucle (usar estas func.)? ¿Y al hilo k ? for (int i = 0; i< n; i++){…} SPD. Tema 5. 24

Declarando Ámbito de datos (I) • shared: variable es compartida por todos los procesos. Ej: vectores del proceso. • private: Cada proceso tiene una copia #pragma omp parallel for shared(a,b,c,n) private(i, temp) for (i = 0; i < n; i++) { temp = a[i]/b[i]; a[i] = b[i] + temp * c[i]; } • Hay reglas para decidir por defecto el ámbito, pero mejor no arriesgarse ¿Qué pasa si n=2; • Lo peligroso son las escrituras float a[2], b[2], c[2];? • CUIDADO: false sharing SPD. Tema 5. 25

Declarando Ámbito de datos (II) • Variables REDUCTION: operaciones colectivas sobre elementos de un array • Operadores: + * - & | ^ && || asum = 0.0; aprod = 1.0; #pragma omp parallel for reduction(+:asum) reduction(*:aprod) for (i = 0; i < n; i++) { asum = asum + a[i]; aprod = aprod * a[i]; } SPD. Tema 5. 26

Planificación de Tareas: SCHEDULE (I) Diferentes formas de asignar iteraciones a threads • schedule(static [,chunk]) – “chunk” iteraciones se asignan de manera estática a los threads en round-robin

• schedule (dynamic [,chunk]) – Cada thread toma “chunk” iteraciones cada vez que está sin trabajo

• schedule (guided [,chunk]) – Cada thread toma progresivamente menos iteraciones (dinámicamente) SPD. Tema 5. 27

Planificación de Tareas: SCHEDULE (II) • igual num iteraciones para static, dynamic. • exponencialm. decreciente para guided

• Hilo 0 1 2 a

b

c

0 1 2 a

e d

h

b

0 1 2

c a

d

b

c

e

f

h g

g

d

f e

g

f

i

i

Static

Dynamic

Guided SPD. Tema 5. 28

Planificación de Tareas: SCHEDULE (III) RECUERDA: • Static : menos coste / mejor localidad datos • Dynamic: más coste / carga más equilibrada

Static: bucles simples Dynamic: si carga varía según la iteración SPD. Tema 5. 29

Regiones Paralelas #pragma omp parallel { /* Bloque básico replicado (ejecutado) por cada thread */

}

Reparto de tareas en f(tid). Pag 15 Pero “carrera” entre todos ¿Qué se imprime? SPD. Tema 5. 30

Work Sharing (reparto de tareas) 1. Directiva for, –

–

para repartir la ejecución de las iteraciones de un bucle entre todos los threads (bloques básicos y número de iteraciones conocido). Se suele usar junto a omp parallel for

2. Directiva sections, –

para definir “manualmente” trozos o secciones de una región paralela a repartir entre los threads en función del tid.

3. Directiva single, –

para definir un trozo de código que sólo debe ejecutar un thread. SPD. Tema 5. 31

Secciones (una por hilo) #pragma omp parallel sections { #pragma omp section { printf ("id s1=%d,\n“,omp_get_thread_num()); for (i=0; i