PDF de programación - Arquitecturas Paralelas Multiprocesadores

Arquitecturas Paralelas

Multiprocesadores

William Stallings, Organización y Arquitectura de

Computadores, 5ta. ed., Capítulo 16: Procesamiento Paralelo.

Andrew S. Tanenbaum, Organización de Computadoras 4ta.

ed., Capítulo 8: Arquitecturas de computadoras paralelas.

Hesham El-Rewini & Mostafa Abd-El-Barr, Advanced
Computer Architecture and Parallel Processing. Willey.



Arquitecturas Paralelas
Taxonomía de Flynn



Massively Parallel

Processor

(MPP)

Arquitecturas Paralelas
Taxonomía de Flynn-Johnson



Arquitecturas Paralelas
Clasificación MIMD Tanenbaum



Arquitecturas Paralelas
Arquitecturas MIMD

MULTICOMPUTADORAS

Procesadores débilmente acoplados

Arquitectura de memoria distribuida (mensajes)

MULTIPROCESADORES

Procesadores fuertemente acoplados

Arquitectura de memoria compartida (globales)



Multiprocesadores
Introducción

VENTAJAS
Datos, sincronización y coordinación usando variables globales.
Modelo simple de programación. Espacio único de memoria. Una sola
copia del sistema operativo (con planificador adecuado). Threads. Los
sistemas operativos modernos coordinan la distribución de los
recursos. Es fácil mover procesos entre procesadores. Menos espacio.
Menos potencia. Más estable.

DESVENTAJAS
Performance de la memoria. Se soluciona con caches, pero aparece el
problema de la coherencia de caches. La red de interconexión es
complicada (acceso a memoria). Dinámica: bus, crossbar o
multistage. Se satura rápidamente. Soporta pocos procesadores (2-
16). Poco escalables.



Multiprocesadores
Clasificación

Lar arquitecturas multiprocesador pueden clasificarse según la
estrategia de distribución de la memoria compartida, siempre con un
único mapa de memoria:

UMA (o SMP): Uniform Memory Access (o
Symetric MultiProcessor)

NUMA: Non Uniform Memory Access

COMA: Cache Only Memory Architecture



Multiprocesadores
UMA (SMP)
La organización con bus es la más utilizada en multiprocesadores
multiple core. En esta categoría entran también las organizaciones
con memoria multipuerto (no escalable). La memoria compartida es
accedida por todos los procesadores de la misma forma en que un
monoprocesador accede a su memoria. Todos los procesadores son
similares y tienen capacidades equivalentes. Todos los procesadores
tienen el mismo tiempo de acceso a cualquier posición de memoria.
Comparten I/O.

Redes: multipuerto, bus o crossbar. Ej: Sun Starfire, Intel Xeon/Pentium/Core2.



Multiprocesadores
NUMA
Utiliza (como SMP) un único espacio de direcciones, pero en este caso
cada procesador es dueño de una parte de la memoria, a la cual
puede acceder más rápido. Utiliza pasaje de mensajes escondido. El
problema de coherencia es más complicado. El sistema operativo
(más sofisticado) puede ayudar mediante migración de páginas. Sin
coherencia de cache, multicomputador.

Redes de interconexión: tree, bus jerárquico.
Ejemplos: SGI Origin 3000, Cray T3E, AMD Opteron.



Multiprocesadores
COMA
Como en NUMA, cada procesador tiene una parte de la memoria, pero
es sólo cache. El espacio de memoria completo es la suma de los
caches. Utilizan un mecanismo de directorio distribuído.

Ejemplo: KSR-1.



Multiprocesadores
SMP vs. NUMA

Dependencia con la naturaleza de la aplicación.

Cada instancia del programa dispone de sus

IMPORTANTE

propios datos?



Multicore SMP, c/core superescalar SMT

Multiprocesadores
INTEL Pentium III
.



Multiprocesadores
AMD Opteron (Hypertransport)

Hypertransport Consortium:
ADM, IBM, Alliance, Apple, Cisco, Sun, Transmeta.
NO INTEL! Sigue con bus.



Multiprocesadores
IBM POWER5 (Fabric Switch)

MCM: multi chip module

1 Mother: 4 MCMs x 4 Power5 x 2 cores x
2 SMT = 64 threads simultáneas
+ NIC -> cluster con pasaje de mensajes



Motherboard

Multiprocesadores
Intel (Multicore - Bus)



Multiprocesadores
Análisis de SMP basado en bus
El bus es la red más simple para memoria compartida. Es un medio
compartido, con arbitraje y capacidad de direccionamiento. La
arquitectura bus/cache elimina
la necesidad de memorias
multipuerto. El principal problema es la saturación del bus. Depende
fuertemente de
(debe
minimizarse el número de veces que el procesador necesita acceder
al bus). Depende también de las características del programa de
aplicación.

la eficiencia del hardware de cache

N ≤

BI

V (1−h)

N: número de procesadores
h: hit rate del cache (1-h): miss rate
B: ancho de banda del bus [c/s]
I: duty cycle del procesador [fetch/c]
uperesc>1
V: velocidad pico del procesador [fetch/s]
B.I: ancho de banda efectivo [fetch/s]

