Download Conectividad

Arquitecturas Paralelas
Curso 15/16
Horas
1 INTRODUCCIÓN
5
2 CONECTIVIDAD
6
3 MÁQUINAS MIMD
6
4 MÁQUINAS SIMD y SIMT
6
5 MULTITHREADING
2
arqPar
Temario
2 CONECTIVIDAD
1 Introducción
Conectividad-2
“Designing Network On-Chip Architectures …”
José Flich y …- 2011 [Capítulos 1 y 4]
“Principles and Practices of Interconnection ...”
William James Dally y … - 2004 [Cap: 1,2,3,22]
2 Conceptos
1 Clasificación de las redes
2 Caracterización por Grafos
3 Perfiles de comunicación
3 Redes de medio de transmisión compartido (Buses)
4 Redes directas (estáticas )
1 Encaminamiento
2 Array lineal, anillo, ..., hipercubo
5 Redes indirectas (dinámicas)
1 Crossbar, redes multietapa ()
Introducción
arqPar
Conectividad-3
QUEREMOS MÁS VELOCIDAD:
A menor Grano, mayor Grado
TAREA
µP1
µP2
µP4
µP3
µP5
! AUMENTAN LAS NECESIDADES DE COMUNICACIÓN !
Introducción
arqPar
Conectividad-4
Comunicación Hw <===> Comunicación Sw
Memoria Común (Load/Store)
Comunicar µPi y Memoria
µP1
µP2
µPi
µPn
RED
M1
Mj
Paso Mensajes (Send/Receive)
Comunicar Pi con Pj
P1
P2
Pi
RED
Mk
Es muy importante la Latencia y el Ancho de banda
Pn
arqPar
Introducción
Conectividad-5
http://www.euroben.nl/reports/overview13.pdf
¿Consumo?
Coste
*
50
Gigabit Ethernet
0,1
29..120
¡ LA RED TIENE UNA IMPORTANCIA VITAL !
arqPar
Introducción
Conectividad-6
2005: 30% consumo energía dinámica del chip y subiendo
2010: 2,2 Km/cm2 de cables dentro de un MPSOC
¡ LA RED TIENE UNA IMPORTANCIA VITAL !
Introducción
arqPar
Conectividad-7
Sistema
Placa
ChipMulticore
LAN
WAN
Introducción
arqPar
Conectividad-8
Sistema
27 nodos
www.sicortex.com SC5832
Placa
Chip
6
núcleos
36 placas
arqPar
Introducción
Conectividad-9
72 núcleos 96GB 100GF => 19.000€
27/Mayo/2009: Quiebra
arqPar
Introducción
Tom Willis Sep/2007
Intel Connects Cables
IBM
Sequoia
#2 Nov/12
1.572.864
nodos
Conectividad-10
Introducción
arqPar
• LAN/WAN Internet
Conectividad-11
• Multiprocesadores …
Millones de nodos
Cientos .. Miles
# Nodos dinámico
Fijo
Enlaces largos
Cortos
Red irregular
Regular
Latencia alta
Baja
NOC’s
No tan regular
• Defectos  Tolerancia a fallos
• Áreas con frec. Reloj distintas
arqPar
Conceptos
Conectividad-12
• CLASIFICACIÓN DE LAS REDES
– MEDIO DE TRANSMISIÓN COMPARTIDO
– DIRECTAS vs INDIRECTAS
– TOTAL vs PARCIALMENTE CONECTADAS
• CARACTERIZACIÓN POR GRAFOS
– GRADO Y DIÁMETRO
• PERFILES DE COMUNICACIÓN
– 1 => 1; N => N; 1 => N; N => 1
Clasificación de las Redes
arqPar
Conectividad-13
• Medio de Transmisión Compartido: Ponerse de acuerdo
en su uso (maestro/esclavo, …)
Redes locales
Ethernet
Redes inalámbricas
µP1
Buses (Backplane)
µP2
M1
Token
Ring
µPi
Mj
µPn
Mk
• Síncronos vs asíncronos
• Multiplexados
• Arbitraje del bus
Clasificación de las Redes
arqPar
Conectividad-14
• Redes directas: Conexiones fijas entre los elementos
(Pi, Pj) “invariables durante la ejecución”
P1
P2
• Acoplamiento débil
• Amplio uso en multicomputadores
P4
P3
• Los propios Nodos encaminan
• Los caminos del origen al
destino pueden ser distintos
Clasificación de las Redes
arqPar
Conectividad-15
• Redes indirectas: Conexiones varían entre los elementos
(µPi, Mj) “variables durante la ejecución”
µP1
µP2
µPi
µPn
RED
M1
Mj
Mk
Red Telefónica
• Acoplamiento fuerte
• Amplio uso en multiprocesadores
• Encamina la propia red
Clasificación de las Redes
arqPar
• Totalmente conectadas:
“Cada elemento tiene conexión
directa con los demás”
Conectividad-16
• Parcialmente conectadas:
¡ conexas !
Latencia mínima (Lm)
Mayor latencia (2Lm)
Alto coste O(n2)
Menor coste O(n)
Encaminar más
complejo
No escalable
• Jerarquizadas: Aislar tráfico por “localidades”
Caracterización por Grafos
arqPar
Conectividad-17
Nodos => µP y/o Bancos de Memoria
Aristas => Enlaces de comunicación
• Grado de un nodo: Líneas incidentes (Si unidireccionales Ge + Gs)
4
2
C
A1
B
D2
E3
• Relacionado con el número de puertos E/S
y, por lo tanto, con el coste
• Deseable constante y pequeño
• Grado de la red: El del nodo con mayor grado (4)
• Deseable regularidad
• Compromiso en el Grado
Más conectividad => Menor latencia
Mayor coste
Menor conectividad => Más latencia
Menor coste
Caracterización por Grafos
arqPar
Conectividad-18
• Diámetro de la red: Camino más distante de entre los mínimos que
unen a dos nodos cualesquiera.
• Métrica => Número de saltos => 2
¿1, 2, 3, ......?
1
2
¿5? => 2, 5, 4, 8, 7, 6
4 => 2, 5, 4, 3, 6 más corto
3
4
5
• Relación directa con la latencia
6
7
8
9
Perfiles de Comunicación
arqPar
Conectividad-19
• Enlaces de comunicación establecidos concurrentemente.
1 => 1
Ventanilla única
N => N
Varias Ventanillas
N => 1
Reducción
Bus Común
1 => N
T.V. News
Difusión, Broadcast, Multicast
Máquinas CRCW
arqPar
Redes Medio Compartido (Bus I)
µP1
µP2
µPi
µPn
$
$
$
$
M1
Mj
Mk
Conectividad-20
¿Cuántos Pi podré instalar?
Pentium 4 a 3,8GHz
Bus de 64 bits y 800MHz
¿Un único Pi satura el Bus?
$
¡ Cachés !
 98% Hit
