PDF de programación - Sesión 8. Redes de interconexión. Conceptos y clasificación - Ingeniería de los Computadores

Ingeniería de los Computadores

Sesión 8. Redes de interconexión.

Conceptos y clasificación

Conceptos

Ingeniería de los Computadores
Sesión 8. Redes de interconexión

• Redes de Interconexión



 Elemento fundamental en arquitecturas paralelas con varios

elementos de proceso que se comunican


 Eficiencia en la comunicación crítica: multiprocesadores,

multicomputadores


 Diseño de la red condiciona: escalabilidad de la arquitectura,

complejidad, tolerancia a fallos, etc.


 Aspectos relacionados: control de flujo y encaminamiento



Conceptos

Ingeniería de los Computadores
Sesión 8. Redes de interconexión

• Estructura general del sistema de comunicación

Conceptos

Ingeniería de los Computadores
Sesión 8. Redes de interconexión

• Parámetros básicos



 Tamaño de la red: número de nodos (EPs, memorias,

computadores)

 Grado del nodo (d – degree): número de canales de entrada y

salida

 Nodos unidireccionales: grado de salida y grado de entrada
 Grado del nodo -> puertos de E/S (¿coste?)
 Diámetro de red: longitud máxima del camino más corto entre

dos nodos cualquiera de una red.


Conceptos

Ingeniería de los Computadores
Sesión 8. Redes de interconexión

• Parámetros básicos



 Anchura de la bisección (B): mínimo número de canales que, al

cortar, separa la red en dos partes iguales
 El número de cables que cruzan la bisección es una cota inferior de la

densidad de cableado

 Longitud del cable: efectos sobre la latencia
 Simetría: Una red es simétrica si es isomorfa a ella misma

independientemente del nodo considerado origen

 Rendimiento

 Funcionalidad. Indica cómo la red soporta el encaminamiento

de datos, tratamiento de las interrupciones, sincronización.

 Latencia. Indica el retraso de un mensaje



Conceptos

Ingeniería de los Computadores
Sesión 8. Redes de interconexión

• Parámetros básicos



 Rendimiento

 Ancho de banda. Velocidad máxima de transmisión de datos
 Complejidad hardware. Coste de implementación (cables,

conmutadores, conectores, etc.)

 Escalabilidad. Capacidad de la red para expandirse de forma

modular

 Capacidad de transmisión. Número total de datos que se

pueden transmitir a través de la red en una unidad de tiempo.
(Punto caliente)



Conceptos

Ingeniería de los Computadores
Sesión 8. Redes de interconexión

• Diseño de una red de inteconexión

 Topología -> grafo de interconexión
 Control de flujo -> método usado para regular el tráfico en la red

 Mensaje
 Paquete
 Flit

 Encaminamiento -> método usado por un mensaje para elegir un

camino entre los canales de la red
 Determinista
 Adaptativo



Conceptos

Ingeniería de los Computadores
Sesión 8. Redes de interconexión

• Diseño de una red de interconexión



Conceptos

Ingeniería de los Computadores
Sesión 8. Redes de interconexión

• Diseño de una red de interconexión. Topología



Conceptos

Ingeniería de los Computadores
Sesión 8. Redes de interconexión

• Diseño de una red de interconexión. Encaminamiento



Conceptos

Ingeniería de los Computadores
Sesión 8. Redes de interconexión

• Diseño de una red de interconexión



Conceptos

Ingeniería de los Computadores
Sesión 8. Redes de interconexión

• Diseño de una red de interconexión. Control de flujo



Conceptos

Ingeniería de los Computadores
Sesión 8. Redes de interconexión

• Diseño de una red de interconexión. Niveles de servicios



Conceptos

Clasificación

Ingeniería de los Computadores
Sesión 8. Redes de interconexión

• Clasificación de redes de interconexión



Conceptos

Clasificación

Ingeniería de los Computadores
Sesión 8. Redes de interconexión

• Clasificación de redes de interconexión



 Redes de medio compartido

 Redes de área local

 Bus de contención (Ethernet)
 Token bus (Arcnet)
 Token ring (IBM Token ring)

 Bus de sistema (backplane bus) (Sun Gigaplane)

 Redes directas (estáticas basadas en router)

 Topologías ortogonales (Malla, Toro, Hipercubo)
 Otras topologías (Árbol, CCC, Estrella, …)

 Redes indirectas (dinámicas basadas en conmutador)



Conceptos

Clasificación

Ingeniería de los Computadores
Sesión 8. Redes de interconexión

