QUEREMOS MÁS VELOCIDAD:
A menor Grano, mayor Grado
(Gp:) µP1
(Gp:) TAREA
(Gp:) µP2
(Gp:) µP3
(Gp:) µP4
(Gp:) µP5
! AUMENTAN LAS NECESIDADES DE COMUNICACIÓN !
Comunicación Hw < ===> Comunicación Sw
Memoria Común (Load/Store)
Comunicar µPi y Memoria
Paso Mensajes (Send/Receive)
Comunicar Pi con Pj
(Gp:) µP1
(Gp:) µP2
(Gp:) µPi
(Gp:) µPn
(Gp:) R E D
(Gp:) M1
(Gp:) Mj
(Gp:) Mk
(Gp:) P1
(Gp:) P2
(Gp:) Pi
(Gp:) Pn
(Gp:)
R E D
Es muy importante la Latencia y el Ancho de banda
¡ LA RED TIENE UNA IMPORTANCIA VITAL !
http://www.euroben.nl/reports/overview13.pdf
(Gp:) Gigabit Ethernet
(Gp:) 0,1
(Gp:) 29..120
(Gp:) Coste
*
50
¿Consumo?
¡ LA RED TIENE UNA IMPORTANCIA VITAL !
(Gp:) 2005: 30% consumo energía dinámica del chip y subiendo
(Gp:) 2010: 2,2 Km/cm2 de cables dentro de un MPSOC
(Gp:) LAN
(Gp:)
WAN
Sistema
Placa
ChipMulticore
(Gp:) Sistema
(Gp:) Placa
(Gp:) Chip
www.sicortex.com SC5832
(Gp:) 27 nodos
(Gp:) 36 placas
(Gp:) 6
núcleos
72 núcleos 96GB 100GF => 19.000€
27/Mayo/2009: Quiebra
(Gp:) Tom Willis Sep/2007
Intel Connects Cables
(Gp:) IBM Sequoia
#2 Nov/12
1.572.864
nodos
(Gp:) LAN/WAN Internet
(Gp:) Multiprocesadores …
(Gp:) Millones de nodos Cientos .. Miles
# Nodos dinámico Fijo
Enlaces largos Cortos
Red irregular Regular
Latencia alta Baja
CLASIFICACIÓN DE LAS REDES
MEDIO DE TRANSMISIÓN COMPARTIDO
DIRECTAS vs INDIRECTAS
TOTAL vs PARCIALMENTE CONECTADAS
PERFILES DE COMUNICACIÓN
1 => 1; N => N; 1 => N; N => 1
CARACTERIZACIÓN POR GRAFOS
GRADO Y DIÁMETRO
Medio de Transmisión Compartido: Ponerse de acuerdo en su uso (maestro/esclavo, …)
Síncronos vs asíncronos
Multiplexados
Arbitraje del bus
(Gp:) Redes locales
(Gp:) Ethernet
(Gp:) Token Ring
(Gp:) µP2
(Gp:) µPi
(Gp:) µPn
(Gp:) Mj
(Gp:) Mk
(Gp:) Buses (Backplane)
(Gp:) µP1
(Gp:) M1
Redes inalámbricas
Redes directas: Conexiones fijas entre los elementos (Pi, Pj) “invariables durante la ejecución”
(Gp:) P1
(Gp:) P4
(Gp:) P2
(Gp:) P3
Acoplamiento débil
Amplio uso en multicomputadores
Los propios Nodos encaminan
Los caminos del origen al
destino pueden ser distintos
(Gp:) Red Telefónica
Redes indirectas: Conexiones varían entre los elementos (µPi, Mj) “variables durante la ejecución”
Acoplamiento fuerte
Amplio uso en multiprocesadores
Encamina la propia red
(Gp:) µP1
(Gp:) µP2
(Gp:) µPi
(Gp:) µPn
(Gp:) R E D
(Gp:) M1
(Gp:) Mj
(Gp:) Mk
Totalmente conectadas: “Cada elemento tiene conexión directa con los demás”
(Gp:) Parcialmente conectadas:
¡ conexas !
(Gp:) Jerarquizadas: Aislar tráfico por “localidades”
(Gp:) Latencia mínima (Lm)
(Gp:) Alto coste O(n2)
(Gp:) No escalable
(Gp:) Menor coste O(n)
(Gp:) Mayor latencia (2Lm)
(Gp:) Encaminar más
complejo
Nodos => µP y/o Bancos de Memoria
Aristas => Enlaces de comunicación
Grado de un nodo: Líneas incidentes (Si unidireccionales Ge + Gs)
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
(Gp:) Más conectividad => Menor latencia
Mayor coste
(Gp:) Menor conectividad => Más latencia
Menor coste
(Gp:) 1
(Gp:) 2
(Gp:) 3
(Gp:) 4
(Gp:) 2
(Gp:) A
(Gp:) B
(Gp:) C
(Gp:) D
(Gp:) E
Diámetro de la red: Camino más distante de entre los mínimos que unen a dos nodos cualesquiera.
Relación directa con la latencia
(Gp:) ¿1, 2, 3, ……?
Métrica => Número de saltos => 2
(Gp:) 1
(Gp:) 4
(Gp:) 7
(Gp:) 6
(Gp:) 5
(Gp:) 9
(Gp:) 2
(Gp:) 8
(Gp:) 3
(Gp:) ¿5? => 2, 5, 4, 8, 7, 6
(Gp:) 4 => 2, 5, 4, 3, 6 más corto
Enlaces de comunicación establecidos concurrentemente.
(Gp:) 1 => 1
(Gp:) Ventanilla única
(Gp:) Bus Común
(Gp:) N => N
(Gp:) Varias Ventanillas
(Gp:) T.V. News
(Gp:) 1 => N
(Gp:) Difusión, Broadcast, Multicast
(Gp:) Reducción
(Gp:) N => 1
(Gp:) Máquinas CRCW
(Gp:) µP1
(Gp:) M1
(Gp:) Mj
(Gp:) Mk
(Gp:) µP2
(Gp:) µPi
(Gp:) µPn
¿Cuántos Pi podré instalar?
Pentium 4 a 3,8GHz
Bus de 64 bits y 800MHz
¿Un único Pi satura el Bus?
(Gp:) $
(Gp:) $
(Gp:) $
(Gp:) $
(Gp:) $
(Gp:) ¡ Cachés !
(Gp:) µP2
(Gp:) µPn
¡ Algunos problemas !
(Gp:) Fallo costoso
(Gp:) µP1
(Gp:) ? 98% Hit
(Gp:) colisiones
(Gp:) ¿ Niveles cache ?
(Gp:) ¿ Cuánto hit en cache “ld” ?
(Gp:) Simulación con:
PTLsim/X arquitectura tipo x86-64
L1D = 16KB [128 conjuntos, 4 vías]
SPEC CPU2006
400 millones de instrucciones simuladas
(Gp:) Benchmark
(Gp:) Benchmark
(Gp:) L1D
(Gp:) L2
(Gp:) L3
(Gp:) 88,3
(Gp:) 65,2
(Gp:) 22,7
(Gp:) L*
(Gp:) 98,0
(Gp:) %Hit
(Gp:) 16K
(Gp:) 256K
(Gp:) 4M
(Gp:) L1I 32K => 99,5%
(Gp:) µP1
(Gp:) M1
(Gp:) Mj
(Gp:) Mk
(Gp:) µP2
(Gp:) µPi
(Gp:) µPn
(Gp:) L
(Gp:) L
(Gp:) L
(Gp:) L
(Gp:)
Shared L3 cache
(Gp:) L3 cache controler
(Gp:) Shared Bus
(Gp:)
Shared L2 cache
(Gp:) L2 cache controler
(Gp:) Shared Bus
¿ Soluciones ?
Bus pipelining
(Gp:) Pedir bus
Arbitrar
Dar bus
Usar bus
(Gp:) AR
(Gp:) ARB
(Gp:) AG
(Gp:) RQ
(Gp:) ACK
(Gp:) 1 2 3 4 5
(Gp:) AR
(Gp:) ARB
(Gp:) AG
(Gp:) RQ
(Gp:) P
(Gp:) 1 2 3 4 5 6
(Gp:) RPLY
(Gp:) Write
(Gp:) Read
¿Cuántos ciclos 2W y 4R?
(Gp:) read 1
write 2
write 3
read 4
read 5
read 6
bus ocupado
(Gp:) AR
(Gp:) ARB
(Gp:) AG
(Gp:) RQ
(Gp:) RPL
(Gp:) AR
(Gp:) ARB
(Gp:) AG
(Gp:) Stall
(Gp:) P
(Gp:) Stall
(Gp:) RQ
(Gp:) ACK
(Gp:) AR
(Gp:) ARB
(Gp:) Stall
(Gp:) Stall
(Gp:) AG
(Gp:) Stall
(Gp:) RQ
(Gp:) ACK
(Gp:) AR
(Gp:) Stall
(Gp:) Stall
(Gp:) ARB
(Gp:) Stall
(Gp:) AG
(Gp:) Stall
(Gp:) RQ
(Gp:) RPL
(Gp:) P
(Gp:) AR
(Gp:) Stall
(Gp:) ARB
(Gp:) Stall
(Gp:) AG
(Gp:) RQ
(Gp:) RPL
(Gp:) P
(Gp:) AR
(Gp:) Stall
(Gp:) ARB
(Gp:) AG
(Gp:) Stall
(Gp:) Stall
(Gp:) RQ
(Gp:) RPL
(Gp:) P
(Gp:) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
Con pipeline mejor
?
Split transaction: Pipelining + Dividir la transacción en dos
8 peticiones pendientes en SGI
112 peticiones pendientes en SUN E 6000
(Gp:) read 1
resp 1
write 2
ack 2
write 3
ack 3
read 4
resp 4
read 5
resp 5
read 6
resp 6
(Gp:) AR
(Gp:) ARB
(Gp:) AG
(Gp:) RQ
(Gp:) AR
(Gp:) ARB
(Gp:) AG
(Gp:) Stall
(Gp:) Stall
(Gp:) RQ
(Gp:) Stall
(Gp:) Stall
(Gp:) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
(Gp:) RPL
(Gp:) AR
(Gp:) ARB
(Gp:) AG
(Gp:) AR
(Gp:) ARB
(Gp:) AG
(Gp:) RQ
(Gp:) ACK
(Gp:) AR
(Gp:) ARB
(Gp:) AG
(Gp:) AR
(Gp:) ARB
(Gp:) AG
(Gp:) RQ
(Gp:) ACK
(Gp:) AR
(Gp:) ARB
(Gp:) AG
(Gp:) AR
(Gp:) ARB
(Gp:) AG
(Gp:) RQ
(Gp:) RPL
(Gp:) AR
(Gp:) ARB
(Gp:) AG
(Gp:) RPL
(Gp:) AR
(Gp:) ARB
(Gp:) AG
(Gp:) AR
(Gp:) ARB
(Gp:) AG
(Gp:) Stall
(Gp:) Stall
(Gp:) RQ
(Gp:) Stall
(Gp:) Stall
(Gp:) RPL
(Gp:) AR
(Gp:) ARB
(Gp:) AG
(Gp:) RpA
(Gp:) RqA
(Gp:) RqB
(Gp:) RqC
(Gp:) RpB
(Gp:) RpC
¿ Mejora ?
(Gp:) RqA
(Gp:) 1 2 3 4 5 6 7 8 9 10 11 12 13 14
(Gp:) RpA
(Gp:) RqB
(Gp:) RpB
(Gp:) RqC
(Gp:) RpC
(Gp:) Transacciones
variables: 1..6 ciclos
Modo ráfaga (Burst): Transacciones largas (línea de caché)
(Gp:) Normal
(Gp:) Arb
(Gp:) 1 2 3 4 5 6 7 8 9 10 11 12 13 14
(Gp:) Cmd
(Gp:) Dir
(Gp:) Dato
(Gp:) Arb
(Gp:) Cmd
(Gp:) Dir
(Gp:) Dato
(Gp:) Arb
(Gp:) Cmd
(Gp:) Dir
(Gp:) Dato
(Gp:) Arb
(Gp:) Cmd
(Gp:) Dir
(Gp:) Dato
(Gp:) Arb
(Gp:) Cmd
(Gp:) Dir
(Gp:) Dato
(Gp:) Dato
(Gp:) Dato
(Gp:) Dato
(Gp:) Ráfaga
¿ Inconveniente ?
(Gp:) arbitraje
mensaje A
mensaje B
(Gp:) GrA
(Gp:) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
(Gp:) Cmd
(Gp:) Dir
(Gp:) Dato
(Gp:) Dato
(Gp:) Dato
(Gp:) Dato
(Gp:) GrB
(Gp:) Cmd
(Gp:) Dir
(Gp:) Dato
(Gp:) ReA
(Gp:) Eti
(Gp:) Dato
(Gp:) Dato
(Gp:) Dato
(Gp:) Dato
(Gp:) Mensaje más prioritario
(Gp:) Mensaje continuado
Buses jerárquicos
(Gp:) 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
(Gp:) Difusión
Serialización
(Gp:) Frecuencia
Secuencial
(Gp:) Evolución FSB Intel
Menor diámetro aumentando el grado
Compromiso grado vs diámetro y muchos nodos
Tabla de parámetros
Encaminamiento
Generalidades
Array lineal
Anillo simple y de grado “n”
Conectividad total
Árbol, Fat Tree y Estrella
Mallas, Toroides y WK-rec
Hipercubo con y sin ciclo
(Gp:) P
(Gp:) M
(Gp:) IC
(Gp:) Red con enlaces directos entre Pi
(Gp:) P
(Gp:) M
(Gp:) IC
(Gp:) P
(Gp:) M
(Gp:) IC
Nodos => PC’s o similares
(Gp:) Pn
(Gp:) L2
(Gp:) Switch
(Gp:) MultiC más integrado
(Gp:) De otros nodos
(Gp:) A otros nodos
Ejemplos: Alpha 21364, SiCortex, Intel Core i7 y SCC
(Gp:) Buffers
Arbitraje
Encamina.
.. 10GBseg
15nseg Lat
.. 128 nodos [8×16]
.. 4 TB MP
12 diámetro
(Gp:) www.sicortex.com
(Gp:) 500MHz
(Gp:) 2007
2GBseg
1µseg Lat
(Gp:) Kautz Graph
(Gp:) www.intel.com/technology/quickpath/introduction.pdf
(Gp:) 2008
19,2..25,6 GBseg
(Gp:) 2012
Mayo 2010: Intel lanza de forma selectiva el SCC [prototipo]
48 IA-32
núcleos
Memoria común sin coherencia ? Sw
http://techresearch.intel.com/spaw2/uploads/files/SCC_Platform_Overview.pdf
64 GBseg
(Gp:) Nov 2012: Intel lanza el coprocesador Xeon Phi (60/61 núcleos)
70 GBseg
Jul 2014: Sale a la venta masiva la placa “Parallella Epiphany-16”
(Gp:) onChip Write
Network
(Gp:) offChip Write
Network
(Gp:) Read Request
Network
(Gp:) 8B / ciclo
(Gp:) 1B / ciclo
(Gp:) 1R / 8 ciclos
(Gp:) 38,4Gbps
(Gp:) 4,8Gbps
(Gp:) 2,4Gbps
Jul 2014: Sale a la venta masiva la placa “Parallella Epiphany-16”
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
(Gp:) 1
(Gp:) 4
(Gp:) 7
(Gp:) 6
(Gp:) 5
(Gp:) 9
(Gp:) 2
(Gp:) 8
(Gp:) 3
(Gp:) Conmutación de paquetes
(Gp:) Redes directas
(Gp:) Conmutación de circuitos
(Gp:) Redes indirectas
8×8 = 64 nodos
Diámetro = 7+7=14
Numerar nodo 0..63
(Gp:) fila
(Gp:) col
(Gp:) 0..7
(Gp:) 0..7
(Gp:) 0,0
(Gp:) 0,1
(Gp:) 0,2
(Gp:) 0,7
(Gp:) 0,3
(Gp:) 0,4
(Gp:) 0,5
(Gp:) 0,6
(Gp:) 1,0
(Gp:) 2,0
(Gp:) 7,0
(Gp:) 3,0
(Gp:) 4,0
(Gp:) 5,0
(Gp:) 6,0
(Gp:) A
(Gp:) B
(Gp:) Dinámico: A[2,3] => B[5,1]
(Gp:) E
(Gp:) datos
(Gp:) L
(Gp:) 5,1
Algo: MovCol+MovFila
(Gp:) C
(Gp:) D
(Gp:) En origen: C[3,4] => D[1,6]
(Gp:) E
(Gp:) datos
(Gp:) L
(Gp:) 1,6
(Gp:) ,N,N,E,E
(Gp:) E
(Gp:) datos
(Gp:) L
(Gp:) 1,6
(Gp:) ,N,N,E
N[00], E[01], S[10], O[11]
(Gp:) SiCortex, Intel QuickPath, Epiphany …
(Gp:) Epiphany-III
(Gp:) Dir
(Gp:) Dato
(Gp:) Ctrl
(Gp:) 32 64 8
(Gp:) fila
(Gp:) col
(Gp:) dirMemLocal
(Gp:) 6 6 20
Arbitraje Round Robin
Broadcast
En conmutación de paquetes veremos dos técnicas:
(Gp:) Buffer de
paquete
(Gp:) Los mensajes se
dividen en paquetes (64..1024bits) y se envían paquete a paquete
(Gp:) Origen
(Gp:) Almacenamiento y reenvío
(Gp:) Destino
Elevada latencia (3*Tiempo trans. Paquete “Ttp”)
(Gp:) Origen
(Gp:) “Wormhole”
(Gp:) Destino
Mejora la latencia (2*Tiempo trans. Flit + Ttp)
(Gp:) Buffer de
flit
(Gp:) Los paquetes se
dividen en flits (2..64bits) y se envían flit a flit
(Gp:) 2
(Gp:) 1
(Gp:) 0
(Gp:) 0
(Gp:) 0
(Gp:) 0
(Gp:) 1
(Gp:) 1
(Gp:) 0
(Gp:) 1
(Gp:) 2
(Gp:) 2
(Gp:) 0
(Gp:) 1
(Gp:) 2
(Gp:) Header
(Gp:) Payload
(Gp:) CRC
(Gp:) 8
(Gp:) 8
(Gp:) 64
(Gp:) 20 | 10 | 5
(Gp:) Flit
(Gp:) Phit
Distancia
Latencia
Almacena y
Reenvío
(Gp:) Wormhole
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
(Gp:) + 7 veces
mejor
(Gp:) A
(Gp:) B
(Gp:) C
(Gp:) D
(Gp:) D
(Gp:) C
(Gp:) A
(Gp:) B
(Gp:) D
(Gp:) C
(Gp:) A
(Gp:) B
(Gp:) D
(Gp:) C
(Gp:) A
(Gp:) B
(Gp:) D
(Gp:) C
(Gp:) A
(Gp:) B
¡ Interbloqueo !
(Gp:) A
(Gp:) D
(Gp:) B
(Gp:) A
(Gp:) D
(Gp:) B
(Gp:) A
(Gp:) D
Una forma de evitar el interbloqueo
(Gp:) ARRAY LINEAL
(Gp:) 0
(Gp:) 1
(Gp:) 2
(Gp:) 3
(Gp:) 4
(Gp:) 5
(Gp:) 6
(Gp:) 7
(Gp:) ANILLO (DE GRADO 2)
(Gp:) 0
(Gp:) 1
(Gp:) 2
(Gp:) 3
(Gp:) 4
(Gp:) 5
(Gp:) 6
(Gp:) 7
(Gp:) ANILLO (DE GRADO ‘n’ 3)
(Gp:) 0
(Gp:) 1
(Gp:) 2
(Gp:) 3
(Gp:) 4
(Gp:) 5
(Gp:) 6
(Gp:) 7
Grado, diámetro, escalable, …
“Navigation in a small world” – Jon M. Kleinberg
Nature – 24 Agosto 2000
N = 8 n = 3
(Gp:) Salto 3
(Gp:) 1
(Gp:) 1
(Gp:) 1
(Gp:) 2
(Gp:) 2
(Gp:) 2
(Gp:) 3
(Gp:) d = 3, d = 1,71
(Gp:) Salto 2
(Gp:) 1
(Gp:) 1
(Gp:) 1
(Gp:) 3
(Gp:) 2
(Gp:) 2
(Gp:) 2
(Gp:) d = 3, d = 1,71
(Gp:) Salto 4
(Gp:) 1
(Gp:) 2
(Gp:) 1
(Gp:) 1
(Gp:) 2
(Gp:) 2
(Gp:) 2
(Gp:) d = 2, d = 1,57
N = 16 n = 3
(Gp:) Salto 2
(Gp:) d = 6, d = 3,2
(Gp:) 6
(Gp:) Salto 3
(Gp:) 5
(Gp:) d = 5, d = 2,67
(Gp:) Salto 4
(Gp:) 4
(Gp:) d = 4, d = 2,27
Salto 5 iguala y 7 y 8 empeoran
N = 16 n = 4
(Gp:) d = 4, d = 2,13
(Gp:) 4
(Gp:) 3
(Gp:) d = 3, d = 2
(Gp:) Salto 5
(Gp:) 4
(Gp:) d = 4, d = 2,13
¿Cómo podría ser N=32 y n=5?
(Gp:) Salto 3
(Gp:) Salto 4
N = 32 n = 5
(Gp:) d = 4, d = ???
4
¿ Escalable ?
4
(Gp:) 0
(Gp:) 1
(Gp:) 2
(Gp:) 3
(Gp:) 4
(Gp:) 5
(Gp:) 6
(Gp:) 7
Grado, diámetro, escalable, …
(Gp:) Moverse por aquí
con menor grado
(Gp:) K=1
(Gp:) K=2
(Gp:) K=3
(Gp:) K=4
ÁRBOL BINARIO
(Gp:) ÁRBOL BINARIO EQUILIBRADO
“Fat Tree”
(Gp:) 2
(Gp:) 2
(Gp:) 2
(Gp:) 2
(Gp:) 4
(Gp:) 4
Grado, diámetro, escalable, …
Cuello de botella [tráfico aleatorio]
(Gp:) ¿Cómo encaminar A ? B?
(Gp:) ESTRELLA
Fat Tree ¡Indirectas!
¿Más nodos más niveles? => más latencia
(Gp:) 32
(Gp:) 16
(Gp:) 8
(Gp:) 8
Dragonfly “high radix routers”
local channels
(Gp:) 36, 100 .. 648
56Gb/s
(Gp:) K=3
(Gp:) MALLA 3D
MALLA 2D
(Gp:) K=1
(Gp:) K=2
M3D 102410*10*10 => D=27
¿Escalabilidad cuadrática o cúbica?
(Gp:) Encaminamiento ordenado por direcciones
(Gp:) O(1,1,1)
(Gp:) D(3,3,3)
(Gp:) O(2,2,1)
(Gp:) D(3,3,2)
¡Colisión!
¿ Interbloqueos ?
Grado, diámetro, escalable, …
¿ Cuello de botella?
¿Cuello de botella tráfico N?N?
(Gp:) 18
(Gp:) 18
(Gp:) 18
(Gp:) 18
(Gp:) 18
(Gp:) 18
(Gp:) 18
(Gp:) 18
(Gp:) 18
(Gp:) 18
(Gp:) 18
(Gp:) 18
¡ 18 msj por todos los enlaces en cada sentido !
TOROIDES (2D y 3D)
K=1
K=2
T3D 102410*10*10 => D=15
¡ Anillo embebido !
Grado, diámetro, escalable, …
Cables largos vs cortos
Muchos cruces
Grado, diámetro, escalable, …
¿Grado 5?
(Gp:) Grado 3
(Gp:) (3,1)
(3,2)
(Gp:) (3,3)
(Gp:) Grado 4
(Gp:) (4,1)
(Gp:) (4,2)
(Gp:) (4,3)
(5,1)
(5,2)
WK (4,5) 1024 => D=31
¿Cuello de botella tráfico N?N?
(Gp:) 5
(Gp:) 5
(Gp:) 5
(Gp:) 5
(Gp:) 5
(Gp:) 5
(Gp:) 5
(Gp:) 5
(Gp:) 5
(Gp:) 5
(Gp:) 5
(Gp:) 5
(Gp:) 9
(Gp:) 9
(Gp:) 9
(Gp:) 9
(Gp:) 9
(Gp:) 9
(Gp:) 9
(Gp:) 9
(Gp:) 9
(Gp:) 9
(Gp:) 9
(Gp:) 9
(Gp:) 16
(Gp:) 16
(Gp:) 16
(Gp:) 16
(Gp:) 16
(Gp:) 16
HIPERCUBO
(Gp:) Dim1
Dim2
Dim3
Dim4
(Gp:) Diámetro = log2 N
(Gp:) Grado = log2 N
(Gp:) Fácil encaminar
‘N=2k’ nodos, ‘k’ dimensiones = log2 N
Escalable a costa de demasiado grado
Topología cada vez menos utilizada
Encaminamiento en HIPERCUBO (Sea N=16)
(Gp:) 0001
(Gp:) 0010
(Gp:) 0100
(Gp:) 1000
(Gp:) 1
(Gp:) 2
(Gp:) 3
(Gp:) 4
(Gp:) 1. Numerar nodos en binario. Nodos adyacentes difieren en un bit (el asociado a la dirección que les une)
(Gp:) 0000
(Gp:) 4321
(Gp:) 1010
(Gp:) 1111
(Gp:) 0101
(Gp:) 0111
(Gp:) 0110
(Gp:) 0011
2. Enviar mensaje por el enlace asociado a la menor dirección donde no coinciden bit del nodo actual y bit del nodo destino
(Gp:) Nodo actual 0111
Nodo destino 1010
(Gp:) 0110
1010
(Gp:) 0010
1010
(Gp:) 1010
1010
¿ Realizar ORX ?
0111 ORX 1010 = 1101
(Gp:) ¿Caminos distintos?
HIPERCUBO CON CICLOS
K=3
(Gp:) 2
(Gp:) 2
(Gp:) 4
(Gp:) 3
(Gp:) 4
(Gp:) 5
(Gp:) 5
(Gp:) 4
(Gp:) 3
(Gp:) 4
(Gp:) 1
(Gp:) 3
(Gp:) 1
(Gp:) 2
(Gp:) 2
(Gp:) 3
(Gp:) 6
(Gp:) 4
(Gp:) 4
(Gp:) 3
(Gp:) 3
(Gp:) 1
(Gp:) 5
(Gp:) 0
Grado, diámetro, escalable, …
¿ Diámetro ?
¿Cómo conectar unos 1024 nodos?
(Gp:) M3D 10*10*10
(Gp:) 27
(Gp:) 6*
(Gp:) T3D 10*10*10
(Gp:) 15
(Gp:) 6
(Gp:) Hipercubo 10
(Gp:) 10
(Gp:) 10
(Gp:) HiperCiclo 7
(Gp:) 3
(Gp:) 896 N
(Gp:) Grafo Kautz
(Gp:) 6
(Gp:) 3
(Gp:) 972 N
(Gp:) 16
(Gp:) WK 4ary 5rec
(Gp:) 31
(Gp:) 4*
(Gp:) M2D 32*32
(Gp:) 62
(Gp:) 4*
(Gp:) Árbol
(Gp:) 18
(Gp:) 3*
(Gp:) Topología
(Gp:) Diámetro
(Gp:) Grado
(Gp:) Total
(Gp:) 1
(Gp:) 1023
(Gp:) Anillo10
(Gp:) 9
(Gp:) 10
(Gp:) Anillo2
(Gp:) 512
(Gp:) 2
(Gp:) Array lineal
(Gp:) 1023
(Gp:) 2*
(Gp:) Topología
(Gp:) Grado
(Gp:) Diámetro
(Gp:) Nº de nodos
(Gp:) Array lineal
(Gp:) Anillo
(Gp:) Anillo de grado ‘n’
(Gp:) Árbol binario
(Gp:) Árbol binario equilibrado
(Gp:) Estrella
(Gp:) Malla
(Gp:) Toroide
(Gp:) Hipercubo
(Gp:) Hipercubo con ciclos
(Gp:) N
(Gp:) 2
(Gp:) N-1
(Gp:) N
(Gp:) 2
(Gp:) ?N/2?
(Gp:) N
(Gp:) n=log2N
(Gp:) n-1
(Gp:) 2K-1
(Gp:) 3
(Gp:) 2*(K-1)
(Gp:) 2K-1
(Gp:) 2K
(Gp:) 2*(K-1)
(Gp:) N
(Gp:) N-1
(Gp:) 2
(Gp:) nK
(Gp:) 2*K
(Gp:) K*(n-1)
(Gp:) nK
(Gp:) 2*K
(Gp:) K* ? n/2 ?
(Gp:) 2K
(Gp:) K
(Gp:) K
(Gp:) K*2K
(Gp:) 3
(Gp:) 2*K – 1 + ? K/2 ?
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)
(Gp:) Multiprocessor systems-on-chips (MPSoCs)
(Gp:) Hoy 4..16 núcleos
¿Se llegará a 400 en 2020?
(Gp:) 1983-1987
(Gp:) 1988-1992
(Gp:) 1993-1997
M1
M2
M3
Mm
?P1
?P2
?P3
?Pn
“Crossbar”
Funcionalidad de los conmutadores simples:
colisión
(Gp:) difusión
(Gp:) Perfil N*M
(Gp:) O (N2)
(Gp:) Muchas patas
8×8 OnChip
mm2 => 5 núcleos
W => 2 núcleos
(Gp:) crossbar
8*8
(Gp:) O (64)
Perfil 8*8
Latencia 1
¿ Reducir O( N2) a costa de … ?
(Gp:) Usar sólo crossbar 2*2
(Gp:) directo
(Gp:) cruce
(Gp:) difusión
(Gp:) colisión
(Gp:) etapa 1
(Gp:) etapa 2
(Gp:) etapa m
(Gp:) Red de interconexión
(Gp:) Conjunto de crossbar 2*2
?
(Gp:) a
(Gp:) b
(Gp:) c
(Gp:) d
(Gp:) e
(Gp:) f
(Gp:) g
(Gp:) h
Red de interconexión “perfect Suffle”
Limitado a N = potencia de 2
(Gp:) N = 2
N = 4
Viable: [a,f – b,e – c,h – d,g]
NoViable: [a,f – c,e – …….]
Crossbar ? 24
Red ? ? 16
Red de interconexión “perfect Suffle”
Limitado a N = potencia de 2
(Gp:) 000
(Gp:) 001
(Gp:) 010
(Gp:) 011
(Gp:) 100
(Gp:) 101
(Gp:) 110
(Gp:) 111
(Gp:) 000
(Gp:) 001
(Gp:) 010
(Gp:) 011
(Gp:) 100
(Gp:) 101
(Gp:) 110
(Gp:) 111
(Gp:) ¿Encaminamiento?
Sea de 001 a 010
(Gp:) 001
(Gp:) 010
(Gp:) 001
(Gp:) 010
(Gp:) Bit igual => directo
Bit distinto => cruce
(Gp:) 001
(Gp:) 010
(Gp:) 001
(Gp:) 010
(Gp:) 011
(Gp:) 001
(Gp:) 100
(Gp:) 100
(Gp:) 110
(Gp:) 101
Colisión
¿ Latencia
y O( ) ?
¿Mejorable?
(Gp:) 000
(Gp:) 001
(Gp:) 010
(Gp:) 011
(Gp:) 100
(Gp:) 101
(Gp:) 110
(Gp:) 111
(Gp:) 000
(Gp:) 001
(Gp:) 010
(Gp:) 011
(Gp:) 100
(Gp:) 101
(Gp:) 110
(Gp:) 111
(Gp:) 101
(Gp:) 000
(Gp:) 001
(Gp:) 010
(Gp:) 011
(Gp:) 100
(Gp:) 101
(Gp:) 110
(Gp:) 111
¡ Permite difusió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
#NODOS TIPO DE RED SUPERCOMPUTADOR
..N Configurable Bull systems
>50.000 Dragonfly Cray Inc. XC30
.. 1.152 Toro 2y3D Cray Inc. XE6/XE6m
(96+96)*N Toro 3D Cray Inc. XK7
.. 4.096 ..? Toro 3D + Árbol Eurotech Aurora
.. 98.304 Toro 6D Fujitsu PRIMEHPC FX 10
.. 512 Crossbar multidim. Hitachi SR 16000
.. 1.572.864 Toro 5D IBM BlueGene/Q
256 x 2.048 Variable IBM eServer p775
.. 8.192 Crossbar multidim. NEC SX-9
.. 4.096 Toro 2D .. ? SGI Altix UV
intercluster