µPn
¡ Algunos problemas !
colisiones
µP2
µP1
Fallo
costoso
¿ Niveles cache ?
arqPar
Redes Medio Compartido (Bus II) Conectividad-21
• ¿ Cuánto hit en cache “ld” ?
Benchmark
%Hit
16K L1D 88,3
256K L2 65,2
4M
L3 22,7
L* 98,0
L1I 32K => 99,5%
Simulación con:
• PTLsim/X arquitectura tipo x86-64
• L1D = 16KB [128 conjuntos, 4 vías]
• SPEC CPU2006
• 400 millones de instrucciones simuladas
Benchmark
arqPar
Redes Medio Compartido (Bus III) Conectividad-22
µP1
µP2
µPi
µPn
L
L
L
L
Shared Bus
M1
Mj
L2 cache
controler
Shared L2 cache
Mk
Shared Bus
L3 cache
controler
Shared L3 cache
¿ Soluciones ?
arqPar
Redes Medio Compartido (Bus IV) Conectividad-23
• Bus pipelining
Write
Read
Pedir bus
Arbitrar
Dar bus
Usar bus
1
2
3
4
5
AR ARB AG RQ ACK
1
2
3
4
AR ARB AG RQ
5
6
P RPLY
¿Cuántos ciclos 2W y 4R?
Con pipeline mejor
read 1
write 2
write 3
read 4
read 5
read 6
bus ocupado
1
2
3
4
5
6
7
8 9 10 11
AR ARB AG RQ P RPL
AR ARB AG Stall Stall RQ ACK
AR ARB Stall Stall AG Stall RQ ACK
AR Stall Stall ARB Stall AG Stall RQ
AR Stall ARB Stall AG
AR Stall ARB
?
12 13
14
15
P RPL
RQ P RPL
AG Stall Stall RQ
16
17
P RPL
arqPar
Redes Medio Compartido (Bus V) Conectividad-24
• Split transaction: Pipelining + Dividir la transacción en dos
1
read
resp
write
ack
write
ack
read
resp
read
resp
read
resp
1
1
2
2
3
3
4
4
5
5
6
6
1
2
RqA
2
3
4
5
6
7
8
9
10
11
12 13
14
15
16
17
AR ARB AG RQ
AR ARB AG RPL
AR ARB AG RQ
¿ Mejora ?
AR ARB AG ACK
AR ARB AG RQ
AR ARB AG ACK
AR ARB AG RQ
AR ARB AG RPL
AR ARB Stall Stall Stall Stall AG RQ
AR ARB AG RPL
AR ARB Stall Stall Stall Stall AG RQ
AR ARB AG RPL
3
4
5
6
7
8 9
RpA
RqB
Transacciones
variables: 1..6 ciclos
RqA
RpA
RqB
10
11
12 13
14
RpB
RqC
RpC
8 peticiones pendientes en SGI
RpB
RqC
RpC
112 peticiones pendientes en SUN E 6000
arqPar
Redes Medio Compartido (Bus VI) Conectividad-25
• Modo ráfaga (Burst): Transacciones largas (línea de caché)
1
2
3
4
5
6
7
8 9 10 11 12 13 14
Arb
Arb
Arb
Arb
Cmd Dir Dato Cmd Dir Dato Cmd Dir Dato Cmd Dir Dato
Normal
Arb
Cmd Dir Dato Dato Dato Dato
¿ Inconveniente ?
Ráfaga
arbitraje
mensaje A
mensaje B
1
2
3
4
5
6
7
8 9 10 11 12 13 14 15
GrA
GrB
ReA
Cmd Dir Dato Dato Dato Dato
Eti Dato Dato Dato Dato
Cmd Dir Dato
Mensaje más
prioritario
Mensaje
continuado
arqPar
Redes Medio Compartido (Bus VII) Conectividad-26
• Buses jerárquicos
• Buses múltiples
Concluyendo
Cachés (L1, L2 y L3)
Pipelining
Split Transaction
Modo ráfaga
Buses Jerárquicos
Buses Múltiples
Muy costoso + 32µP
Difusión
Serialización
Frecuencia
Secuencial
arqPar
Redes Medio Compartido (Bus VIII) Conectividad-27
• ¿BUSES NO?
• - Ancho de banda
• + Consumo  + Capacitancia
• + Latencia:
 Señal se propaga más lenta
 Líneas más largas
 El arbitraje retrasa
