![Page 1: Arquitecturas Paralelas MIMD - electro.fisica.unlp.edu.arelectro.fisica.unlp.edu.ar/arq/transparencias/ARQII_08-MIMD_old.pdf · sola copia del sistema operativo (con planificador](https://reader031.vdocumento.com/reader031/viewer/2022022621/5bb072fc09d3f2a8728de047/html5/thumbnails/1.jpg)
Arquitecturas ParalelasMIMD
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.
![Page 2: Arquitecturas Paralelas MIMD - electro.fisica.unlp.edu.arelectro.fisica.unlp.edu.ar/arq/transparencias/ARQII_08-MIMD_old.pdf · sola copia del sistema operativo (con planificador](https://reader031.vdocumento.com/reader031/viewer/2022022621/5bb072fc09d3f2a8728de047/html5/thumbnails/2.jpg)
Taxonomía de Flynn
MPP
![Page 3: Arquitecturas Paralelas MIMD - electro.fisica.unlp.edu.arelectro.fisica.unlp.edu.ar/arq/transparencias/ARQII_08-MIMD_old.pdf · sola copia del sistema operativo (con planificador](https://reader031.vdocumento.com/reader031/viewer/2022022621/5bb072fc09d3f2a8728de047/html5/thumbnails/3.jpg)
Taxonomía de Flynn-Johnson
![Page 4: Arquitecturas Paralelas MIMD - electro.fisica.unlp.edu.arelectro.fisica.unlp.edu.ar/arq/transparencias/ARQII_08-MIMD_old.pdf · sola copia del sistema operativo (con planificador](https://reader031.vdocumento.com/reader031/viewer/2022022621/5bb072fc09d3f2a8728de047/html5/thumbnails/4.jpg)
Clasificación MIMD Tanenbaum
![Page 5: Arquitecturas Paralelas MIMD - electro.fisica.unlp.edu.arelectro.fisica.unlp.edu.ar/arq/transparencias/ARQII_08-MIMD_old.pdf · sola copia del sistema operativo (con planificador](https://reader031.vdocumento.com/reader031/viewer/2022022621/5bb072fc09d3f2a8728de047/html5/thumbnails/5.jpg)
Arquitecturas MIMD
Multiprocesadores Multicomputadoras
![Page 6: Arquitecturas Paralelas MIMD - electro.fisica.unlp.edu.arelectro.fisica.unlp.edu.ar/arq/transparencias/ARQII_08-MIMD_old.pdf · sola copia del sistema operativo (con planificador](https://reader031.vdocumento.com/reader031/viewer/2022022621/5bb072fc09d3f2a8728de047/html5/thumbnails/6.jpg)
MultiprocesadoresIntroducción
VENTAJASDatos, 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.
DESVENTAJASPerformance 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 (16-64). Poco escalables.
![Page 7: Arquitecturas Paralelas MIMD - electro.fisica.unlp.edu.arelectro.fisica.unlp.edu.ar/arq/transparencias/ARQII_08-MIMD_old.pdf · sola copia del sistema operativo (con planificador](https://reader031.vdocumento.com/reader031/viewer/2022022621/5bb072fc09d3f2a8728de047/html5/thumbnails/7.jpg)
MultiprocesadoresClasificació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
![Page 8: Arquitecturas Paralelas MIMD - electro.fisica.unlp.edu.arelectro.fisica.unlp.edu.ar/arq/transparencias/ARQII_08-MIMD_old.pdf · sola copia del sistema operativo (con planificador](https://reader031.vdocumento.com/reader031/viewer/2022022621/5bb072fc09d3f2a8728de047/html5/thumbnails/8.jpg)
MultiprocesadoresUMA (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.
![Page 9: Arquitecturas Paralelas MIMD - electro.fisica.unlp.edu.arelectro.fisica.unlp.edu.ar/arq/transparencias/ARQII_08-MIMD_old.pdf · sola copia del sistema operativo (con planificador](https://reader031.vdocumento.com/reader031/viewer/2022022621/5bb072fc09d3f2a8728de047/html5/thumbnails/9.jpg)
MultiprocesadoresNUMA
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.
![Page 10: Arquitecturas Paralelas MIMD - electro.fisica.unlp.edu.arelectro.fisica.unlp.edu.ar/arq/transparencias/ARQII_08-MIMD_old.pdf · sola copia del sistema operativo (con planificador](https://reader031.vdocumento.com/reader031/viewer/2022022621/5bb072fc09d3f2a8728de047/html5/thumbnails/10.jpg)
MultiprocesadoresCOMA
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.
![Page 11: Arquitecturas Paralelas MIMD - electro.fisica.unlp.edu.arelectro.fisica.unlp.edu.ar/arq/transparencias/ARQII_08-MIMD_old.pdf · sola copia del sistema operativo (con planificador](https://reader031.vdocumento.com/reader031/viewer/2022022621/5bb072fc09d3f2a8728de047/html5/thumbnails/11.jpg)
MultiprocesadoresSMP vs. NUMA
.
![Page 12: Arquitecturas Paralelas MIMD - electro.fisica.unlp.edu.arelectro.fisica.unlp.edu.ar/arq/transparencias/ARQII_08-MIMD_old.pdf · sola copia del sistema operativo (con planificador](https://reader031.vdocumento.com/reader031/viewer/2022022621/5bb072fc09d3f2a8728de047/html5/thumbnails/12.jpg)
MultiprocesadoresINTEL Pentium III
.
![Page 13: Arquitecturas Paralelas MIMD - electro.fisica.unlp.edu.arelectro.fisica.unlp.edu.ar/arq/transparencias/ARQII_08-MIMD_old.pdf · sola copia del sistema operativo (con planificador](https://reader031.vdocumento.com/reader031/viewer/2022022621/5bb072fc09d3f2a8728de047/html5/thumbnails/13.jpg)
MultiprocesadoresAMD Opteron (Hypertransport)
.
Hypertransport Consortium: ADM, IBM, Alliance, Apple, Cisco, Sun, Transmeta.NO INTEL! Sigue con bus.
![Page 14: Arquitecturas Paralelas MIMD - electro.fisica.unlp.edu.arelectro.fisica.unlp.edu.ar/arq/transparencias/ARQII_08-MIMD_old.pdf · sola copia del sistema operativo (con planificador](https://reader031.vdocumento.com/reader031/viewer/2022022621/5bb072fc09d3f2a8728de047/html5/thumbnails/14.jpg)
MultiprocesadoresIBM POWER5 (Fabric Switch)
.
![Page 15: Arquitecturas Paralelas MIMD - electro.fisica.unlp.edu.arelectro.fisica.unlp.edu.ar/arq/transparencias/ARQII_08-MIMD_old.pdf · sola copia del sistema operativo (con planificador](https://reader031.vdocumento.com/reader031/viewer/2022022621/5bb072fc09d3f2a8728de047/html5/thumbnails/15.jpg)
MultiprocesadoresIntel (Multicore - Bus)
.
![Page 16: Arquitecturas Paralelas MIMD - electro.fisica.unlp.edu.arelectro.fisica.unlp.edu.ar/arq/transparencias/ARQII_08-MIMD_old.pdf · sola copia del sistema operativo (con planificador](https://reader031.vdocumento.com/reader031/viewer/2022022621/5bb072fc09d3f2a8728de047/html5/thumbnails/16.jpg)
MultiprocesadoresAná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 la eficiencia del hardware de cache (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.
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%.
( )hVBIN−
≤1
N: número de procesadoresh: hit rate del cache (1-h): miss rateB: ancho de banda del bus [c/s]I: duty cycle del procesador [fetch/c] uperesc>1V: velocidad pico del procesador [fetch/s] B.I: ancho de banda efectivo [fetch/s]
N procesadores a velocidad V producen N(1-h)V fallos, entonces N(1-h)V<B.I
![Page 17: Arquitecturas Paralelas MIMD - electro.fisica.unlp.edu.arelectro.fisica.unlp.edu.ar/arq/transparencias/ARQII_08-MIMD_old.pdf · sola copia del sistema operativo (con planificador](https://reader031.vdocumento.com/reader031/viewer/2022022621/5bb072fc09d3f2a8728de047/html5/thumbnails/17.jpg)
MultiprocesadoresCoherencia 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. 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, protocolo MESI)
Existen cuatro combinaciones. La combinación a-a satura rápidamente.
![Page 18: Arquitecturas Paralelas MIMD - electro.fisica.unlp.edu.arelectro.fisica.unlp.edu.ar/arq/transparencias/ARQII_08-MIMD_old.pdf · sola copia del sistema operativo (con planificador](https://reader031.vdocumento.com/reader031/viewer/2022022621/5bb072fc09d3f2a8728de047/html5/thumbnails/18.jpg)
MultiprocesadoresProtocolos 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. 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 las copias de 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).
![Page 19: Arquitecturas Paralelas MIMD - electro.fisica.unlp.edu.arelectro.fisica.unlp.edu.ar/arq/transparencias/ARQII_08-MIMD_old.pdf · sola copia del sistema operativo (con planificador](https://reader031.vdocumento.com/reader031/viewer/2022022621/5bb072fc09d3f2a8728de047/html5/thumbnails/19.jpg)
MultiprocesadoresEl 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.
![Page 20: Arquitecturas Paralelas MIMD - electro.fisica.unlp.edu.arelectro.fisica.unlp.edu.ar/arq/transparencias/ARQII_08-MIMD_old.pdf · sola copia del sistema operativo (con planificador](https://reader031.vdocumento.com/reader031/viewer/2022022621/5bb072fc09d3f2a8728de047/html5/thumbnails/20.jpg)
MultiprocesadoresEl modelo de programación
i) Creación de tareasii) Comunicación: shared data
iii) Coordinación: a) locks (exlusión mutua) Sincronización: b) barriers
![Page 21: Arquitecturas Paralelas MIMD - electro.fisica.unlp.edu.arelectro.fisica.unlp.edu.ar/arq/transparencias/ARQII_08-MIMD_old.pdf · sola copia del sistema operativo (con planificador](https://reader031.vdocumento.com/reader031/viewer/2022022621/5bb072fc09d3f2a8728de047/html5/thumbnails/21.jpg)
MultiprocesadorespThreads - Ejemplo
/************************************************************************"hello world" Pthreads. Compilar con: gcc -lpthread -o hello hello.c*************************************************************************/#include <pthread.h>#include <stdio.h>#define NUM_THREADS 5
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);}
![Page 22: Arquitecturas Paralelas MIMD - electro.fisica.unlp.edu.arelectro.fisica.unlp.edu.ar/arq/transparencias/ARQII_08-MIMD_old.pdf · sola copia del sistema operativo (con planificador](https://reader031.vdocumento.com/reader031/viewer/2022022621/5bb072fc09d3f2a8728de047/html5/thumbnails/22.jpg)
Muticomputadoras
Diferencia entre MPP (loosely coupled) y Clusters (very-loosely coupled). Al no existir recursos compartidos, la comunicación se realiza a través de mensajes enviados por la red. El mensaje es una unidad lógica que puede transportar datos, instrucciones, sincronización o interrupciones.
![Page 23: Arquitecturas Paralelas MIMD - electro.fisica.unlp.edu.arelectro.fisica.unlp.edu.ar/arq/transparencias/ARQII_08-MIMD_old.pdf · sola copia del sistema operativo (con planificador](https://reader031.vdocumento.com/reader031/viewer/2022022621/5bb072fc09d3f2a8728de047/html5/thumbnails/23.jpg)
MuticomputadorasIntroducción
VENTAJASEscala mejor y soporta más nodos. Se eliminan las construcciones de sincronización. No está limitado por el ancho de banda de la memoria (si por el de la red). Puede utilizar redes estáticas no completamente conectadas (routing, bw, latencia). Sincronización y comunicación son lo mismo.
DESVENTAJASProgramación con mensajes explícitos (send/receive en lugar de load/store); los programas son diferentes. Tiempo de transmisión del mensaje. Una copia del SO en cada computadora. Difícil mover procesos entre computadoras.
![Page 24: Arquitecturas Paralelas MIMD - electro.fisica.unlp.edu.arelectro.fisica.unlp.edu.ar/arq/transparencias/ARQII_08-MIMD_old.pdf · sola copia del sistema operativo (con planificador](https://reader031.vdocumento.com/reader031/viewer/2022022621/5bb072fc09d3f2a8728de047/html5/thumbnails/24.jpg)
MuticomputadorasGranularidad
El programa se divide en N procesos concurrentes que se ejecutan en n computadoras. Si n<N existirán varios procesos (time-sharing) en cada computadora (canales externos vs. canales internos, no se puede compartir). Definimos, para un proceso:
Granularidad gruesa: cada proceso tiene muchas instruccionesGranularidad fina: pocas (incluso 1)
Los multiprocesadores funcionan mal en aplicaciones de granularidad fina debido el alto costo de las comunicaciones.
óncomunicacidetiempocómputodetiempoadGranularid =
![Page 25: Arquitecturas Paralelas MIMD - electro.fisica.unlp.edu.arelectro.fisica.unlp.edu.ar/arq/transparencias/ARQII_08-MIMD_old.pdf · sola copia del sistema operativo (con planificador](https://reader031.vdocumento.com/reader031/viewer/2022022621/5bb072fc09d3f2a8728de047/html5/thumbnails/25.jpg)
MuticomputadorasRuteo (routing)
A menos que se disponga de una red completamente conectada, esta problemática estará presente. Se define como el conjunto de técnicas utilizadas para:
a) Identificación de todos los caminos posibles.b) Selección del mejor a través de una función.
Las técnicas pueden clasificarse según su dinámica: Adaptivas (dependen del estado de la red) o Determinísticas (oblivious).O según su organización: Centralizadas (conozco la ruta al conocer la fuente y el destino) o Distribuídas (solo conozco el próximo salto)
Ejemplo: XOR en Hipercubo
![Page 26: Arquitecturas Paralelas MIMD - electro.fisica.unlp.edu.arelectro.fisica.unlp.edu.ar/arq/transparencias/ARQII_08-MIMD_old.pdf · sola copia del sistema operativo (con planificador](https://reader031.vdocumento.com/reader031/viewer/2022022621/5bb072fc09d3f2a8728de047/html5/thumbnails/26.jpg)
MuticomputadorasRouting (cont)
Tipos de operaciones:a) Unicastb) Multicastc) Broadcast
Problemas:a) Deadlock (solución monotónica) Ej: regla y lápizb) Livelock (solo en adaptivas) Ej: pasilloc) Starvation
![Page 27: Arquitecturas Paralelas MIMD - electro.fisica.unlp.edu.arelectro.fisica.unlp.edu.ar/arq/transparencias/ARQII_08-MIMD_old.pdf · sola copia del sistema operativo (con planificador](https://reader031.vdocumento.com/reader031/viewer/2022022621/5bb072fc09d3f2a8728de047/html5/thumbnails/27.jpg)
MuticomputadorasConmutación (switching)
Técnica utilizada para pasar un mensaje de la entrada a la salida.a) Circuit-switching: reserva el camino. Ej: telefonía.b) Store-and-forward:
i) Packet-switching: El mensaje es dividido en paquetes que pueden viajar por diferentes caminos. Cada paquete lleva información de routing. Overhead. Pueden llegar desordenados. Ej: TCP.ii) Message-switching: el mensaje viaja entero.
c) Cut-Through-switching (wormhole routing): Todos los paquetes (flits – flow control bits – 32 bits low latency) se mueven tipo pipeline, siguiendo la misma ruta. El primero la fija. Cada nodo debe llevar la cuenta de los mensajes que está transmitiendo. Util en direcciones cortas. Ejemplo: hipercubo.
![Page 28: Arquitecturas Paralelas MIMD - electro.fisica.unlp.edu.arelectro.fisica.unlp.edu.ar/arq/transparencias/ARQII_08-MIMD_old.pdf · sola copia del sistema operativo (con planificador](https://reader031.vdocumento.com/reader031/viewer/2022022621/5bb072fc09d3f2a8728de047/html5/thumbnails/28.jpg)
MuticomputadorasEl modelo de programación
Primitivas de comunicación: send, receive, broadcast, barrier.Mensajes bloqueantes (3 way) y no bloqueantes.PVM y MPI: bibliotecas de comunicaciones para C. Open Source: LAM-MPI y MPICH
#include <stdio.h>#include <mpi.h>
int main(){int rank, size;MPI_Init( &argc, &argv );MPI_Comm_size( MPI_COMM_WORLD, &size );MPI_Comm_rank( MPI_COMM_WORLD, &rank );printf( "Hello world from process %d of %d\n", rank, size );MPI_Finalize();return 0;
}
![Page 29: Arquitecturas Paralelas MIMD - electro.fisica.unlp.edu.arelectro.fisica.unlp.edu.ar/arq/transparencias/ARQII_08-MIMD_old.pdf · sola copia del sistema operativo (con planificador](https://reader031.vdocumento.com/reader031/viewer/2022022621/5bb072fc09d3f2a8728de047/html5/thumbnails/29.jpg)
SMP vs MPP
En el medio NUMA (enmascara mensajes de HW por medio de SW).
![Page 30: Arquitecturas Paralelas MIMD - electro.fisica.unlp.edu.arelectro.fisica.unlp.edu.ar/arq/transparencias/ARQII_08-MIMD_old.pdf · sola copia del sistema operativo (con planificador](https://reader031.vdocumento.com/reader031/viewer/2022022621/5bb072fc09d3f2a8728de047/html5/thumbnails/30.jpg)
MuticomputadorasEjemplos MPP
Blue GeneIBM #1 Nov2006360 TeraFLOPS (teorico)280 TeraFLOPS (real)Toriode 3d 32x32x6465536 procesadores dual core
![Page 31: Arquitecturas Paralelas MIMD - electro.fisica.unlp.edu.arelectro.fisica.unlp.edu.ar/arq/transparencias/ARQII_08-MIMD_old.pdf · sola copia del sistema operativo (con planificador](https://reader031.vdocumento.com/reader031/viewer/2022022621/5bb072fc09d3f2a8728de047/html5/thumbnails/31.jpg)
MuticomputadorasEjemplos MPP
Red StormCray #2 Nov2006Nodos: AMD Opteron dual coreRed: Cray SeaStar2 chipHypertransport 6 canales 6.4GB/sToriode 3d
![Page 32: Arquitecturas Paralelas MIMD - electro.fisica.unlp.edu.arelectro.fisica.unlp.edu.ar/arq/transparencias/ARQII_08-MIMD_old.pdf · sola copia del sistema operativo (con planificador](https://reader031.vdocumento.com/reader031/viewer/2022022621/5bb072fc09d3f2a8728de047/html5/thumbnails/32.jpg)
Casos de estudio
IBM System p5. Cluster 1600 con nodos 595.
Cray XT4.
Consolas de juegos de séptima generación (Xbox 360 de Microsoft, Playstation 3 de Sony y Wii de Nintendo).
Deep Blue vs. Kasparov (1997).