PDF de programación - Sesión 9. Redes de interconexión. Topologías - Ingeniería de los Computadores

Ingeniería de los Computadores

Sesión 9. Redes de interconexión.

Topologías

Conceptos

Clasificación

Ingeniería de los Computadores
Sesión 9. Redes de interconexión
Topologías

• Redes estáticas o directas

 Clasificación

 Estrictamente ortogonales (malla, hipercubo, toro)

 (Estrictamente) Cada nodo A tiene al menos un enlace en

cada dimensión i

 (Ortogonal) Cada enlace supone un desplazamiento en

una dimensión

 No ortogonales (árbol)

 Propiedades

 Grado
 Diámetro
 Regularidad (todos los nodos tienen el mismo grado)
 Simetría (se ve semejante desde cualquier nodo)



Conceptos

Clasificación

Ingeniería de los Computadores
Sesión 9. Redes de interconexión
Topologías

• Redes estáticas o directas. Anillo unidireccional

 F. interconexión: F+1(i) = (i+1) mod N
 Grado de entrada/salida: 1/1
 Diámetro: N-1

EP5

EP4

EP0

EP3

EP1

EP2



 ¿Anillo bidireccional?



Conceptos

Clasificación

Ingeniería de los Computadores
Sesión 9. Redes de interconexión
Topologías

• Redes estáticas o directas. Malla abierta

 F. interconexión:

 F+1(i) = (i+1) si i mod r <> r-1
 F-1(i) = (i-1) si i mod r <> 0
 F+r(i) = (i+r) si i div r <> r-1
 F-r(i) = (i-r) si i div r<>0

 Grado: 4
 Diámetro: 2(r-1), donde N=r2



Conceptos

Clasificación

Ingeniería de los Computadores
Sesión 9. Redes de interconexión
Topologías

• Redes estáticas o directas. Malla Illiac

 F. interconexión:

 F+1(i) = (i+1) mod N
 F-1(i) = (i-1) mod N
 F+r(i) = (i+r) mod N
 F-r(i) = (i-r) mod N

 Grado: 4
 Diámetro: (r-1), donde N=r2



Conceptos

Clasificación

Ingeniería de los Computadores
Sesión 9. Redes de interconexión
Topologías

• Redes estáticas o directas. Redes n-cubos k-arias ó toros

 n dimensiones, k nodos
 F. interconexión toro 2D:

 F+1(i) = (i+1) mod r + (i DIV r) · r
 F-1(i) = (i-1) mod r + (i DIV r) · r
 F+r(i) = (i+r) mod N
 F-r(i) = (i-r) mod N

 Grado: 4
 Diámetro: , donde N=r2

2

⋅


r
2






Conceptos

Clasificación

Ingeniería de los Computadores
Sesión 9. Redes de interconexión
Topologías

• Redes estáticas o directas. Desplazador barril

 F. interconexión:

 B+k(i) = (i+2k) mod N
 B-k(i) = (i -2k) mod N
 K=0...n-1, n=log N, i=0...N-1

 Grado: 2n - 1
 Diámetro: n/2



Conceptos

Clasificación

Ingeniería de los Computadores
Sesión 9. Redes de interconexión
Topologías

• Redes estáticas o directas. Hipercubo

 F. interconexión:

 Fi (hn-1, ... , hi, ... h0) = hn-1, ... , h�i, ... h0

 Grado: n (n=log N)
 Diámetro: n



Conceptos

Clasificación

Ingeniería de los Computadores
Sesión 9. Redes de interconexión
Topologías

• Redes estáticas o directas. Ciclo cubo conectado (CCC) (red jerárquica)



2 niveles

1º Anillo

2º Hipercubo

•Grado pequeño
•Diámetro grande
•Fácil encaminar

•Grado grande
•Diámetro pequeño
•Fácil encaminar

Conceptos

Clasificación

Ingeniería de los Computadores
Sesión 9. Redes de interconexión
Topologías

• Redes estáticas o directas. Red CCC



(000,1)

(000,2)

(000,0)

Conceptos

Clasificación

