PDF de programación - Sistemas Multiprocesadores

Sistemas Multiprocesadores
Introducción

1.
2. Clasificación de los multiprocesadores
3. Redes básicas de interconexión
4. Clusters
5.

Programación y aplicaciones

Sistemas

Multiprocesadores

Arquitectura y Tecnología de Computadores

Universidad de Sevilla

Prof. Saturnino Vicente Díaz

1

1. Introducción

• Niveles de paralelismo
•
Introducción a los sistemas multiprocesadores
• Argumentos a favor de los multiprocesadores
• Argumentos en contra de los multiprocesadores
•

Investigación actual

HLL

S.O.

ISA

Compilador/

librerías

Introducción

Si existe DLP

Paralelizador/
reescritura

Vectorizador

Niveles de paralelismo

TLP

(Multiprocesadores)

DLP extraído
(SIMD / PV)

DLP extraído

(Núcleos

Multimedia)

Desenrollado

ILP

(VLIW /
Superesc)

Encadenamiento

Paralelismo
a nivel de bits

Implemen-

tación

Lógica
Digital

Electrónica

Fig. 1.1

2

Introducción

• Sistemas multiprocesadores

– En los sistemas actuales la CPU

• es un todo monolítico
• está separada de la memoria principal y de la E/S
• Alcanza grandes velocidades

– Vamos a romper con esta concepción para diseñar los

multiprocesadores

Reduce el
nº de mensajes

APROVECHAR
UniProc. barato
altas prestaciones

ESCRIBIR
Código
Paralelo

DISEÑAR

Comunicación

eficiente

Cuidado con
el progreso de
las apli. reales

Sistemas

Multiprocesadores

Introducción
t

=

t

uni
ejec
,
N

– Idealmente, , lo cual es imposible

ejec

,

mult

• La red de interconexión juega un papel importante

– Comunicación entre procesadores
– Comunicación entre procesadores y memoria

• La memoria está separada de los procesadores, pero no
totalmente ⇒ Cada procesador tiene su caché local. La
forma de organizar la jerarquía de memoria es vital

– Lo que vamos a construir se parece a:

Fig. 1.2

Fig. 1.4

Fig. 1.3

3

Introducción

Introducción

• Argumentos a favor de los Multiprocesadores
rendimiento de

– En 15 ó 20 años, el

los
Uniprocesadores llegará a su fin, debido a dos razones:
• Incrementar el rendimiento conectando uniprocesadores

en paralelo

– Menos costoso que diseñar un nuevo procesador
– Más flexible para todo tipo de soft que un nuevo diseño

• El ritmo de innovación en la endoarquitectura es difícil

de mantener indefinidamente

– Actualmente el incremento en transistores es superior al

de rendimiento (nºtran x 4 ; rend. x 3 cada 3 años)

– Algunos estudios indican el inicio de la saturación en

prestaciones de los uniprocesadores

Prestaciones
Uniprocesador

Coste de
saturación

1990’s

1980´s (VLSI)

1970´s (Circuitos integrados)

1960´s (Transistores discretos)

Coste

Fig. 1.5

– Parece que los MPr’s son la única forma de aumentar

considerablemente el rendimiento a un precio razonable

• Argumentos en contra de los Multiprocesadores
– Cada 2 ó 3 años, alguien anuncia el fin de los UniPr
• A los 2 ó 3 años se disparan las prestaciones por una
nueva idea arquitectónica. Esto es debido a que hay
mucho mercado ⇒ mucha inversión ⇒ mucho avance

– Segmentación
– Vectorización
– Superescalaridad
– HyperThreading, etc.

– Lentitud en las comunicaciones

• Latencia a memoria local es del orden de pocos ns
• En MPr, si un Pr necesita un dato remoto ⇒alta latencia,

del orden de microsegundos (Ejemplo)

– Limitación del paralelismo de las aplicaciones

• La ley de Amdahl nos indica el efecto del paralelismo de

las aplicaciones en la aceleración
ejec
,

ejec

=

t

t

– Intuitivamente
– Sin embargo, la mejora solo afecta al porcentaje de

mult

uni

N

,

código que se pueda paralelizar

» Dado un código normal, un compilador intenta
paralelizar el código, y lo consigue en la mitad del
programa
A

→

=

=

=

2

1

2
N

N
+

1

1
)
F

+