• Clasificación de redes de interconexión



 Redes de medio compartido
 Redes directas
 Redes indirectas (dinámicas basadas en conmutador)

 Topologías regulares

 Barra cruzada (Crossbar)
 Redes de interconexión multietapa (MIN)

 Con bloqueos (unidireccionales y bidireccionales)
 Sin bloqueos (red de Clos)

 Topologías irregulares

 Redes híbridas (redes jerárquicas)



Conceptos

Clasificación

Ingeniería de los Computadores
Sesión 8. Redes de interconexión

• Redes de medio compartido



 Medio de transmisión compartido
 Arbitraje (resolución de conflictos)
 Sencillo Broadcast
 Ancho de banda limitado (escalabilidad limitada) -> cuello de

botella

 Bus de sistema (arquitectura UMA: Proc -> Mem)
 Redes de área local

 Ethernet (no determinista)
 Token bus (determinista  aplic. tiempo real)
 Token ring (estructura en anillo)



Conceptos

Clasificación

Ingeniería de los Computadores
Sesión 8. Redes de interconexión

• Redes de medio compartido (arbitraje del bus)



 Prioridad estática. Señales de control:

 BRQ
 BGNT
 BBSY común



BRQ

BGNT

BBSY

Conceptos

Clasificación

Ingeniería de los Computadores
Sesión 8. Redes de interconexión

• Redes de medio compartido (arbitraje del bus)



 Prioridad estática. Daisy Chain (centralizada-serie):

 BRQ común
 BGNT propagada
 BBSY común



BGNT

P1

P2

Pn



Módulo

de

arbitraje



BRQ

BBSY

Conceptos

Clasificación

Ingeniería de los Computadores
Sesión 8. Redes de interconexión

• Redes de medio compartido (arbitraje del bus)



 Prioridad estática. Codificador-decodificador de prioridad

(centralizada-paralela)
 BRQ individual
 BGNT individual
 BBSY común



Módulo

de

arbitraje

P2

Pn

BGNT

BRQ

P1

BBSY



Conceptos

Clasificación

Ingeniería de los Computadores
Sesión 8. Redes de interconexión

• Redes de medio compartido (arbitraje del bus)



 Prioridad estática. Codificador-decodificador de prioridad

(centralizada-paralela)
 BRQ individual
 BGNT individual
 BBSY común



BRQ

...



Codificador

de

proridad



BGNT



Decodificador



...

Línea de
presencia
(BBSY)

Conceptos

Clasificación

Ingeniería de los Computadores
Sesión 8. Redes de interconexión

• Redes de medio compartido (arbitraje del bus)



 Prioridad estática. Autoarbitraje (distribuido-paralelo)

 BRQ individual
 BGNT individual
 BBSY común



Módulo

de

arbitraje

Módulo

de

arbitraje

Módulo

de

arbitraje

BRQ

P1

P2

...

Pn

BGNT

BBSY

Conceptos

Clasificación

Ingeniería de los Computadores
Sesión 8. Redes de interconexión

• Redes de medio compartido (arbitraje del bus)



 Multiplexación temporal

 Ventajas

 Asignación equitativa
 Simplicidad
 Inconvenientes

 Infrautilización del ancho de banda

 Prioridad dinámica

 LRU
 RDC
 FCFS



Conceptos

Clasificación

Ingeniería de los Computadores
Sesión 8. Redes de interconexión

• Redes de medio compartido (arbitraje del bus)



 Prioridad dinámica (LRU)

P0 P1 P2 P3 Acción
0 1 2 3 P0 utiliza bus
0 1 2 3 P2 solicita bus
1 2 0 3 P2 utiliza bus
1 2 0 3 P1 y P3 solicitan bus
2 3 1 0 P3 utiliza bus

Conceptos

Clasificación

Ingeniería de los Computadores
Sesión 8. Redes de interconexión

• Redes directas

 Nodos conectados a subconjuntos de nodos
 Escalabilidad
 Router -> comunicación entre los nodos
 Canales unidireccionales o bidireccionales

• Redes indirectas

 Comunicación a través de conmutadores
 Topologías regulares (matriciales) e irregulares (NOWs)

• Redes híbridas (combinación de las anteriores)
• Redes multibus
• Redes jerárquicas (jerarquía de buses conectados mediante routers )
• Redes basadas en clusters

 Nodos conectados (buses – fácil broadcast) formando clusters
 Clusters conectados entre sí (red directa - escalabilidad)