Sistemasde Procesadores Paralelos - UNICEN

1

Sistemas de ProcesadoresParalelos

(Multiprocesadores y Multicomputadoras)

PARTE I

Profesor: Mag. Marcelo TosiniCátedra: Arquitectura de Computadoras y técnicas DigitalesCarrera: Ingeniería de SistemasCiclo: 4º año

Generalidades

3

Introducción

Sistemas de cómputo compuestos por varios (decenas… miles) de procesadoresSistemas de cómputo compuestos por varios (decenas… miles) de procesadores

Tres elementos principales:• Procesadores• Memoria• Interconexión

Tres elementos principales:• Procesadores• Memoria• Interconexión

Microprocesadores

• Fuertemente acoplados

•Comunicación a través de

memoria central

• Velocidad acotada por el

ancho de banda (bits/seg.)

• Conexionado a través de

una red o con memorias

multipuerta

• Fuertemente acoplados


memoria central

• Velocidad acotada por el

ancho de banda (bits/seg.)

• Conexionado a través de

una red o con memorias

multipuerta

Multicomputadoras

• Débilmente acoplados


redes de comunicación

• Existe un protocolo de

pasaje de mensajes

• Cada procesador posee su

propia memoria RAM y sus

puertos de I/O

• Débilmente acoplados


redes de comunicación

• Existe un protocolo de

pasaje de mensajes

• Cada procesador posee su

propia memoria RAM y sus

puertos de I/O

4

Multiprocesadores

Multiprocesadores

COMA NUMAUMA

SMP: SymetricMultiProcessor

DSM: DistributedShared Memory

Distintas maneras de organizar la memoria común

UMA (Uniform Memory Access)La memoria física es uniformemente compartida por todos los procesadores. Todos los procesadores tienen el mismo tiempo de acceso a todas las palabras de la memoria. Cada procesador tiene su propia caché privada y también se comparten los periféricos

NUMA (Non Uniform Memory Access)El acceso a memoria no es uniforme para diferentes procesadores. Existen memorias localesasociadas a cada procesador y estos pueden acceder a datos de su memoria local de una manera más rápida que a las memorias de otros procesadores

COMA (Cache Only Memory Access)Caso especial de los sistemas NUMA. No ha tenido mucha transcendencia, al igual que los SIMD. Las memorias distribuidas son memorias caché, por este motivo es un sistema muy restringido en cuanto a la capacidad de memoria global. No hay jerarquía de memoria en cada módulo procesador. Todas las caché forman un mismo espacio global de direcciones.

5

Multicomputadores

Multicomputadoras

NOW

COWMPP

• Se pueden ver como un computador paralelo en el cual cada procesador tiene su propiamemoria local.

• En estos sistemas la memoria se encuentra distribuida y no compartida como en lossistemas multiprocesador.

• Los computadores se comunican a través de paso de mensajes• Sólo tienen acceso directo a su memoria local y no al las memorias del resto de procesadores.

• El diagrama de bloques de un multicomputador es similar a los sistemas UMA

• Se pueden ver como un computador paralelo en el cual cada procesador tiene su propiamemoria local.

• En estos sistemas la memoria se encuentra distribuida y no compartida como en lossistemas multiprocesador.

• Los computadores se comunican a través de paso de mensajes• Sólo tienen acceso directo a su memoria local y no al las memorias del resto de procesadores.

• El diagrama de bloques de un multicomputador es similar a los sistemas UMA

• MPP: Masively Parallel Processors

• COW: Cluster of Workstations

• NOW: Network of Workstations

6

Sistema de memoria compartida

PE1PE1 PE2PE2 PEnPEn

MemoriaMemoriaRed de interconexiónRed de interconexión

Mapeo

memoria

Mapeo

memoria

PEPE

caché

local

caché

local

Sistema de memoria compartida

UMA

Red de interconexión

Elemento de proceso con memoria local

7

Sistema de pasaje de mensajes

bus de transferencia de mensajesbus de transferencia de mensajes

Esquema de un módulo de procesamiento

Conexión entre los módulos

y la red de interconexión

a través del sistema de

transferencia de

mensajes (STM)

PEPE

memorialocal

memorialocal E/SE/S

STMSTM

8

Conectividad de ambas alternativas

µP1µP1 µP2µP2 µP3µP3 µPnµPn

RedRed

M1M1 MkMkM2M2

Memoria común(Load / Store)

[La RED comunica procesadores y memorias]Se realiza por hardware

µP1µP1 µP2µP2 µP3µP3 µPnµPn

RedRed