• ¿ Tolerancia a fallos ?
arqPar
Redes Medio Compartido (Bus VIII) Conectividad-28
• Evolución FSB Intel
arqPar
Redes directas
Conectividad-29
Generalidades
Encaminamiento
Menor diámetro aumentando el grado
• Array lineal
• Anillo simple y de grado “n”
• Conectividad total
Compromiso grado vs diámetro y muchos nodos
• Árbol, Fat Tree y Estrella
• Mallas, Toroides y WK-rec
• Hipercubo con y sin ciclo
Tabla de parámetros
arqPar
Redes directas (Generalidades)
Conectividad-30
MultiC más integrado
P
M
P
IC
M
De otros
nodos
A otros
nodos
IC
Switch
Pn
Red con enlaces directos entre Pi
IC
P
L2
• Buffers
• Arbitraje
• Encamina.
M
Nodos => PC’s o similares
Ejemplos: Alpha 21364, SiCortex, Intel Core i7 y SCC
arqPar
Redes directas (P 21364)
Conectividad-31
arqPar
Redes directas ( Toro2D 21364 )
.. 10GBseg
15nseg Lat
Conectividad-32
.. 128 nodos [8x16]
.. 4 TB MP
12 diámetro
arqPar
Redes directas (P SiCortex)
Conectividad-33
2007
500MHz
2GBseg
1µseg Lat
www.sicortex.com
arqPar
Redes directas (P SiCortex)
Kautz Graph
Conectividad-34
Redes directas (Intel Core i7…)
arqPar
Conectividad-35
2008
19,2..25,6 GBseg
www.intel.com/technology/quickpath/introduction.pdf
arqPar
Redes directas (Intel Core i7…)
Conectividad-36
arqPar
Redes directas (Intel Xeon E5…)
Conectividad-37
2012
arqPar
Redes directas (Intel SCC …)
Conectividad-38
http://techresearch.intel.com/spaw2/uploads/files/SCC_Platform_Overview.pdf
• Mayo 2010: Intel lanza de forma selectiva el SCC [prototipo]
48 IA-32
núcleos
64 GBseg
Memoria común sin coherencia  Sw
arqPar
Redes directas (Intel SCC …)
Conectividad-39
• Nov 2012: Intel lanza el coprocesador Xeon Phi (60/61 núcleos)
70 GBseg
arqPar
Redes directas (Epiphany-16 …)
Conectividad-40
• Jul 2014: Sale a la venta masiva la placa “Parallella Epiphany-16”
onChip Write
Network
8B / ciclo
38,4Gbps
4,8Gbps
2,4Gbps
offChip Write
Network
1R / 8 ciclos
1B / ciclo
Read Request
Network
arqPar
Redes directas (Epiphany-16 …)
Conectividad-41
• Jul 2014: Sale a la venta masiva la placa “Parallella Epiphany-16”
arqPar
Encaminamiento (Modos)
Conectividad-42
• Mecanismo Hw/Sw para que la información llegue del origen al
destino.
Hay que distinguir entre:
Algoritmo:
Elección del camino y gestión de conflictos
Técnica:
Modo de propagar la información
Conmutación
de paquetes
6
1
2
3
4
5
7
8
9
Redes directas
Conmutación
de circuitos
Redes indirectas
arqPar
Encaminamiento (Algoritmo)
8x8 = 64 nodos
Diámetro = 7+7=14
Numerar nodo 0..63
0,0
0,2
0,3
0,4
0,5
0,6
0,7
fila col
0..7 0..7
• Dinámico: A[2,3] => B[5,1]
E datos L 5,1
• En origen: C[3,4] => D[1,6]
,N,N,E,E
1,0
D
2,0
A
3,0
Algo: MovCol+MovFila
E datos L
0,1
Conectividad-43
1,6
C
4,0
5,0
B
6,0
7,0
E datos L
,N,N,E
1,6
N[00], E[01], S[10], O[11]
SiCortex, Intel QuickPath, Epiphany …
arqPar
Encaminamiento (Algoritmo)
Conectividad-44
Arbitraje Round Robin
Broadcast
Epiphany-III
32
Dir
6
fila
64
Dato
6
col
8
Ctrl
20
dirMemLocal
arqPar
Encaminamiento (wormhole)
Conectividad-45
• En conmutación de paquetes veremos dos técnicas:
Almacenamiento y reenvío
Origen
210
Buffer de
paquete
Destino
210
Los mensajes se
dividen en paquetes
(64..1024bits) y se
envían paquete a
paquete
Elevada latencia (3*Tiempo trans. Paquete “Ttp”)
“Wormhole”
Origen
210
Buffer de
flit
210
Destino
10
0
Mejora la latencia (2*Tiempo trans. Flit + Ttp)
Los paquetes se
dividen en flits
(2..64bits) y se
envían flit a flit
¿Similar a
IP/ATM
MPLS?
arqPar
Encaminamiento (wormhole)
8
64
8
Header
Payload
CRC
Flit
Conectividad-46
Phit
20 | 10 | 5
arqPar
Encaminamiento (ejemplo)
Conectividad-47
Almacena y
Reenvío
Latencia
Toro2D 8*16 Alpha 21364
Diámetro = 12
Flit = 39 b Paquete = 702b
Ancho Banda = 3,2Gb*seg
Tflit = 12,1875nseg
Tpaq = 219,375nseg
AlmaReen => 2.632,5 nseg
Wormhole => 353,4 nseg
Wormhole
Distancia
+ 7 veces
mejor
arqPar
Encaminamiento (Interbloqueo)
Conectividad-48
C
D
A
B
D
D
C
D
B
C
¡ Interbloqueo !
C
D
B
A
B
B
A
C
A
A
arqPar
D
Encaminamiento (Canales virtuales) Conectividad-49
A
D
A
B
D
A
B
Una forma de
evitar el
interbloqueo
arqPar
Redes directas (array, anillo)
Conectividad-50
• Grado, diámetro, escalable, …
0
ARRAY LINEAL
1
ANILLO (DE GRADO 2)
0
2
3
4
0
2
7
6
3
4
6
7
ANILLO (DE GRADO ‘n’ 3)
1
5
5
1
2
7
6
3
5
4
arqPar
Redes directas (array, anillo)
Conectividad-51
“Navigation in a small world” – Jon M. Kleinberg
Nature – 24 Agosto 2000
Redes directas (anillo de grado “n”)
arqPar
Conectividad-52
N=8 n=3
Salto 2
1
Salto 3
1
1
1
2
2
2
3
d = 3, d = 1,71
Salto 4
1
1
2
2
3
1
2
d = 3, d = 1,71
1
2
2
2
2
1
d = 2, d = 1,57
Redes directas (anillo de grado “n”)
arqPar
Conectividad-53
N = 16 n = 3
Salto 2
6
d = 6, d = 3,2
Salto 3
5
d = 5, d = 2,67
Salto 5 iguala y 7 y 8 empeoran
Salto 4
4
d = 4, d = 2,27
Redes directas (anillo de grado “n”)
arqPar
Conectividad-54
N = 16 n = 4
Salto 3
4
d = 4, d = 2,13
Salto 4
3
d = 3, d = 2
¿Cómo podría ser N=32 y n=5?
Salto 5
4
d = 4, d = 2,13
Redes directas (anillo de grado “n”)
arqPar
Conectividad-55
N = 32 n = 5
4
¿ Escalable ?
4
d = 4, d = ???
arqPar
Redes directas (conexión total)
• Grado, diámetro, escalable, …
0
1
2
7
6
3
5
4
Conectividad-56
arqPar
Redes directas (Gráfica)
Conectividad-57
70
Diámetro
60
50
Array
Anillo
Anillo "n"
Total
40
30
20
10
Moverse por aquí
con menor grado
0
0
20
40
# Nodos
60
arqPar
Redes directas (árbol, …)
• Grado, diámetro, escalable, …
Conectividad-58
ÁRBOL BINARIO
EQUILIBRADO
“Fat Tree”
ÁRBOL BINARIO
K=1
2
2
4
4
2
K=2
2
K=3
K=4
• Cuello de botella [tráfico aleatorio]
¿Cómo encaminar A  B?
ESTRELLA
Redes directas (árbol, …)
arqPar
• Fat Tree ¡Indirectas!
E
8
A
32
F
8
B
16
Conectividad-59
C
D
¿Más nodos más niveles? => más latencia
arqPar
Redes directas (árbol, …)
• Dragonfly “high radix routers”
local
channels
36, 100 .. 648
40,56,100Gb/s
Conectividad-60
arqPar
Redes directas (malla)
Conectividad-61
• Grado, diámetro, escalable, …
MALLA 3D
MALLA 2D
K=3
K=1
K=2
O(1,1,1)
D(3,3,3)
O(2,2,1)
D(3,3,2)
• Encaminamiento ordenado por direcciones
• M3D 102410*10*10 => D=27
• ¿Escalabilidad cuadrática o cúbica?
¡Colisión!
¿ Interbloqueos ?
¿ Cuello de botella?
arqPar
Redes directas (malla3D)
Conectividad-62
• ¿Cuello de botella tráfico NN?
18
18
18
18
18
18
18
18
18
18
18
18
¡ 18 msj por todos
los enlaces en cada
sentido !
arqPar
Redes directas (toroide)
• Grado, diámetro, escalable, …
TOROIDES (2D y 3D)
Cables largos vs cortos
Muchos cruces
K=1
K=2
• T3D 102410*10*10 => D=15
• ¡ Anillo embebido !
Conectividad-63
arqPar
Redes directas (toroide)
Conectividad-64
• Todos los cables de igual longitud  Toroide plegado
12
0
1
2
3
4
5
6
7
8
9
10
11
13
15
14
0
1
3
8
2
9
11
12
13
14
15
10
4
5
7
6
arqPar
Redes directas (WK-Recursivo)
?
• Grado, diámetro, escalable, …
Conectividad-65
Grado 3
(3,1)
1
Grado 4
(4,1)
(3,2)
3
(4,2)
(3,3)
7
(4,3)
¿Grado 5?
arqPar
Redes directas (WK-Recursivo)
(5,1)
Conectividad-66
(5,2)
• WK (4,5) 1024 => D=31
Diámetro
1
3
7
15
31
Grado 3
3
9
27
81
243
Grado 4
4
16
64
256
1024
Grado 5
5
25
125
625
3125
arqPar
Redes directas (WK-Recursivo)
Conectividad-67
• ¿Cuello de botella tráfico NN?
5
5
16
5
9
5
5
9
9
5
9
9
16
16
16
16
9
5
5
9
9
5
9
9
9
5
9
16
5
5
arqPar
Redes directas (hipercubo)
Conectividad-68
HIPERCUBO ‘N=2k’ nodos, ‘k’ dimensiones = log2 N
Dim3
Dim1
Dim2
Diámetro = log2 N
Grado = log2 N
Fácil encaminar
Dim4
• Escalable a costa de demasiado grado
• Topología cada vez menos utilizada
arqPar
Redes directas (hipercubo)
Conectividad-69
Encaminamiento en HIPERCUBO (Sea N=16)
3
2
1.
Numerar nodos en binario. Nodos
adyacentes difieren en un bit (el
asociado a la dirección que les une)
2.
Enviar mensaje por el enlace
asociado a la menor dirección
donde no coinciden bit del nodo
actual y bit del nodo destino
4321
0110
1
4
0111
1111
0010
0011
1010
1000
0100
0000
Nodo actual
0101
¿ Realizar ORX ?
0111 ORX 1010 = 1101
¿Caminos distintos?
0001
0111
0110
0010
1010
Nodo destino 1010
1010
1010
1010
arqPar
Redes directas (hipercubo con ciclos)
Conectividad-70
• Grado, diámetro, escalable, …
K=3
1
0
HIPERCUBO CON CICLOS
2
3
1
1
2
3
2
3
4
4
2
¿ Diámetro ?
3
3
4
4
4
3
4
5
5
6
5
arqPar
Redes directas (Grafo de Kautz)
Conectividad-71
arqPar
Redes directas (Un ejemplo)
• ¿Cómo conectar unos 1024 nodos?
Topología Diámetro Grado
Array lineal
1023
2*
Anillo2
512
2
Anillo10
9
10
Total
1
1023
Árbol
M2D 32*32
WK 4ary 5rec
18
62
31
3*
4*
4*
M3D 10*10*10
T3D 10*10*10
27
15
6*
6
Hipercubo 10
896 N HiperCiclo 7
972 N Grafo Kautz
10
16
6
10
3
3
Conectividad-72
Redes directas (Tabla de Parámetros) Conectividad-73
arqPar
Topología
Nº de nodos
Grado
Diámetro
Array lineal
N
2
N-1
Anillo
N
2
N/2
Anillo de grado ‘n’
N
n=log2N
n-1
Árbol binario
2K-1
3
2*(K-1)
Árbol binario equilibrado
2K-1
2K
2*(K-1)
Estrella
N
N-1
2
Malla
nK
2*K
K*(n-1)
Toroide
nK
2*K
K*  n/2 
Hipercubo
2K
K
K
K*2K
3
2*K - 1 +  K/2 
Hipercubo con ciclos
arqPar
Perspectiva histórica
Conectividad-74
MIMD
HWANG (1993) IDENTIFICA TRES GENERACIONES:
1983-1987
Hipercubo con Encaminamiento Sw
1988-1992
Malla con Encaminamiento Hw (Sw de grano medio)
1993-1997
µP y comunicaciones en el mismo chip (grano fino)
1983-1987
1988-1992
1993-1997
Multiprocessor systems-on-chips (MPSoCs)
Hoy 4..16 núcleos
¿Se llegará a 400 en 2020?
arqPar
Redes indirectas (Barras cruzadas) Conectividad-75
P1
Perfil N*M
P2
O (N2)
P3
“Crossbar”
Pn
M1
M2
M3
Mm
Funcionalidad de los conmutadores simples:
colisión
Muchas patas
8x8 OnChip
mm2 => 5 núcleos
W => 2 núcleos
difusión
arqPar
Redes indirectas (Multietapa)
crossbar
8*8
• O (64)
• Perfil 8*8
• Latencia 1
Conectividad-76
¿ Reducir O( N2) a costa de … ?
Usar sólo crossbar 2*2
directo
cruce
difusión
colisión

