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