Paso de mensajes(Send / Receive)[La RED comunica

procesadores entre si]Se realiza por software

Multiprocesadores Multicomputadoras

Redes de

Interconexión

10

Indirectas (dinámicas basadas en switches)• Topologías regulares

• Crossbar• De interconexión multietapa (MIN)

• Redes con bloqueos• MIN unidireccional• MIN bidireccional

Red Omega• Redes sin bloqueos

• Red Closs• Hipercubo

• Topologías irregulares

Indirectas (dinámicas basadas en switches)• Topologías regulares

• Crossbar• De interconexión multietapa (MIN)

• Redes con bloqueos• MIN unidireccional• MIN bidireccional

Red Omega• Redes sin bloqueos

• Red Closs• Hipercubo

• Topologías irregulares

Clasificación de las redes de

interconexión

De medio compartido• Redes de área local

• Ethernet• Token bus• Token ring

• Bus de sistema

De medio compartido• Redes de área local

• Ethernet• Token bus• Token ring

• Bus de sistema

Directas (estáticas basadas en routers)• Topologías estrictamente ortogonales

• Malla• 2D• 3D

• Toroides• Toro 1D unidireccional• Toro 2D unidireccional• Toro 2D bidireccional

• Hipercubo• Otras topologías específicas:

• Árboles, grafos en estrella, etc

Directas (estáticas basadas en routers)• Topologías estrictamente ortogonales

• Malla• 2D• 3D

• Toroides• Toro 1D unidireccional• Toro 2D unidireccional• Toro 2D bidireccional

• Hipercubo• Otras topologías específicas:

• Árboles, grafos en estrella, etc

Híbridas• Buses de sistema múltiples• Redes jerárquicas• Otras topologías Hipergrafo

• Hiperbuses• Hipermallas

Híbridas• Buses de sistema múltiples• Redes jerárquicas• Otras topologías Hipergrafo

• Hiperbuses• Hipermallas

1

2

3

4

11

Redes de medio compartido

• El medio de comunicación es compartido por todos los elementos de proceso

• Sólo un dispositivo puede usar la red en un momento dado• La red actúa como un elemento pasivo ya que no genera mensajes• La comunicación es tipo broadcast por lo que debe haber sistemas dearbitraje para solucionar colisiones

• El medio de comunicación es compartido por todos los elementos de proceso

• Sólo un dispositivo puede usar la red en un momento dado• La red actúa como un elemento pasivo ya que no genera mensajes• La comunicación es tipo broadcast por lo que debe haber sistemas dearbitraje para solucionar colisiones

Redes de área local

Permiten comunicar equipos distanciados varios metros entre si

Buses

Comunican equipos (procesadores) dentro de un rack


Permiten comunicar equipos distanciados varios metros entre si

Buses

Comunican equipos (procesadores) dentro de un rack

1

12

Bus de sistema

•• Estructura mas simple para comunicar procesadores basados en buEstructura mas simple para comunicar procesadores basados en buss

•• Conecta procesadores y memorias en topologConecta procesadores y memorias en topologíía UMAa UMA

•• SegSegúún la arquitectura puede ser:n la arquitectura puede ser:

•• Un bus Un bus bidireccionalbidireccional

•• Dos buses unidireccionalesDos buses unidireccionales

Proc1Proc1

Mem1Mem1 I/OI/O

Proc3Proc3Proc2Proc2

Mem2Mem2

Bus

driver

Bus

driverProc1Proc1 Mem1Mem1 I/OI/OProc3Proc3Proc2Proc2Bus

driver

Bus

driver

Un bus bidireccional Dos buses unidireccionales

1

13


• Bus de Contención (CSMA/CD)Acceso al bus compartido mediante competencia entre los dispositivos yresolución de colisiones. Mas popular: CSMA/CD

Desventaja: No determinista. No se puede garantizar el tiempo de esperade un dispositivo hasta ganar el acceso al bus

Velocidades de 10 Mbps a 100 Mbps

• Bus de Contención (CSMA/CD)Acceso al bus compartido mediante competencia entre los dispositivos yresolución de colisiones. Mas popular: CSMA/CD

Desventaja: No determinista. No se puede garantizar el tiempo de esperade un dispositivo hasta ganar el acceso al bus

Velocidades de 10 Mbps a 100 Mbps

• Token Bus

Dispositivos conectados en modo broadcast al medio (bus)

Uso de un token circulante entre los dispositivos en orden para habilitarel uso del bus

Velocidades de 2.4 Mbps

• Token Bus

Dispositivos conectados en modo broadcast al medio (bus)