(
1

−

F
N

1
2

+

1
*2

N

» Suponer que queremos conseguir una aceleración de
80, con 100 procesadores ¿Qué fracción del
programa debe ser paralela?

75,99≈F

4

Introducción

•

Investigación actual
– Software más adaptado a la computación paralela

• Nuevos algoritmos

– Se obtendrían mayor rendimiento

• Nuevos lenguajes paralelos
• Que los compiladores extraigan el paralelismo implícito
en los programas no escritos explícitamente en paralelo
• Portabilidad de los programas entre distintas plataformas

– Reducir/ocultar la alta latencia remota

• Mediante hardware (p.e. cachés de datos compartidos)
• Mediante software, (p.e. reestructurando los accesos a
datos para que sean más locales, ocultar los accesos
remotos mediante ejecución de otras partes del código,
etc.)

– Flexibilidad en los multiprocesadores

2. Clasificación de los

multiprocesadores

• Clasificación en función de la organización

de la memoria
– Uniform Memory Access (UMA)
– NonUuniform Memory Access (NUMA)
– Message Passing Machines (MPM)
• Emulación de Multiprocesadores
• Mercado actual de los multiprocesadores

• Distintas

aplicaciones pueden

requerir distintas
topología para extraer más paralelismo. Los MPr
deberían poder cambiar su estructura
(topología,
distribución de la memoria, etc) de forma dinámica y
fácil, para así, adaptarse a las distintas aplicaciones

5

Clasificación en función de la
organización de la memoria
• La memoria es determinante en un sistema
con tanto ancho de banda de memoria
(ABmem)
– El ABmem de 1 sólo procesador es muy grande
– La memoria puede servir para comunicarse

entre los procesadores

• UMA (Uniform Memory Access)

Fig. 2.2.

– Espacio de direcciones de memoria compartido
– Tiempo de acceso uniforme para toda dirección
– Hardware bastante simple.
– El cuello de botella es el acceso a memoria

principal, lo cual implica:

• Grandes cachés en cada procesador
• El número de procesadores no puede ser muy

alto. Hoy en día N≤32.

Clasificación en función de la
organización de la memoria
– Multiprocesadores muy populares hoy en día:

• Todos los SMP’s (Multiprocesadores simétricos

con memoria compartida basado en bus común)

• bi, quad-Pentium
• Sun Enterprise 10000 (crossbar)

Fig.2.3. Organización del Pentium Pro de 4 procesadores “quad pack”

– Programación y comunicación

• Al

tener espacio de direcciones de memoria
la

compartida ⇒ Se adapta perfectamente a
programación multihilo (multi-thread)

• También

pero

se puede usar para programación
lento. La
sería mediante

multiprocesos,
comunicación entre procesos
intercambio de variables en la memoria compartida
• Surge el problema de la coherencia entre cachés ⇒

sería más

disponer de Hard adicional para solucionarlo

6

Clasificación en función de la
organización de la memoria
– Problema de coherencia en UMA

• El overhead por acceder a la memoria compartida

es muy grande. Hay que usar cachés

• Debemos asegurar la coherencia de los datos en

dichos dispositivos

• Cuando usamos un dato privado ⇒ traerlo a caché
• Si accedemos a un dato compartido, hay que traerlo
a caché, pero si otros procesadores también acceden
al dato y se lo llevan a su caché, existirán varias
copias distintas del mismo dato. Si algún
procesador modifica el dato ⇒ Problema de
coherencia

– Solución

• Intentar evitar las incoherencias mediante hard
• En UMA se usan protocolos de husmeo (snooping)
– Se pueden utilizar gracias a tener un bus único y

compartido de comunicación

– Los controladores de cachés locales espían el bus
para ver si circula algún dato de alguna línea que
tenga almacenada en su caché

– Los cachés deben de estar provistos de 2 puertos de

acceso (p.e. replicando la memoria de etiquetas)

» Uno para el acceso del procesador
» Otro para que el controlador pueda comparar

las direcciones que aparecen por el bus
• Ejemplo: Protocolo de invalidación CB (MSI)

Clasificación en función de la
organización de la memoria

• NUMA (NonUniform Memory Access)

Fig.2.4. Modelo de multiprocesador NUMA con memorias locales compartidas

– Espacio de direcciones de memoria compartido
– Tiempo de acceso no uniforme para toda dirección.
Depende de si accedemos a memoria local (no a
caché) o a remota.

al

– Debido

incremento de prestaciones del
uniprocesador y del AB requerido, ésta es la única
solución para sistemas con muchos procesadores

– tacc pequeño en accesos a memoria local
– Hard de la red es complejo, necesita redes de
interconexión especiales. Existen distintas líneas de
comunicación separadas ⇒ mayor AB

– El problema de la coherencia es más difícil de

mantener en hard

7

Clasificación en función de la
organización de la memoria
– Estos multiprocesadores son escalables

• Escalable: Si crece el número de procesadores N,
entonces la memoria crece como orden(N). Esto es
gracias a que cada procesador lleva su propia
memoria

• Los procesadores UMA no son escalables, puesto
que si aumentamos el número de procesadores, la
memoria es la misma.

– Programación y comunicación

• Comunicación entre procesadores es mediante

variables globales

• Al tener espacio de direcciones de memoria
compartida ⇒ Se adapta perfectamente a la
programación multihilo (multi-thread)

• Debe existir cacheo de datos remotos en hard,

aunque la coherencia sea compleja

• Debe existir soporte hard para el acceso remoto

– Ld local, provoca acceso a caché o memoria local
– Ld remoto, provoca interrupción I/O a la red

• Si existe coherencia, el código NUMA es
totalmente compatible con UMA. Esto supone una
ventaja, puesto que
los UMA están muy
extendidos
aplicaciones
desarrolladas. El programador debe tener cuidado
con los accesos remotos

hay muchas

y

– Ejemplos: TC2000, KSR-1, Standford Dash,

BBN Butterfly, Cray T3D

Clasificación en función de la
organización de la memoria

• Solución al problema de coherencia en NUMA
– La solución hard es más compleja que en UMA
– Han exist