Ingeniería de los Computadores
Sesión 9. Redes de interconexión
Topologías

• Redes estáticas o directas. Árbol binario

 Balanceado: todas las ramas del árbol tienen la misma longitud
 Cuello de botella  nodo raíz
 N (balanceado)= 2k-1 (k = niveles del árbol)
 Grado: 3
 Diámetro: 2(k-1)



Conceptos

Clasificación

Ingeniería de los Computadores
Sesión 9. Redes de interconexión
Topologías

• Redes indirectas o dinámicas

 Uso de conmutadores y árbitros
 Ejemplos

 Redes crossbar
 Redes de conexión multietapa (MIN)

 Modelo: G(N,C)

 N, conjunto de conmutadores
 C, enlaces (unidireccionales o bidireccionales) entre

conmutadores

 Canal bidireccional  dos canales unidireccionales
 Un conmutador puede tener conectados 0, 1 ó más

elementos (Procesadores, memorias, etc.)

 Distancia entre dos nodos: distancia entre los conmutadores que

conectan los nodos más 2.



Conceptos

Clasificación

Ingeniería de los Computadores
Sesión 9. Redes de interconexión
Topologías

• Redes indirectas o dinámicas. Redes crossbar

 Conexión directa nodo-nodo
 Gran ancho de banda y capacidad de interconexión
 Conexión Proc. – Mem.  limitado por los accesos a memoria

(columnas)

 Conexión Proc(N) – Proc(N)  máximo de N conexiones
 Coste elevado: O(N·M)

P1

Pn

P2

...



M1

M2
...
Mn

Conceptos

Clasificación

Ingeniería de los Computadores
Sesión 9. Redes de interconexión
Topologías

• Redes indirectas o dinámicas. Redes MIN

 Conectan dispositivos de entrada con dispositivos de salida

mediante un conjunto de etapas de conmutadores, donde cada
conmutador es una red crossbar.

 Concentradores  nº entradas > nº salidas
 Expansores  nº salidas > nº entradas



A

B

S1

S2

CA

CB

Conceptos

Clasificación

Ingeniería de los Computadores
Sesión 9. Redes de interconexión
Topologías

• Redes indirectas o dinámicas. Redes MIN

 Conexión de etapas adyacentes  Patrón de conexión
 Patrón basado en permutaciones: conmutadores con el mismo

número de entradas y salidas.

 Ejemplo: barajado perfecto.

B (an-1, an-2, ..., a0) = (an-2, ... , a0, an-1)



Conceptos

Clasificación

Ingeniería de los Computadores
Sesión 9. Redes de interconexión
Topologías

• Redes indirectas o dinámicas. Redes MIN

 Número de entradas an y número de salidas bn (red anxbn)

 n etapas de conmutadores (C0, C1, …,Cn-1)
 Conmutadores axb
 an-1-i x bi conmutadores en la etapa Ci

 Funcionalidad de los conmutadores: barras cruzadas, reducción,

difusión

 Subred de interconexión entre etapas: R0, R1,…
 Tipos de canales: unidireccionales, bidireccionales



Conceptos

Clasificación

Ingeniería de los Computadores
Sesión 9. Redes de interconexión
Topologías

• Redes indirectas o dinámicas. Redes MIN – red Omega

 El patrón de conexión Ci es una permutación k-baraje perfecto a excepción del último

(Rn) que es permutación 0



Conceptos

Clasificación

Ingeniería de los Computadores
Sesión 9. Redes de interconexión
Topologías

• Redes indirectas o dinámicas. Redes MIN – red mariposa



Conceptos

Clasificación

Ingeniería de los Computadores
Sesión 9. Redes de interconexión
Topologías

• Redes indirectas o dinámicas. Redes MIN – red cubo



Conceptos

Clasificación

Ingeniería de los Computadores
Sesión 9. Redes de interconexión
Topologías

• Redes indirectas o dinámicas. Redes MIN – red delta



Conceptos

Clasificación

Ingeniería de los Computadores
Sesión 9. Redes de interconexión
Topologías

• Prestaciones