Uso de un token circulante entre los dispositivos en orden para habilitarel uso del bus

Velocidades de 2.4 Mbps

• Token Ring

Dispositivos conectados en anillo físico

Uso de un token circulante entre los dispositivos

Velocidades de hasta 16 Mbps sobre cable y hasta 100 Mbps con FDDI (Fiber distributedData Interface)

• Token Ring

Dispositivos conectados en anillo físico

Uso de un token circulante entre los dispositivos

Velocidades de hasta 16 Mbps sobre cable y hasta 100 Mbps con FDDI (Fiber distributedData Interface)

1

14

Redes Directas (punto a punto)

ProcesadorProcesador Memorialocal

MemorialocalI/OI/O

RouterRouter

canales de entrada

canales de salida

• Conexiones punto a punto entre distintosprocesadores de la red

• Consiste en un conjunto de nodos• Cada nodo se conecta a un subconjuntode otros nodos de la red

• Se pueden formar varios patrones regulares o irregulares

• Cada nodo posee un procesador, memoria localy dispositivos de entrada/salida

• Los nodos pueden tener distintas capacidadesfuncionales: vectoriales, gráficos, etc

• El nodo se conecta a la red a través de un router• El router maneja la comunicación mediante el usode mensajes

• Cada router tiene conexión directa con el routerde sus vecinos

• Los nodos no están necesariamente conectados físicamente a todos los demás nodos de la red

• La topología de conexiones debe asegurar que todoslos nodos se puedan acceder desde cualquier nodo

Arquitectura de un nodo

2

15

Redes Directas (punto a punto)EjemplosEjemplos

hipercubo Toroide

Malla

Árbol

Panal Red De Bruijn

2

16

Redes Directas (punto a punto)

Mezcla perfecta(perfect shuffle)

Mas ejemplosMas ejemplos

Anillo

Estrella

Mesh 3D

2

17

Redes Directas: Cubo cósmico

Ejemplo muy representativo de un sistema de pasaje deEjemplo muy representativo de un sistema de pasaje de

mensajesmensajes

Características:

• Constituido por 64 computadoras (nodos)

• Interconectadas por una red punto a punto bidireccional y

asincrónica

• Cada procesador está conectado a 6 nodos distintos

• La geometría subyacente es la de un hipercubo de 6

dimensiones

2

18


2

19


Como hay 64 procesadores

cada uno tiene una dirección

de 6 bits (0 a 63)

Entonces:

log 2 (#proc) = # vecinos

Vecinos:

procesadores cuya

dirección varia en

un bit

2

20


cargador

Paquet

e

de inic

io

Edición y

compilación

de programas

2

21

Redes Híbridas• Combinan mecanismos de las otras 3 categorías (compartidas, directas e indirectas)• Incrementan el ancho de banda respecto a las de medio compartido • Reducen la distancia entre nodos respecto a las redes directas e indirectas• Modeladas como hipergrafos:

• vértices: Conjunto de nodos de procesamiento• aristas: Conjunto de canales de comunicación o buses

Global busGlobal bus

Cluster busCluster busCluster busCluster bus

·····

Jerarquía de 2 niveles de buses

Cluster busCluster bus

Cluster busCluster bus

Cluster busCluster bus Cluster busCluster bus

Cluster busCluster busCluster busCluster bus

Malla bidimensional de clusters

4

22

Redes indirectas• Basadas en conmutadores (switches)• No existe comunicación directa entre nodos (como en las directas)• La conexión entre nodos se realiza mediante uno o más switches• Cada switch tiene un conjunto de puertos• Cada puerto posee un enlace de entrada y otro de salida• Cada switch puede tener conectados algunos nodos (o ninguno)• Cada switch se conecta con otros switches

S1S1 S1S1 S1S1

S1S1S1S1

S1S1

SnSn Switch

Nodo

Topología irregular

3

23

Redes indirectas

Red Red CrossbarCrossbar

SS

SS

SS

SS

SS

SS

SS

SS

SS

V1V1

V2V2

V3V3

H1H1

H2H2

H3H3

• Utilizada comúnmente en sistemas de memoria compartida, proveyendo accesos simultáneos no bloqueantes entre dispositivos fuente y destino (V y H).

• Cada conmutador de cruce (switch) puede ofrecer un camino único de conexión entre unpar de elementos

• Los conmutadores se pueden encender o apagar desde el programa• Una configuración usual de microprocesadores es la de disponer los procesadores en una entrada (p.e. Vertical) y las memorias en la otra entrada (p.e. Horizontal)

3

24

Redes indirectasRed Red CrossbarCrossbar• En condiciones particulares puede funcionar como un bus permitiendo que varios destinos reciban información de una sola fuente

• Permite conexionado entre procesadores dispuestos como multicomputadora, usando la red como medio de pasaje de mensajes

• Usos:• Como mecanismo de conexionado de procesadores con memorias• Como red de interconexión entre procesadores• En el diseño de routers para redes directas• Como componentes básico de diseño de redes indirectas de gran escala

• Para una crossbar de N entradas y M salidas el costo es O(NM)• Es escalable ya que se puede implementar una crossbar de N x M usando (N/n) * (M/n) crossbar de n x n

Switch básico(2 entradas2 salidas)

Crossbarde 2 entradasy 2 salidas

(con E/S auxiliares)

Crossbarde 4 entradasy 4 salidas

(con 4 crossbar de 2x2)

3

25

Redes indirectas

Memorias Memorias MultipuertoMultipuerto

Las memorias miltipuerto hacen posible la construcción de redes de interconexión

en las que los procesadores se comunican a través de las memorias en lugar de buses.

Desventaja: los procesadores deben esperar en caso de acceso a la misma locación

de memoria

Ventaja: los protocolos de comunicación entre unidades funcionales se reducen

MM

P2P2

P4P4

P3P3

P1P1

3

26

Métricas de rendimiento de las redes

• Complejidad de hardware: Medida asintótica del área

• Diámetro: Máximo de los caminos más cortos entre 2 nodos cualquiera de la red

• Bloqueo: Si se puede o no establecer una nueva conexión en presencia de otras conexiones

• Grado de nodo: Número de nodos a los que se conecta cada nodo

N procesadores

Ci = N

D = N/2

B = Si

G = 2

N procesadores

Ci = N2

D = 1

B = No

G = N/2

))((minmax,

plengthDijPpNji ∈∈

=

3

27

Redes de interconexión multietapa(MIN – Multistage Interconnection Networks)

a x bswitch

a x bswitch

Inter-stageconnection1


a x bswitch

a x bswitch

···

a x bswitch

a x bswitch

a x bswitch

a x bswitch



a x bswitch

a x bswitch

···

a x bswitch

a x bswitch

a x bswitch

a x bswitch



a x bswitch

a x bswitch

···

a x bswitch

a x bswitch

a x bswitch

a x bswitch

Inter-stageconnectionn-1

Inter-stageconnectionn-1

a x bswitch

a x bswitch

···

a x bswitch

a x bswitch

···

···

···

Stage 1 Stage 2 Stage 3 Stage G

• Una red multietapa genérica se compone de G etapas generalmente iguales• Cada etapa se forma con k switches compuestos por crossbars de axb entradas/salidas• Entre etapas adyacentes se usa una red de interconexión fija• El número de etapas, la cantidad de crossbars de cada etapa y los valores a y b determinanla capacidad de encaminamiento de las redes MIN

• Según la relación entre entradas y salidas se denominan:• N = M : unicast• N > M : concentradores• N < M : expansores

N entradas

M salidas

3

28


pi= q

i-1connectionlinks

pi= q

i-1connectionlinks a x b

switch

a x bswitch

a x bswitch

a x bswitch

···

a x bswitch

a x bswitch

• Para una red de G etapas adyacentes cada etapa Gi tiene wi switches de tamaño ai,j x bi,j donde 1≤j≤ wi .

• La etapa Gi consta de pi entradas y qi salidas

Ci etapa Gi Ci+1

wi switches

qi= p

i+1connectionlinks

qi= p

i+1connectionlinks

···

···

ai,1 bi,1

ai,2 bi,2

ai,wi bi,wi

∑

∑

=

=

=

=

i

i

w

jjii

w

jjii

bq

ap

1,

1,

• La conexión entre 2 etapas adyacentesGi-1 y Gi (Ci), define al patrón deconexión para pi=qi-1 enlaces, conp0 = N y qg-1 = M

• Un patrón de conexión Ci(pi) define comodeben estar conectadas las qi-1 salidas dela etapa anterior con las pi entradas a la etapa actual

3

29


2 x 22 x 2

2 x 22 x 2

···

2 x 22 x 2

• Las distintas redes multietapa se diferencian en los módulos conmutadores(switches) y en los patrones de las conexiones entre etapas (CEE)

• Los módulos conmutadores mas simples y usados son crossbars de 2 x 2• Las CEE mas populares son:

• Perfect shuffle• Butterfly• Crossbar• Reversal• Baseline• Exchange

···

···

3

30

Patrones de Conexión entre etapas

• Funciones que mapean N entradas en N salidas

• Cuando se ejecuta una función de ruteo f el dato de la entrada pies enviado a la salida qf(i)

• En la CEE, cada puerto de entrada y salida tiene una direcciónúnica que se puede expresar con m bits de la forma

• Dado que el número de entradas (p) es igual al número de salidas (q) a las conexiones entre etapas se las denomina permutaciones

X = xn-1, xn-2, …, x0

GeneralidadesGeneralidades

3

31


PerfectPerfect shuffleshuffle ((σσ))

σk(xn-1 xn-2 …x1 x0) = xn-2 … x1 x0 xn-1

NN

kXkXX

k mod)()(

+=σ

La permutación entre los patrones de entrada y salida se basa en la mezcla perfecta de dos montones (de cartas) iguales, intercalando una a una las cartasde un montón en el otroLa red perfect shuffle toma la primera mitad de las entradas y las entremezcla con la segunda mitad, de manera que la primera mitad pasa a las posiciones paresde las salidas y la segunda mitad a las impares

Perfect shuffle realiza un desplazamiento cíclico hacia la izquierda de los dígitos de X en log2 k

posiciones

σk-1(xn-1 xn-2 …x1 x0) = x0 … xn-1 xn-2 x1

Inverse perfect shuffle realiza un desplazamiento cíclico hacia la derecha de los dígitos de X en log2 k

posiciones

con k = 1, 2… 4y k ≤ N

3

32


Ejemplo de Ejemplo de PerfectPerfect shuffleshuffle ((σσ) para N=8) para N=8

0 (000)

1 (001)

2 (010)

3 (011)

4 (100)

5 (101)

6 (110)

7 (111)

0 (000)

1 (001)

2 (010)

3 (011)

4 (100)

5 (101)

6 (110)

7 (111)

Perfect shufflek = 2

0 (000)

1 (001)

2 (010)

3 (011)

4 (100)

5 (101)

6 (110)

7 (111)

0 (000)

1 (001)

2 (010)

3 (011)

4 (100)

5 (101)

6 (110)

7 (111)

Inverse perfect shufflek = 2

0 (000)

1 (001)

2 (010)

3 (011)

4 (100)

5 (101)

6 (110)

7 (111)

0 (000)

1 (001)

2 (010)

3 (011)

4 (100)

5 (101)

6 (110)

7 (111)

Perfect shufflek = 4

3

33


BitBit reversalreversal ((ρρ))

ρρ(xn-1 xn-2 …x1 x0) = x0 x1 … xn-2 xn-1

La permutación entre los patrones de entrada y salida se basa en el intercambiode los bits simétricos

x7 x6 x5 x4 x3 x2 x1 x0

0 (000)

1 (001)

2 (010)

3 (011)

4 (100)

5 (101)

6 (110)

7 (111)

0 (000)

1 (001)

2 (010)

3 (011)

4 (100)

5 (101)

6 (110)

7 (111)

Bit reversalN = 8

3

34


ButterflyButterfly ((ββ))

La permutación entre los patrones de entrada y salida se basa en el intercambiode los bits simétricos

01111110111111.........).........( xxxxxxxxxxxxxxxxxx

iiijjjnjjjiiini −+−+−−+−+−=β

la i-esima permutación butterfly intercambialos dígitos i-esimo y el j-esimo, siendo ambossimétricos respecto de la mitad de los dígitos

con i+j=N-1

xi xj

3

35


Variantes de Variantes de ButterflyButterfly ((ββ))

• k-sub butterfly: basada en el intercambio de los bits 0 con el k-1

11010111......)......(

−−−−=

kknkknkxxxxxxxxxxβ xk x0

• k-supra butterfly: basada en el intercambio de los bits n-1 con el k-1

01110111......)......( xxxxxxxxxx

nkkkkn

k

−−−−=β xn-1 xk

3

36


ButterflyButterfly ((ββ))

0 (000)

1 (001)

2 (010)

3 (011)

4 (100)

5 (101)

6 (110)

7 (111)

0 (000)

1 (001)

2 (010)

3 (011)

4 (100)

5 (101)

6 (110)

7 (111)

Butterflyi = 2

0 (000)

1 (001)

2 (010)

3 (011)

4 (100)

5 (101)

6 (110)

7 (111)

0 (000)

1 (001)

2 (010)

3 (011)

4 (100)

5 (101)

6 (110)

7 (111)

Butterfly sub kk = 2

0 (000)

1 (001)

2 (010)

3 (011)

4 (100)

5 (101)

6 (110)

7 (111)

0 (000)

1 (001)

2 (010)

3 (011)

4 (100)

5 (101)

6 (110)

7 (111)

Butterfly sub kk = 1

IDENTIDAD!!!

3

37


Exchange (E)Exchange (E)

1 <= i <= N-1

000 001

101

111110

100

011010

E0(x)

E1(x)

E2(x)

0111101111......)......( xxxxxxxxxxxxE

iiiniiini −+−−+−= xi

0 (000)

1 (001)

2 (010)

3 (011)

4 (100)

5 (101)

6 (110)

7 (111)

0 (000)

1 (001)

2 (010)

3 (011)

4 (100)

5 (101)

6 (110)

7 (111)

i = 2

3

38


BarrelBarrel ShifterShifter (SH)(SH)

N

k

kXXSH ±=± )(

0 (000)

1 (001)

2 (010)

3 (011)

4 (100)

5 (101)

6 (110)

7 (111)

0 (000)

1 (001)

2 (010)

3 (011)

4 (100)

5 (101)

6 (110)

7 (111)

Barrel Shifterk = 1

0 (000)

1 (001)

2 (010)

3 (011)

4 (100)

5 (101)

6 (110)

7 (111)

0 (000)

1 (001)

2 (010)

3 (011)

4 (100)

5 (101)

6 (110)

7 (111)

Barrel Shifterk = 2

0 (000)

1 (001)

2 (010)

3 (011)

4 (100)

5 (101)

6 (110)

7 (111)

0 (000)

1 (001)

2 (010)

3 (011)

4 (100)

5 (101)

6 (110)

7 (111)

barrel Shifterk = -1 (≈ +7)

con k potencia de 2 y k < N

3

39


BarrelBarrel ShifterShifter (SH)(SH) Notas de mérito

• La permutación barrel shifter realmente no realiza la operación de suma

• Puesto que los CEE son módulos cableados, la permutación soloconecta una entrada X a una salida a distancia X ± k

• La utilidad de esta CEE se evidencia en la implementación detopologías de anillos

Anillok = 1

Doble anillok = 2

Barrel Shifterk = 4

3

40


BarrelBarrel ShifterShifter (SH)(SH) Otros ejemplos

Anillo acordeN = 8k = 2k´ = 1

Grado = 2

Anillo acordeN = 8k = 4k´= 1

Grado = 2

Barrel ShifterN = 8k = 4k´ = 2k” = 1

Grado = 3

Las combinaciones de varias permutaciones simultáneamente se usafrecuentemente en multicomputadores

Arreglo linealN = 8k = 2k´ = 1

Grado = 2

3

41

Patrones de Conexión entre etapasBaselineBaseline connectionconnection ((δδ))

1 <= i <= N-1

1101101111......)......( xxxxxxxxxxxx

iiiniiini −+−−+−=δ xi+1

0 (000)

1 (001)

2 (010)

3 (011)

4 (100)

5 (101)

6 (110)

7 (111)

0 (000)

1 (001)

2 (010)

3 (011)

4 (100)

5 (101)

6 (110)

7 (111)

Baselinei = 2

0 (000)

1 (001)

2 (010)

3 (011)

4 (100)

5 (101)

6 (110)

7 (111)

0 (000)

1 (001)

2 (010)

3 (011)

4 (100)

5 (101)

6 (110)

7 (111)

Baselinei = 1

0 (000)

1 (001)

2 (010)

3 (011)

4 (100)

5 (101)

6 (110)

7 (111)

0 (000)

1 (001)

2 (010)

3 (011)

4 (100)

5 (101)

6 (110)

7 (111)

Baselinei = 0

IDENTIDAD!!!

3

42

Tipos de redes multietapa

Tres tipos dependiendo de la disponibilidad de caminos para establecer nuevas conexiones:

• Bloqueantes: No siempre es posible la conexión entre un puerto de entrada y otro de salida por conflictos entre conexiones existentes

• No bloqueantes: cualquier puerto de entrada puede conectarsea cualquier puerto de salida libre sin afectar a las conexiones yaexistentes

• Reconfigurables: Cada puerto de entrada puede ser conectadoa cada puerto de salida. Sin embargo las conexiones existentespueden requerir de un reajuste en sus caminos

3

43

Redes no bloqueantes

• Son intrínsicamente caras debido a su característica de no bloqueo

• Mas baratas que una crossbar del mismo tamaño

• Costo prohibitivo para grandes tamaños de red

• Conectan cualquier entrada libre a cualquier salida libre

(sin importar otras conexiones).

• Cada nodo en cualquier etapa es una red crossbar

Red CrossbarRed crossbar

Switch básico Crossbar

3

44

Redes no bloqueantesEjEj: Red : Red ClosClos de 3 etapas para N entradas y M salidasde 3 etapas para N entradas y M salidas

En el caso mas usual n = p (red clos balanceada)En el caso mas usual n = p (red clos balanceada)

n x rn x r

1

n

n x rn x r

1

n

n x rn x r

1

n

···

r x pr x p

1

p

r x pr x p

1

p

r x pr x p

1

p

···

N/nxM/pN/nxM/p

···

N/nxM/pN/nxM/p

N/nxM/pN/nxM/p

N/n crossbarde n entradas

y r salidascada uno

M/p crossbarde r entradasy p salidascada uno

r = (n-1)+(p-1)+1 crossbarde N/n entradas y M/p salidas

cada uno

3

45

Red Clos: Métricas

• Complejidad:• Área cuantificada por la cantidad de switches básicos

rpp

M

p

M

n

Nrnr

n

Nárea ++=

• Diámetro:• Camino más largo entre un nodo de entrada y un nodo de salida

)1()1()1( −++−++−+= prp

M

n

Nrndiámetro

• Máxima Complejidad:• Área (en switches básicos) de la crossbar mas grande de la red

);;max( rpp

M

n

NnridadMaxComplej =

3

46

Red Clos: ejemplo de diseño

Problema: se desea diseñar una red estrictamente no bloqueante para

12 canales (12 entradas y 12 salidas de la red)

manteniendo baja la complejidad máxima de cualquier

nodo de la red

Posibles soluciones:

(A) 2 nodos de entrada (salida) con 6 entradas cada uno (salidas)

(B) 3 nodos de entrada (salida) con 4 entradas cada uno (salidas)

(C) 4 nodos de entrada (salida) con 3 entradas cada uno (salidas)

(D) 6 nodos de entrada (salida) con 2 entradas cada uno (salidas)

3

47

Red Clos: ejemplo de diseño

n p r Máxima complejidad

A

B

C

D

6

4

3

2

6

4

3

2

11

7

5

3

6 x 11 = 66

4 x 7 = 28

4 x 4 = 16

6 x 6 = 36

Peor

Mej

or

3

48

Redes reconfigurables

Pueden realizar todas las conexiones posibles reconfigurando

conexiones existentes en caso de bloqueos.

0

1

2

3

0

1

2

3

0

1

2

3

0

1

2

3

No usados

En este estado si se desea usar la

conexión 1 con 1, la misma esta

bloqueada

Red Benes

3

49

Redes de interconexión bloqueante• Pueden realizar algunas pero no todas las interconexiones entreentradas y salidas

• Dependiendo del tipo de canales y switches se clasifican en:

• Unidireccionales: Los canales y switches son unidireccionales

• Bidireccionales: Los canales y switches son bidireccionales(La información puede transmitirse simultáneamente en direcciones opuestas entre switches vecinos)

3

50

Redes de interconexión bloqueante

Unidireccionales• Switches unidireccionales son crossbar a x b (a entradas y b salidas)

• Tipos de conexiones:• Unicast: Cada entrada puede conectarse a una única salida

Existen min(a, b) conexiones simultáneas

• Multicast: Cada entrada puede conectarse a varias salidas

• Broadcast: Cada entrada puede conectarse a todas las salidas

Etc.

3

51


Unidireccionales

Para N entradas y M salidas de la red: • Si N = M se usan conmutadores con a = b• Si N > M se usan conmutadores con a > b (concentradores)• Si N < M se usan conmutadores con a < b (distribuidores)

Para N puertos de entrada y salida (M = N) y conmutadores de k x kse necesitan al menos

NOTASNOTAS

Nk

log

Ejemplo:N = 16k = 2Etapas = 4




3

52

Redes Unidireccionales: EjemplosRed Red BaselineBaseline• El patrón de conexión Ci está descrito por la (n-i)-esima permutación en línea base δn-i (1≤i≤n)

• El patrón de conexión C0 está descrito por σk (perfect-shuffle)• Posee algoritmo de autoencaminamiento en el que los bits sucesivos de la dirección de destino controlan las sucesivas etapas de la red

• Cada etapa divide el camino en 2 sub caminos, uno hacia la parte alta y otro hacia la parte baja de la subred correspondiente

00000001

00100011

01000101

01100111

10001001

10101011

11001101

11101111

00000001

00100011

01000101

01100111

10001001

10101011

11001101

11101111

C0 G1 C1 G2 C2 G3 C3 G4 C4

3

53

Redes Unidireccionales: EjemplosRed OmegaRed Omega• El patrón de conexión Ci está descrito por la (n-i)-esima permutación perfect-shuffle σk (1≤i≤n-1)

• El patrón de conexión Cn está descrito por β0 (butterfly sub cero = identidad)• Posee algoritmo de autoencaminamiento en el que los bits sucesivos de la dirección de destino controlan las sucesivas etapas de la red

• Propuesta para el procesamiento de matrices usando switches 2x2 de cuatro estados (directo, intercambio, el de arriba a todos y el de abajo a todos)

00000001

00100011

01000101

01100111

10001001

10101011

11001101

11101111

00000001

00100011

01000101

01100111

10001001

10101011

11001101

11101111

C0 G1 C1 G2 C2 G3 C3 G4 C4

3

54

Funcionamiento de la red Omega

En la entrada a la etapa Gi el switch chequea el I-esimo bit de la

dirección de destino

si es 0, el switch selecciona la salida superior

sino, la salida inferior

Formato del paquete de mensaje:Formato del paquete de mensaje:

Dir destino mensaje

n bits

n = log2 N; N = num proc.

Cada vez que la dirección pasa cada etapa I, si el paquete llegó por

el puerto superior, entonces el I-esimo bit se reemplaza por 0. Si el

paquete llegó por el inferior, el I-esimo bit se reemplaza por 1

3

55

Redes Unidireccionales: EjemplosRed Red PerfectPerfect--shuffleshuffle/Exchange/Exchange• Derivada de la red Omega• Utiliza una red de recirculación que devuelve las salidas nuevamente a las entradas

• La red posee una única etapa recirculable que se recorre n veces, una por cada etapa

3

56


Bidireccionales (BMIN)• Cada puerto de los switches posee un par de canales de comunicaciónunidireccionales de direcciones opuestas

• Un switch bidireccional soporta 3 tipos de conexiones:

• Forward: Cada entrada del lado izquierdoconectarse a varias salidas dellado derecho

Backward: Cada entrada del lado derechoconectarse a varias salidas dellado izquierdo

Turnaround (de regreso): Cada entrada de un ladopuede conectarse a varias salidas delmismo lado

3

57

Ejemplos de BMINs

000

001

010

011

100

101

110

111

C0 G0 C1 G1 C2 G2nodos

• Los caminos entre 2 nodos se establecen cruzando etapas hacia delante, despuésestableciendo una conexión de vuelta (en la última etapa) y, por último, cruzando lasetapas hacia atrás

• En el cruce hacia delante puede haber varios caminos posibles• En el cruce hacia atrás (retorno) sólo hay una posibilidad de camino• El peor caso (diámetro) para una red de n etapas es 2n-1

• Los caminos entre 2 nodos se establecen cruzando etapas hacia delante, despuésestableciendo una conexión de vuelta (en la última etapa) y, por último, cruzando lasetapas hacia atrás

• En el cruce hacia delante puede haber varios caminos posibles• En el cruce hacia atrás (retorno) sólo hay una posibilidad de camino• El peor caso (diámetro) para una red de n etapas es 2n-1

BMIN BMIN ButterflyButterfly

Fuente

Destino

3

58

Ejemplos de BMINs

• Los procesadores se encuentran en las hojas de un árbol de n niveles• Los nodos intermedios son switches bidireccionales• Una comunicación entre 2 nodos sube por el árbol hasta alcanzar el menor antecesorcomún de ambos nodos y posteriormente baja al destino

• Los procesadores se encuentran en las hojas de un árbol de n niveles• Los nodos intermedios son switches bidireccionales• Una comunicación entre 2 nodos sube por el árbol hasta alcanzar el menor antecesorcomún de ambos nodos y posteriormente baja al destino

BMIN BMIN FatFat treetree

3

59

Características generales de las redes

• Modo de operación:• Sincronizado: con control central de los switches

• No sincronizado: los switches son autónomos

• Técnicas de switching:• Circuit switching

• Packet switching (paquetes)

• Intermedio: (flits). Se establece un circuito y luego todos los flits lo siguen

• Técnicas de ruteo: métodos para establecer los paths de comunicación• Centralizado: control toma las decisiones para establecer el path

• Distribuido: cada switch decide el path

• Adaptativo: distribuido con información global de estado

•Topología: distribución física de la red

Documents

Sistemasde Procesadores Paralelos - UNICEN