PDF de programación - Tema 2 - Arquitecturas multiprocesador: MIMD de memoria distribuida (multicomputadores)

Tema 2

Arquitecturas multiprocesador:
MIMD de memoria distribuida

(multicomputadores)

José M. Cámara ([email protected])

v. 1.0

Introducción
 Máquinas de hardware débilmente acoplado.
 Existen diferentes niveles de acoplamiento en

esta categoría en función del harware
compartido: almacenamiento,
entrada/salida…

 Al no disponer de espacio común en

memoria, la comunicación se va a llevar a
cabo mediante paso de mensajes.
 Mensaje: unidad de intercambio de información.
 Paquete: unidad de conmutación.

Conmutación

Conmutación de circuitos: se establece una conexión
permanente para la transmisión del mensaje completo.
Conmutación de paquetes (control de flujo):

Sin división: T=(N-1)(L/W) store & forward
Con división en flits: T=(L/W) + (F/W)(N-2) wormhole
Con división en phits: T = L/W + (P/W)(N-2) virtual cut through

Paquetes: disponen de información de destino y nº de orden dentro del mensaje.
Flits (flow control unit): no disponen de ninguna información salvo el de cabecera, por lo que
todos deben seguirle.
Phits: unidad mínima de información posible; equivale al nº de líneas de datos del enlace.

El pipeline en VCT es análogo a Wormhole pero requiere espacio de
almacenamiento intermedio para paquetes completos, como S&F.

Estrategias de conmutación

Store & forward

Wormhole

Virtual cut through

Conmutación de paquetes

Aspectos relevantes:

Control de flujo: cómo y cuando se mueven los paquetes por la
red. Incluye:

Resolución de colisiones: entre paquetes entrantes cuando los recursos de
almacenamiento son escasos.
Encaminamiento: cómo hacer que los paquetes lleguen a su destino.
Bloqueo (deadlock): los paquetes se bloquean formando un
bucle -> la red se colapsa.
Livelock: un paquete se mueve por la red sin llegar nunca a
destino.
Inanición (starvation): un paquete no recibe nunca servicio y
queda anclado en un elemento de almacenamiento.

Abrazo mortal e inanición

Abrazo mortal de tráfico

http://fedoraproject.org/wiki/FAD_SP_2013

Situación potencial de inanición
Los coches procedentes de las calles en la

mitad inferior podrían no conseguir acceder a

la rotonda.

Conmutación de paquetes

Soluciones:

Bloqueo

 Canales virtuales para demorar la aparición del bloqueo
 Ciertas combinaciones de interconexión – algoritmo de encaminamiento están libres de bloqueo.
 Recuperación: si el bloqueo aparece, el sistema puede descartar un paquete para deshacerlo.

Debe notificarlo al emisor para que pueda reintentar.

Resolución de colisiones

Descartar
Almacenar
Reenviar -> livelock
Bloquear

Encaminamiento

Algoritmos de encaminamiento

Buff. CV 1

Buff. CV 2

Buff. CV n

l


r
o
x
e
p
i
t
l
u
M

CV1

CVn

CV2

CV1

l


r
o
x
e
p
i
t
l
u
m
e
D

Buff. CV 1

Buff. CV 2

Buff. CV n

Canales virtuales multiplexados en el tiempo

Contenido multimedia disponible

Algoritmos de encaminamiento

Criterios de clasificación:

Número de destino: unicast, multicast
Lugar donde se toman las decisiones: centralizados,
fuente, distribuidos
Forma de implementación: tabla, máquina de estados
Adaptatividad: deterministas, adaptativos
Nº de caminos alternativos: parcialmente adaptativos,
totalmente adaptativos
Progresividad: progresivos, regresivos
Minimalidad: mínimos, no mínimos -> livelock

CONMUTACIÓN DE

PAQUETES

ENCAMINAMIENTO

ROUTER GENÉRICO

(Intel Paragon)

Norte

Nodo local

Controlador de entrada

Buffer de flit

Oeste

Crossbar

Este

Sur

SITUACIÓN DE ABRAZO

MORTAL I

D→

C↓

A

B

D

C

A↑

B←

SITUACIÓN DE ABRAZO

MORTAL II

C↓

A

B

D

C

A↑

D→

B←

SITUACIÓN DE ABRAZO

MORTAL III

C↓

A

B

D→

B←

D

C

A↑

SITUACIÓN DE ABRAZO

MORTAL IV

A/ C↓ D/ B←

B/D→

C/A↑



ENCAMINAMIENTO DOR I

D→

C→

A

B

D

C

A ←

B←

ENCAMINAMIENTO DOR II

C↓

A

B

D

C

D→

B←

A↑

ENCAMINAMIENTO DOR III

C↓

D

C

B←

D→

A

B

A↑

ENCAMINAMIENTO DOR IV

C↓

D/ B←

A

B/D→

C


A↑

ENCAMINAMIENTO DOR IV

A/ B↓

D/C↓

B/A↑

C/D↑



ENCAMINAMIENTO DOR V

A/ B↓

D/C↓

B/A↑


C/D↑



ENCAMINAMIENTO DOR VI

A

D

B/A↑


C/D↑



REDES VIRTUALES I

(noroeste)

A

B

D

C

A↑

REDES VIRTUALES I

(noreste)

D→

A

B

D

C

REDES VIRTUALES I

(suroeste)

A

B

D

C

B←

REDES VIRTUALES I

(sureste)

C↓

A

B

D

C

REDES VIRTUALES II

(noroeste)

A

B

D

C

A↑

REDES VIRTUALES II

(noreste)

A

B

D

C

D→

REDES VIRTUALES II

(suroeste)

A

B

D

C

B←

REDES VIRTUALES II

(sureste)

C↓

A

B

D

C

REDES VIRTUALES III

(noroeste)

A

B

D

C

A↑

REDES VIRTUALES III

(noreste)

A

B

D

C

D→

REDES VIRTUALES III

(suroeste)

B←

A

B

D

C

REDES VIRTUALES III

(sureste)

C↓

A

B

D

C

REDES VIRTUALES IV

(noroeste)

A

B

D

C/A↑



REDES VIRTUALES IV

(noreste)

A

B/D→



D

C

REDES VIRTUALES IV

(suroeste)

A

B

D/ B←

C

REDES VIRTUALES IV

(sureste)

A/ C↓

B

D

C

REDES VIRTUALES V

(noroeste)

A

B

D/ A←

C

REDES VIRTUALES V

(noreste)

A

B

D

C/D↑



REDES VIRTUALES V

(suroeste)

A/ B↓

B

D

C

REDES VIRTUALES V

(sureste)

A

B/C→



D

C

Ejemplo de algoritmo de

encamianmiento

• Topología: malla.
• Tipo de algoritmo: unicast, progresivo, centralizado, mínimo.
• Según su implementación puede ser:

– Determinista o adaptativo.
– Tabla o máquina de estados.

• Compatible con DOR.
• Consiste en restar las coordenadas del nodo fuente de las del

nodo destino.

• Para ir del nodo (2,8) al nodo (12, 6), la ruta se compone de 12

– 2 = 10 saltos en sentido x+ y 6 – 8 = 2 saltos en sentido y-.