Red de
interconexión
Conjunto de
crossbar 2*2
etapa 1
etapa 2
etapa m
arqPar
Redes indirectas (Red )
Conectividad-77
• Red de interconexión “perfect Suffle”
• Limitado a N = potencia de 2
• Viable: [a,f – b,e – c,h – d,g]
• N=2
• NoViable: [a,f - c,e - …....]
• N=4
a
e
b
f
c
g
d
h
Crossbar  24
Red   16
Redes indirectas (Red )
arqPar
Conectividad-78
• Red de interconexión “perfect Suffle”
• Limitado a N = potencia de 2
Colisión
000
000
001
001
010
011
100
101
001
010
001
00 1
010
01 0
110
111
¿Encaminamiento?
Sea de 001 a 010
010
011
100
101
110
111
Bit igual => directo
¿Mejorable?
Bit distinto => cruce
¿ Latencia
y O( ) ?
Redes indirectas (Red )
arqPar
Conectividad-79
000
000
001
001
010
011
010
011
100
100
101
101
110
111
110
111
¡ Permite difusión !
arqPar
Redes indirectas (Tabla de parámetros) Conectividad-80
Latencia
Complejidad
Conmuta.
Perfil de
Comunicación
Bus
Multietapa Crossbar
Cte
Log2N*cte
cte
N
2 N log2N
N2
11
NN (*)
NN
• BUS
Barato y limitado 2..32
• CROSSBAR
Más caro. Bueno para N moderado
Mayor ancho de banda y fácil encaminar
• MULTIETAPA
Compromiso entre Bus y Crossbar
arqPar
Implantación en el mercado (Oct/2013) Conectividad-81
#NODOS TIPO DE RED SUPERCOMPUTADOR
..N
>50.000
.. 1.152
(96+96)*N
.. 4.096 ..?
.. 98.304
.. 512
.. 1.572.864
256 x 2.048
.. 8.192
.. 4.096
Configurable
Dragonfly
Toro 2y3D
Toro 3D
Toro 3D + Árbol
Toro 6D
Crossbar multidim.
Toro 5D
Variable
Crossbar multidim.
Toro 2D .. ?
Bull systems
Cray Inc. XC30
Cray Inc. XE6/XE6m
Cray Inc. XK7
Eurotech Aurora
Fujitsu PRIMEHPC FX 10
Hitachi SR 16000
IBM BlueGene/Q
IBM eServer p775
NEC SX-9
SGI Altix UV
intercluster
arqPar
Redes en Top500 (Nov/2015)
Conectividad-82
FIN