Ejemplo.
I=1, B=100MHz, V=300MIPS, h=90%. Resulta N<3,3.
¿Cuánto debe valer h para soportar 32 procesadores? Resulta
h>99%. Qué tamaño debe tener la memoria caché?!?!



HINT: N procesadores a velocidad V producen
N(1-h)V fallos, entonces N(1-h)V<B.I

Multiprocesadores
Coherencia de cache
Existen múltiples copias de los datos en diferentes caches. Si un
procesador modifica su copia y los demás caches no se actualizan se
producirán errores en el resultado final. Solo es un problema si hay
escrituras. Se utilizan distintos algoritmos para mantener la
coherencia.

REM Coherencia cache-memoria:
a) write-through: la memoria se actualiza inmediatamente.
b) write-back: se actualiza cuando se reemplaza el bloque.

Coherencia cache-cache:
a) write-update: actualización inmediata.
b) write-invalidate: al modificar setea el dirty-bit y se queda con la
única copia válida. Los demás deben esperar la actualización.
(PowerPC y PII, ver protocolo MESI)

Existen cuatro combinaciones. La a-a satura rápidamente.



Multiprocesadores
Protocolos de coherencia de cache

a) Protocolos de sondeo (snooping protocols): observan la
actividad del bus y ejecutan, mediante broadcasts, los pasos
necesarios para mantener la coherencia. Costoso en terminos de bw,
sobre todo en redes multistage. Quien escribe avisa con un broadcast
(a todos). Todos los procesadores sondean el bus para detectar
modificaciones que le incumban.

b) Protocolos de directorio (directory based protocols): Los
comandos de actualización se envían sólo a los caches afectados por
una actualización. Almacena información en un directorio acerca de
dónde se encuentran
los bloques. Cuando un
procesador quiere escribir una posición, debe solicitar autorización al
controlador, quien luego invalida las demás copias. El directorio
puede estar centralizado (cuello de botella) o distribuído (cada cache
sabe lo que tiene).

las copias de



Multiprocesadores
El protocolo MESI

Es un protocolo tipo write-invalidate, implementado por Intel en la
linea Pentium y por IBM en la Power. Utiliza dos bits por linea de
cache para indicar el estado de la misma: Modified, Exclusive, Shared,
Invalid. Stallings 16.3.



Ver (Wikipedia)

MSI
MOSI
MOESI

Multiprocesadores
El modelo de programación

Los lenguajes de programación evolucionaron para incluir al menos tres constructores:
i) Creación de tareas: grano grueso (fork/exec) o fino (lightweight)
ii) Comunicación: segmento shared data, además de text, data y stack.

iii) Coordinación (a) locks o exlusión mutua, y sincronización (b) barriers

Diferencia con mensajes
(sincronizan naturalmente)



Multiprocesadores
pThreads – Hello world

IEEE POSIX 1003.1c standard

(1995)

5

/************************************************************************
"hello world" Pthreads. Compilar con: gcc -lpthread -o hello hello.c
*************************************************************************/
#include <pthread.h>
#include <stdio.h>
#define NUM_THREADS
void *PrintHello(void *threadid){
printf("\n%d: Hello World!\n", threadid);
pthread_exit(NULL);
}
int main(){
pthread_t threads[NUM_THREADS];
int rc, t;
for(t=0;t<NUM_THREADS;t++){
printf("Creating thread %d\n", t);
rc = pthread_create(&threads[t], NULL, PrintHello, (void *)t);
if (rc){
printf("ERROR; return code from pthread_create() is %d\n", rc);
exit(-1);
}
}
pthread_exit(NULL);
}



Multiprocesadores
OpenMP – Hello world

/**********************************************************************
OpenMP hello world. Compilar con gcc -fopenmp -o hello_omp hello_omp.c
***********************************************************************/
#include <omp.h>
#include <stdio.h>
int main (int argc, char *argv[]) {

int id, nthreads;
#pragma omp parallel private(id) {

id = omp_get_thread_num();
printf("Hello World from thread %d\n", id);
#pragma omp barrier
if ( id == 0 ) {

nthreads = omp_get_num_threads();
printf("There are %d threads\n",nthreads);

}

}
return 0;

}

Open specificatios for Multi Processing: API definida por un grupo de
frabricantes de HW y SW (ANSI en el futuro?). Modelo portable (C, C++,
Fortran, Unix, WinXP) y escalable para desarrolladores de aplicaciones
paralelas en sistemas multi-theaded de memoria compartida.



Multiprocesadores
OpenMP – π

/**********************************************************************
Calculo de pi por montecarlo con OpenMP
***********************************************************************/
#include <omp.h>
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#define N 20
int main (int argc, char *argv[]) {

int i, j=0, n=10000000;
double x, y, d;
omp_set_num_threads(N);
# pragma omp parallel for private(i,x,y,d) reduction(+:j)

for(i=0;i<n;i++){

x=(double)rand()/RAND_MAX;
y=(double)rand()/RAND_MAX;
d=sqrt(x*x+y*y);
if(d<=1.0) j++;

}

printf("PI = %f\n", 4.0*j/n);
return 0;

}



Arquitecturas Paralelas

Multicomputadoras

William Stallings, Organización y Arquitectura de

Computadores, 5ta. ed., Capítulo 16: Procesamiento Paralelo.

Andrew S. Tanenbaum, Organización de Computadoras 4ta.

ed., Capítulo 8: Arqu