10 - redes de interconexion i v9
TRANSCRIPT
Conmutación de Paquetes 2
Índice
Conceptos Básicos de Redes de interconexión Accesibilidad y Bloqueo Equivalencia entre redes Redes crossbar basadas en splitters y combiners
Redes multietapa de conexión total (FC) Redes multietapa de conexión parcial (PC)
Redes Banyan Redes de Fusión Redes de ordenación (Batcher)
Conmutación de Paquetes 3
REDES DE INTERCONEXIÓN Parte 1
Conmutación de Paquetes 4
Conceptos Básicos: Accesibilidad
Accesibilidad Total vs Limitada Una red tiene accesibilidad total cuando cada entrada puede
ser conectada a cada salida cuando ninguna otra conexión ha sido establecida.
Red de interconexión NxM
N entradas M Salidas
Conmutación de Paquetes 5
Conceptos Básicos: Bloqueo Redes con bloqueo:
Si existe al menos una conexión entrada-salida libres que no puede ser establecida … sin cambiar el estado de la red, i.e. Sin liberar otras ya establecidas. i.e. Red con bloqueo: conexiones establecidas impiden otras
Redes sin bloqueo: Siempre existe la posibilidad de establecer un
camino a través de la red de interconexión independientemente del estado de la red
Existen tres tipos diferentes de redes de interconexión sin bloqueo.
Conmutación de Paquetes 6
Redes de interconexión sin bloqueo
Red sin bloqueo en sentido estricto (SNB) Conexión siempre posible. Independencia del estado de la red. Independiente de las políticas de establecimiento definidas.
Red sin bloqueo en sentido amplio (WNB) Podría existir bloqueo, pero se evita Dependiente de la política de establecimiento.
Red sin bloqueo mediante reconfiguración (RNB) Existe un camino disponible, pero: Podría ser necesario aplicar políticas de reconfiguración
sobre las conexiones ya establecidas Existe bloqueo pero se resuelve Se denominan redes “reconfigurables”
Conmutación de Paquetes 7
Red de Referencia: crossbar network
COSTE DE LA RED N
M
Conmutación de Paquetes 8
Coste de una red de interconexión
Métrica típica: Número de Puntos de Cruce Existen más métricas, pero ésta es la que más
comúnmente se utiliza Red de Referencia: Crossbar NxM
Cost C = N*M N = M C = N2
Red sin bloqueo Cada punto de cruce está dedicado a un par específico
de entrada/salida
N inlets
M outlets
Conmutación de Paquetes 9
Permutaciones Crossbar con NxN (p.e N = M) se puede ver como el desarrollo de
una permutación arbitraria P: conjunto de todas las permutaciones posibles en la red Entonces: |P| ≤ N !
|P| = N! para una red crossbar
(sin considerar conexiones multipunto) Ejemplo: Crossbar con N = 3
Posibles 3! = 6 permutaciones:
0 0 0 1 1 2 2 1 1 2 0 2 0 1 2 2 1 2 0 1 0
0 1 2
0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2
Entradas Salidas
Conmutación de Paquetes 10
Propiedades de una Red Crossbar
Sin bloqueo en sentido estricto
P = N! para N=M
C = N x M
Conmutación de Paquetes 11
REDES MULTI-ETAPA Parte 2
Conmutación de Paquetes 12
Redes Multietapa
Objetivo: Sin bloqueo Menor coste
Solución: Redes multietapa (multistage) Reutilización de pequeñas matrices varias veces e
interconectadas entre sí
Conmutación de Paquetes 13
Modelo General para redes multietapa
N M
1 2 s
1
2
r1
1
2
r2 rs
ns x ms
n1
Conmutación de Paquetes 14
Redes Multietapa
Comentarios: s etapas con ri matrices de ni x mi en la etapa i (i=1,...,s) Se cumple que N = n1r1 and M = msrs
Cada matriz ni x mi Se asume que es sin bloqueo (SNB)
Red de interconexión Red Multietapa de conexión total
Full-connection (FC)
Cada Matriz en la etapa i (i=1,...,s) se conecta a todas las matrices en la etapa i-1 e i+1;
Red multietapa de conexión parcial
Partial-connection (PC): No existe Full-Connection
Conmutación de Paquetes 15
Parámetros de una red multietapa
N x M N: # entradas a la red, M: # salidas de la red
s: # etapas
ri: # matrices crossbar en la etapa i, (i=1 ... s)
ni , mi - representa las dimensiones de crossbars en la etapa i
Conmutación de Paquetes 16
Modelo General para redes multietapa
N M ni mi
Conmutación de Paquetes 17
Parámetros de una red multietapa (2)
ri x mi => numero total de salidas en la etapa i
ni x ri => numero total de entradas en la etapa i
N / n1 => número de crossbars en la 1ª etapa
Conmutación de Paquetes 18
Patrón de interconexión entre etapas
i i+1 mi*ri = n i+1 * r i+1
Conmutación de Paquetes 19
Interconexiones: Extended Generalized Shuffle
i i+1
( ji , ki ) ( ji+1 , ki+1 )
ki
ji
ji+1 ki+1
1
2
( ) [ ] 1 1
mod 1 1 + +
+ - = + i r
j k m k i i i i
1
0
0
mi-1 0
ni-1
Red representable con un EGS: “EGS network”
Conmutación de Paquetes 20
Extended Generalized Shuffle
mi*ri = n i+1 * r i+1 i i+1
Conmutación de Paquetes 21
Extended Generalized Shuffle
mi*ri = n i+1 * r i+1 i i+1
Conmutación de Paquetes 22
Extended Generalized Shuffle
mi*ri = n i+1 * r i+1 i i+1
Conmutación de Paquetes 23
Otro ejemplo de Red multietapa
No todas son representables como EGS
Dos etapas con tres matrices (H, I, J) N = M = 4 Red de interconexión
H 0
1
a b
I 0
1 d c
J 0
1
e f
h g
Conmutación de Paquetes 24
EQUIVALENCIA ENTRE REDES Parte 2.1
Conmutación de Paquetes 25
Representando redes multietapa: Grafos
Grafo de red (o simplemente grafo): Nodo: representa una matriz crossbar Arco: representa un enlace entre matrices Inlets/outlets no son representadas
No aportan información relevante al análisis Grafo de canal de una red:
Representa la asociación de cada entrada/salida Indica la secuencia de los elementos de red
usados para el camino desde la entrada a la salida Nodo: representa una matriz crossbar Arco: representa un enlace (o malla)
Red Regular: Aquella en la que los grafos de canal de todas las
conexiones son iguales Ejemplo: Grafo de canal a f
Ejemplo: Grafo de Red para el ejemplo
anterior
Conmutación de Paquetes 26
Equivalencia entre redes (1)
Redes Isomorfas: Dos redes A y B son isomorfas si se puede
establecer entre ellas un isomorfismo con conservación de etiquetas ie. Si reetiquetando una a una las entradas, salidas y
matrices de A con las de B, la red puede hacerse idéntica a B moviendo sus matrices y sus enlaces
Ie. Si moviendo las matrices conjuntamente con los enlaces conectados (se puede voltear), el resultado mapea matrices y etiquetas una a una
Dos redes isomorficas tienen el mismo grafo de canal.
Conmutación de Paquetes 27
Equivalencia entre redes (2)
Topológicamente equivalentes Dos redes son topológicamente equivalentes si podemos
establecer un isomorfismo entre los grafos de las dos redes Si reetiquetando nodos son idénticos
Funcionalmente equivalentes Dos redes son funcionalmente equivalentes si el conjunto de
sus permutaciones es igual
PA = PB
Dos redes sin bloqueo son siempre funcionalmente equivalentes.
PA = PB = conjunto de N! (todas las posibles) permutaciones
Conmutación de Paquetes 28
Equivalencia entre redes (3)
Source: A. Pattavina, “Switching Theory, architecture and performance ....”
Etiqueta
Mismo grafo de red => topologicamente equivalentes
Conmutación de Paquetes 29
Ejemplo de isomorfismo
X 0
1
s
t
Y 0
1 v
u
Z 0
1
w
x
z
y
au bv cs dt
ez fw gx hy
Isomorfismo: HY IX JZ
H 0
1
a
b
I 0
1 d
c J
0
1
e
f
h
g
H 1
0
a
b
I 0
1 d
c J
0
1
e
f
h
g
A’ A’’
B
Conmutación de Paquetes 30
CROSSBAR con COMBINADORES y DIVISORES
Parte 2.2
Conmutación de Paquetes 31
Crossbar Networks Basadas en combinadores y Divisores
Objetivo: Construir una crossbar con un numero menor de bloques Divisores: 1xK
Coste c = K Combinadores: Kx1
Coste c = K Ambos elementos asimétricos pueden manejar solo una
conexión Construiremos un árbol de red de crossbar (Crossbar tree
network) Funcionalmente es equivalente a un crossbar Construida con N divisores (splitters) 1xN & N combinadores
(combiners) Nx1
• • • K
• • • K
Conmutación de Paquetes 32
Árbol Crossbar
• • •
0
• • •
1
• • •
N-1
• • • 0
• • • 1
• • • N-1
Coste: C = 2 N2
1xN Nx1
• • •
• • •
Es dos veces el coste de un Crossbar. ¿?
Conmutación de Paquetes 33
Crossbar Binary Tree
Sustituimos cada elemento 1xK o Kx1 por un árbol con muchos elementos 1x2 o 2x1
• • • N N
Coste c = 4N2 - 4N
Conmutación de Paquetes 34
Ejemplo: Crossbar tree con etapa central
Ejemplo: K = 2, N = 8 K2 = 4 matrices N/K = 4 líneas de salida por matriz
0
1
2
3
4
5
6
7
0
1
2
3
4
5
6
7
Conmutación de Paquetes 35
Crossbar tree con etapa central
Implementar una crossbar tree con una etapa central de conmutación para reducir costes Divisores 1xK en cada entrada.
Se debe cumplir que K = 2k (k = 1... log2N-1)
Cada entrada tiene acceso a K matrices de la etapa central Matriz central:
N/K salidas a los combinadores necesarios para alcanzar la
accesibilidad total
Numero de Matrices: K*N / (N/K) = K2
Coste: c = K2 (N/K)2 + 2NK = N2 + 2NK
Conmutación de Paquetes 36
REDES MULTIETAPA DE CONEXIÓN TOTAL
Parte 3
Conmutación de Paquetes 37
Diagrama de bloques para FC
Crossbar de dos etapas:
Mostrar que en todo momento puede estar con cualquiera de estos dos estados
Conmutación de Paquetes 38
Redes multi etapa Full-Connection
En general se asume: Las Matrices en etapas adyacentes están siempre conectadas
por un solo enlace
ni = ri-1 y mi-1 = ri
Modelo General:
n1 x m1
n1 x m1
n2 x m2
n2 x m2
ni x mi
ni x mi
#1
#r1 #r2 #ri
#1 #1
ns-1 x ms-1
ns-1 x ms-1
ns x ms
ns x ms
#1
#rs-1 #rs
#1
N M
Conmutación de Paquetes 39
Redes de Conectividad total con dos y tres etapas
Redes de dos etapas: Hay accesibilidad total pero tienen bloqueo
Redes de tres etapas: Accesibilidad total Caminos diferentes entre una pareja de Entrada/salida Parámetros de diseño:
Número de matrices en la etapa intermedia n1 y m3
Determinar si el switch es con o sin bloqueo
SNB: Redes de Clos
Conmutación de Paquetes 40
REDES MULTIETAPA DE CONEXIÓN PARCIAL
Parte 4 a)
Conmutación de Paquetes 41
Redes multietapa de conexión parcial (PC)
Conmutadores de alta velocidad Prestaciones Alto grado de paralelismo Paralelismo: acceso a memorias, route lookups, … switching fabric
Redes multietapa de conectividad parcial Cada matriz se conecta solamente a un subconjunto de las matrices
de la siguiente etapa Elementos de Conmutación (SE):
Matrices pequeñas con un tamaño constante 2kx2k con k∈[1,...,5] Ejemplo típico: k = 1 2x2 Switching Elements
Propiedad de Packet self routing (auto encaminables): Cada SE puede “enrutar” paquetes dentro de la R.I. autónomamente Procesamiento en paralelo de paquetes es posible
Es necesaria una lógica de control apropiada
Conmutación de Paquetes 42
Redes de Banyan
Son un tipo de red multietapa NxN de conexión parcial Se construye mediante elementos de conmutación (SE)
Tamaño: bxb Numeración ó etiquetado entrada/salida: 0...b-1 Numero de etapas: s = logbN Numero de matrices por etapa: N/b
Auto encaminamiento Sólo existe un camino por pareja I/O En general son redes con bloqueo
Pero es posible introducir modificaciones para crear redes de Banyan strictly non-blocking o rearrangeable non-blocking
Conmutación de Paquetes 43
Redes de Banyan Delta Red Banyan “Delta”:
Todos los N caminos a una salida tienen el mismo descriptor de camino (path descriptor) self routing property! Path descriptor = secuencia de outlets de salida de cada matriz
No consideramos aquí otro tipo de red Banyan.
Regla de construcción especial que asegura self-routing property Construcción del árbol hacia atrás desde las salidas a las
entradas Las entradas de una matriz en la etapa i se conectan a b salidas con la
misma etiqueta en la matriz de la etapa i-1 (varios patrones posibles)
Hasta llegar a la primera etapa
• Llegamos a todas las matrices de la 1ª etapa, ya que s = logb(N)
hay un camino desde cada matriz de la última etapa a todas las matrices de la primera etapa
Conmutación de Paquetes 44
Ejemplo: construcción de Red Delta (I) Se comienza con una red de interconexión vacía Paso 1: conectar matriz 9 (1ª en la última etapa)
Conecta las entradas de la matriz 9 al mismo índice de salida de la etapa anterior (p.e. índice 0)
Repetir el mismo proceso en las siguientes matrices hasta llegar a la primera etapa
En este ejemplo conectamos siempre al índice cero en el primer paso, pero se puede hacer de otro modo
1
2
3
4
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
5
6
7
8
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
9
10
11
12
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
000 001
Conmutación de Paquetes 45
Ejemplo: construcción de Red Delta (II)
Paso 2: Repetir el mismo proceso comenzando por la matriz 10:
Conectar la matriz 10 a todas las matrices de primera etapa Aquí: Conecto a la salida con índice 1 de la etapa anterior
1
2
3
4
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
5
6
7
8
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
9
10
11
12
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
010 011
Conmutación de Paquetes 46
Ejemplo: construcción de Red Delta (III)
Paso 3: conectar la matriz 11 Utilizar la salida con índice 0 entre las etapas 2 y 3 Utilizar la salida con índice 1 entre las etapas 1 y 2
1
2
3
4
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
5
6
7
8
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
9
10
11
12
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
100 101
Conmutación de Paquetes 47
Ejemplo: construcción de Red Delta (IV)
Paso 4: Conectar la matriz 12 Utilizar la salida con índice 1 en las dos mallas
Resultado: Red Delta de tipo Baseline
1
2
3
4
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
5
6
7
8
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
9
10
11
12
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
110 111
Conmutación de Paquetes 48
Ejemplo: Propiedades de Red Delta Propiedad de las redes Delta Banyan:
Todos los N paths a una salida tienen el mismo path descriptor
Packet Self routing de acuerdo a la salida “Direccionada” Ejemplo: Salida 5 (path descriptor “101”)
1
2
3
4
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
5
6
7
8
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
9
10
11
12
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
Salida 0 = 000 Salida 1 = 001
Salida 2 = 010 Salida 3 = 011
Salida 4 = 100 Salida 5 = 101
Salida 6 = 110 Salida 7 = 111
Matriz 1: Camino 101
Matriz 2: Camino 101
Matriz 3: Camino 101
Matriz 4: Camino 101
Conmutación de Paquetes 49
Topologías de redes Delta
Existe diferentes topologías posibles dependiendo en las reglas específicas de construcción
Cuatro redes típicas Delta Banyan: Baseline: Φ Omega: Ω SW-banyan: Σ n-cube: Γ
Realmente no son más que diferentes métodos de interconexión entre las etapas de acuerdo con la regla de Red Delta
Se cumple que todas ellas son Isomorfas Topológicamente equivalentes Omega y n-cube son además funcionalmente equivalentes
Por lo tanto sólo existen tres tipos distintos...
Conmutación de Paquetes 50
Redes Banyan Recursivas
Las redes SW-banyan y baseline se pueden construir recursivamente
El ejemplo anterior es un Baseline recursivo: ΦN
1
2
3
4
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
5
6
7
8
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
9
10
11
12
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
7
8
0
1
0
1
0
1
0
1
11
12
0
1
0
1
0
1
0
1
Φ8
Φ4
Conmutación de Paquetes 51
Propiedades de redes Banyan
Las cuatro topologías de red de Banyan mencionadas poseen dos propiedades: Buddy property:
Si la matriz ji de la etapa i se conecta a las matrices li+1 y mi+1, entonces estas dos matrices están conectadas también a la misma matriz ki en la etapa i
Constrained reachability property: Las 2k matrices alcanzadas en la etapa i+k por la matriz en la
etapa i son también alcanzadas exactamente por 2k-1 matrices de la etapa i Por aplicación de la propiedad anterior etapa a etapa
No todas las redes de Banyan cumplen con estas dos propiedades
Conmutación de Paquetes 52
Ejemplo: Buddy Property
Si la matriz ji de la etapa i se conecta a las matrices li+1 y mi+1, entonces estas dos matrices están conectadas también a la misma matriz ki en la etapa i i = 1; j1 := 1 l2 = 5 ; m2 = 7 l2 & m2 conectada a k1 = 2 i = 1; j1 := 3 l2 = 6 ; m2 = 8 l2 & m2 conectada a k1 = 4
1
2
3
4
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
5
6
7
8
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
9
10
11
12
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
En la etapa 1: Matrices 1+2 son buddies Matrices 3+4 son buddies
Conmutación de Paquetes 53
Ejemplo: Constrained Reachability Property (I)
Las 2k matrices alcanzadas en la etapa i+k por la matriz en la etapa i son también alcanzadas exactamente por 2k-1 matrices de la etapa i i=1; k=2; Matriz 1: puede alcanzar las matrices 9, 10, 11, 12
2k-1= 3 matrices pueden alcanzarles (2, 3, y 4)
1
2
3
4
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
5
6
7
8
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
9
10
11
12
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
Conmutación de Paquetes 54
Ejemplo: Constrained Reachability Property (II)
Ejemplo: Φ16
i=1; k=2 Matriz A: puede alcanzar
las matrices B, C, D, E 2k-1= 3 matrices pueden
alcanzar B, C, D, E
X, Y, y Z 0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
D
E
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
B
C
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
X
Y
A
Z
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
Conmutación de Paquetes 55
Bloqueo en Redes Banyan
En general, se puede producir bloqueo Definimos ‘combinatorial power’ CP de una red como:
CP = |PBanyan| / |Pcrossbar|
Crossbar: sin bloqueo (puede realizar todas las permutaciones) N! Empleamos la aproximación de Stirling para el factorial:
Si N es grande:
Por tanto:
La probabilidad de bloqueo en una red de Banyan se incrementa con N
N N N Banyan N nº de estados |P = = | = 2 log
2 2
Conmutación de Paquetes 56
Importancia de la redes Banyan
Factores clave: Capacidad de autoenrutamiento
El mismo path descriptor para todas las entradas permite ir a la misma salida
Cada etapa considera solo un bit para el enrutamiento del paquete
Procesamiento distribuido de paquetes Independientemente de cada etapa
“compensa” la alta probabilidad de bloqueo
Conmutación de Paquetes 57
Ejemplo de autoenrutamiento en redes Banyan
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0000 0001 0010 0011 0100 0101
0110 0111
1000 1001 1010 1011 1100 1101
1110 1111
0000 0001 0010 0011 0100 0101
0110 0111
1000 1001 1010 1011 1100 1101
1110 1111
1001
1001 1001 1001 1001 :
Paquete destinado a la salida 1001
Conmutación de Paquetes 58
Topologías de Red Delta Banyan
Conmutación de Paquetes 59
Inciso: Permutaciones típicas (1)
an-1 an-2.... a1 a0
? 0101
0000
1111
0000
1111
El patrón de interconexión mediante enlaces entre etapas (y a la entrada y a la salida) define una permutación fija.
Conmutación de Paquetes 60
Permutaciones típicas (2)
j: permutación identidad: j(an-1 .... a0 ) = an-1 .... a0 h-shuffle:
σ h (an-1 .... a0) = an-1 ... a h+1 ah-1 .... a0ah
( 0 < = h <= n-1 ) h-unshuffle: σ h-1 (an-1 .... a0) = an-1 ... a h+1 a0ah-1 .... a1ah
( 0 < = h <= n-1 )
Conmutación de Paquetes 61
Permutaciones típicas (3)
Source: A. Pattavina, “Switching Theory, architecture and performance ....”
(h-shuffle) (butterfly)
σ o-1 = σ o = β0 = j
Conmutación de Paquetes 62
Permutaciones típicas (4)
Bit-switch:
δ (an-1 .... a0) = a1 a2 ....... an-1a0
bit reversal: ρ (an-1 .... a0) = a0 a1 ... an-2 an-1
Conmutación de Paquetes 63
Permutaciones típicas (5)
Source: A. Pattavina, „Switching Theory, architecture and performance ....”
(bit-switch) (bit-reversal)
Conmutación de Paquetes 64
Source: A. Pattavina, „Switching Theory, architecture and performance ....”
Conmutación de Paquetes 65
REDES DE ORDENAMIENTO Parte 4 b)
Conmutación de Paquetes 66
Redes de ordenamiento
Redes Hardware capaces de ordenar un conjunto de elementos
Ordenamiento = comparar e intercambiar (cambio condicional de elementos)
Crear redes sin bloqueo con autoenrutamiento ¿cómo? poner una red de ordenamiento antes de la red de
Banyan para evitar posibilidades de bloqueo
Batcher, 1969: Empleo de bloques pequeños que permitan crear grandes
redes de ordenamiento recursivamente: Merging networks
Conmutación de Paquetes 67
Redes de Fusión (Merging Networks)
Nos centraremos en “bitonic merging sorting” Numero constante de comparaciones por elemento
El mismo numero de matrices en cada etapa Longitud constante de un camino a través de la red Importante en redes de alta velocidad
Posibilidad de introducir un alto grado de paralelización
Red de tamaño N Capaz de fusionar/ordenar dos secuencias ya ordenadas de
tamaño N/2 en una secuencia ordenada de tamaño N Existen dos algoritmos básicos de funcionamiento:
Odd-even merging Bitonic merging
Conmutación de Paquetes 68
Definición de redes de fusión Bitónica
Secuencia Bitónica: Una secuencia a0, a1,..., aN-1 es bitónica si existe un
índice j (0 ≤ j ≤ N-1) de modo que las subsecuencias a0,..., aj y aj+1,..., aN-1 son una monotónicamente creciente y la otra monotónicamente decreciente
Ejemplos:
0, 3, 4, 5, 8, 7, 2, 1 j = 4
8, 6, 5, 4, 3, 1, 0, 2 j = 6
Conmutación de Paquetes 69
Tipos de secuencias Bitónicas
Secuencia Bitónica Circular: Obtenida mediante el desplazamiento circular de k
posiciones (k ∈ [0,N-1]) Ejemplos:
3, 5, 8, 7, 4, 0, 1, 2 k = 2 1, 2, 3, 5, 8, 7, 4, 0 bitonic (j = 4)
Secuencia Bitónica Balanceada: a0 ≤ a1 ≤ ... ≤ aN/2 - 1 y aN/2 ≥ aN/2 + 1 ≥ ... ≥ aN-1 o: a0 ≥ a1 ≥ ... ≥ aN/2 - 1 y aN/2 ≤ aN/2 + 1 ≤ ... ≤ aN-1
Conmutación de Paquetes 70
Construcción red ordenación tipo fusión Bitónica
Construcción de un fusor bitónico NxN (MN) de manera recursiva a partir de fusores bitónicos de ordenación N/2xN/2
Fusor Bitónico
MN/2
Fusor Bitónico
MN/2
c0 c1
cN/2-2 cN/2-1
cN/2 cN/2+1
cN-2 cN-1
• • • • • •
d0 d1
dN/2-2 dN/2-1
• • • • • •
a0 a1
aN/2-2 aN/2-1
aN/2 aN/2+1
aN-2 aN-1
• • • • • •
L H
L H
L H
L H
e0 e1
eN/2-2 eN/2-1
EGS EGS
Conmutación de Paquetes 71
Fusor de ordenación Bitonico: Ejemplo M16 (N=16)
M8
L H
L H
c14 c15
c12 c13
L H
L H
L H
L H
c10 c11
c8 c9
L H
L H
L H
L H
c6 c7
c4 c5
L H
L H
L H
L H
c2 c3
c0 c1
L H
L H
M4
L H
L H
L H
L H
M4
M4
M4
L H
L H
L H
L H
M8
L H
L H
L H
L H
L H
L H
L H
L H
b6 b7
b4 b5
b2 b3
b0 b1
a6 a7
a4 a5
a2 a3
a0 a1
M2
Conmutación de Paquetes 72
Redes de fusion Bitónica: Ejemplo numérico
M8
L H
L H
c6 = 7 c7 = 8
c4 = 5 c5 = 6
L H
L H
L H
L H
c2 = 3 c3 = 4
c0 = 0 c1 = 1
L H
L H
M4
M4 L H
L H
L H
L H
4 = c6 1 = c7
7 = c4 6 = c5
5 = c2 8 = c3
0 = c0 3 = c1
0 7
3 6
4 5
1 8
BITONICO
0 4
1 3
5 7
6 8
Conmutación de Paquetes 73
Características Fusor de ordenación Bitónico
Topología: la misma que la Banyan n-cube Complejidad:
Numero de etapas:
s[MN] = log2N
Numero de Matrices:
S[MN] = N/2 * log2N
Como para una red Banyan
Conmutación de Paquetes 74
Redes de ordenamiento
Emplearemos el algoritmo sort-by-merging para crear redes de ordenamiento Procedente de las redes de fusión analizadas anteriormente
Algoritmo: Paso 1: Los elementos a ordenar se toman de dos en dos para
formar N/2 secuencias de longitud 2 Paso 2: estas secuencias se toman de nuevo de dos en dos y
fusionan para generar N/4 secuencias de longitud 4 ... Sucesivamente hasta llegar a dos secuencias de longitud
N/2 que fusionan en una secuencia de longitud N (paso n = log2N)
Conmutación de Paquetes 75
Redes de ordenamiento: Vista esquemática
Batcher networks (basado en fusores bitónicos)
2x2 0 1
2x2
2x2
2x2 N-2 N-1
• • •
• • •
• • •
• • •
Bitonic merger
MN/2
Bitonic merger
MN/2
MN/4
MN/4
MN/4
MN/4
Bitonic merger
MN
0
N-1
1 n-2 n-1 n = log2N • • •
• • • • • •
• • •
• • •
• • •
Conmutación de Paquetes 76
Ejemplo red ordenamiento Batcher
Construida recursivamente Tener cuidado con el orden de ordenamiento de
cada red de fusión
Orden creciente / Orden decreciente
M8
L H
L H
L H
L H
L H
L H
L H
L H
M4
M4 L H
L H
L H
L H
H L
H L
H L
H L
M2
L H
L H
L H
L H
M4
L H
H L
L H
H L
Conmutación de Paquetes 77
Redes de ordenamiento: Características (I)
Número de etapas sN: log2N etapas de redes de fusión (fusores)
Cada red de fusión: log2N etapas
1ª etapa de fusión : fusores M2 1 etapa
2ª etapa de fusión : fusores M4 2 etapas
...
log2N etapa de fusión : fusores MN log2N etapas
sumamos:
Todos los caminos desde la entrada a la salida cruzan sN matrices
Conmutación de Paquetes 78
Redes de ordenamiento: Características (II)
Numero de Matrices SN: Cada etapa tiene N/2 matrices Por tanto:
Tiempo de ordenamiento: tD: tiempo de transmisión de cada unidad de datos τ: latencia de una etapa de ordenamiento T: tiempo requerido para ordenar N unidades de datos de tamaño fijo
Coste: Una matriz 2x2: C = 4
Conmutación de Paquetes 79
Referencias
A. Pattavina, “Switching theory”, Wiley 1998 Capítulo 2