PDF de programación - Arquitecturas Paralelas: Redes de interconexión y Medición de performance

Arquitecturas Paralelas:
Redes de interconexión y
Medición de performance

Versión 2014

Hesham El-Rewini & Mostafa Abd-El-Barr, Advanced
Computer Architecture and Parallel Processing. Willey.



Redes de interconexión para
arquitecturas paralelas

Pueden clasificarse según diferentes criterios:
Modo de operación: sincrónico vs. asincrónico.
 Estrategia de control: centralizado vs. descentralizado.
 Técnica de conmutación: circuitos vs. conmutación de paquetes.
 Topología: cómo se conectan procesadores y memorias entre sí.
Cada enlace presenta un balance entre performance (ancho de
banda) y costo.

Diferencia evidente entre redes para memoria compartida y
memoria distribuida. En este último caso no necesita estar
completamente conectada (ruteo de mensajes).



Redes de interconexión
Topologías para memoria compartida

a) Memoria multiport (no escala)
b) Bus (económica, bloqueante)
c) Red conmutada (balance)



Redes de interconexión
Topologías para memoria compartida
CROSSBAR

El routing dinámico se consigue utilizando redes de conmutación
compuestas por ´crossbar switches´ o ´2x2 switches´. Las redes
(permiten varias conexiones
crossbar
simultáneas) pero necesitan gran cantidad de switches (N2 para N
nodos).


son no bloqueantes



Redes de interconexión
Topologías para memoria compartida
OMEGA

Las redes de interconexión multietapa son las más avanzadas entre
las redes actuales de conmutación. En el caso de la red omega, para
conectar N nodos se necesitan log2N etapas con N/2 switches 2x2
cada una.



Redes de interconexión
Topologías para memoria compartida

Ventajas y desventajas de las diferentes topologías:
 Las redes tipo bus son económicas pero pueden transformarse en
el cuello de botella del sistema.
 Los buses paralelos mejoran la performance, pero son costosos.
 Las redes crossbar son no bloqueantes, pero requieren un gran
número de switches.
 Las redes omega son bloqueantes en menor grado. Presentan
mejor performance que los buses y son más económicas que las
crossbar.



Redes de interconexión
Topologías para pasaje de mensajes
I) Estáticas (pizarrón)

II) Dinámicas



4



Redes de interconexión
Topologías estáticas para pasaje de
mensajes
4-cube

7-cube



Redes de interconexión
Topologías estáticas para pasaje de
mensajes

Three-dimensional (3D)
torus network in which the
nodes are connected to
their six nearest-neighbor
nodes in a 3D mesh.



Redes de interconexión
Topologías estáticas para pasaje de
mensajes

Para n nodos, C es el número de conexiones y D el camino más largo
(diámetro de la red)

Completamente conectado: caro, crece rápido. Permite varias conexiones
simultáneas. D=1, C=n(n-1)/2

Anillo: muy económico: C=n. Pero D=n.

Toroide/grilla: más económico, buen equilibrio. D=2(sqrt(n)-1), C=2n
[toroide] y C=2n-sqrt(n) [grid]. C=2n (1D), C=4n (2D) y C=6n (3D)

Hipercubo de m dimensiones: cada nodo conectado a m vecinos. n=2m,
C=n.m/2, D=m.



Redes de interconexión
Ejemplo 8 nodos



Análisis de performance en
Arquitecturas Paralelas
Hesham El-Rewini & Mostafa Abd-El-Barr,
Advanced Computer Architecture and Parallel Processing. Willey.
Capítulo 3 completo.

 Peak rate (no muy útil, marketing)
 Mejora y Eficiencia [S=Ts/Tp, ξ=S/n]

Equal duration model: caso ideal [S=n, ξ=1]
Serial section model: ley de Amdahl [S<n,  <ξ 1]

 Amdahl vs. Gustafson-Barsis
 Efecto del tiempo de comunicación
 Escalabilidad



Definición de mejora y eficiencia

S=

t s
t m

ξ= S
n

Equal duration model

ξ=1



Fractional communication overhead

Serial section model







Serial section model
with communication overhead



Amdhal vs. Gustafson-Barsis

Algunos problemas no se comportan en forma
tan pesimista como predice Amdhal.

A veces el tamaño del problema aumenta con el
número de procesadores. SS(f) es una recta y no
presenta el límite en 1/f.

En este caso f va disminuyendo, en proporción,
al aumentar el orden del problema (en la práctica
sucede en algunos problemas)

S (n)=

n

1+f (n−1)



SS
n

SS

S

1

f

1

SS (n )= f+(1−f )×n
×n

(1−f )

f+

n

lim SS( n)n →∞=∞

SS (n) =n−f (n−1)

S vs. f

gnuplot> plot [x=0:1] [0:10] 5/(x*4+1) title "Amdahl n=5", 10/(x*9+1) title "Amdahl
n=10", 100/(x*99+1) title "Amdahl n=100",1/x title "Amdahl n=oo", 5-(x*4) title

"Gustafson n=5", 10-(x*9) title "Gustafson n=10", 100-(x*99) title "Gustafson n=100"



DISCUSIÓN: Expresión general de la mejora


S=

t1
t n

=

t s+t p
t p
n

+tc

t s+

Donde tanto ts como tc dependen de n



Métrica de Karp-Flatt

Despejando de Amdhal la sección serie (f) y
midiendo experimentalmente la mejora (S) que
se obtiene para un dado problema (utilizando n
procesadores), resulta que f es una medida de
cuán paralelizable es el problema. Puede
utilizarse para predecir cómo se comportará el
sistema al variar el número de procesadores.

f=

− 1
1
S
n
1− 1
n

Esta lógica aplica también si el modelo no es el de Amdhal



Escalabilidad
Ejemplo: Hipercubo de D dimensiones (n=2D, dist max
D=log2(n)), utilizado para realizar la suma de m números.
Mejora (hacia 4): escalable

m

+2 log2 n

S=

m
n



Es escalable si habiendo agregado nodos la
eficiencia se mantiene constante al aumentar m

for m=1:8,
    for n=1:8,
        N=2^n;
        M=2^(m+5);
        S(m,n)=M/(M/N+log2(N));       
        E(m,n)=S(m,n)/N;
    end
end
surf(S);    % ver que en la diagonal se vaya duplicando
ylabel('m: orden 2^(m+5)');
xlabel('n: nodos 2^n');
zlabel('Mejora');



m

+2 log2 n

S=

m
n

for m=1:8,
    for n=1:8,
        N=2^n;
        M=2^(m+5);
        S(m,n)=M/(M/N+log2(N));       
        E(m,n)=S(m,n)/N;
    end
end
surf(E);    % ver que la diagonal se mantenga constante
ylabel('m: orden 2^(m+5)');
xlabel('n: nodos 2^n');
zlabel('Eficiencia');



E=

m/n
+2 log 2n

m
n

Grado de escalabilidad / Isoeficiencia
El grado de escalabilidad de un sistema paralelo se determina por la relación
en que el problema debe incrementarse respecto del número de procesadores
(n), para mantener una eficiencia constante cuando el número de procesadores
aumenta.
Por ejemplo, en un sistema paralelo altamente escalable el tamaño del
problema deberá crecer linealmente con respecto de n a fin de mantener la
eficiencia constante.
En un sistema poco escalable el tamaño del problema necesitará crecer
exponencialmente con respecto de n para mantener la eficiencia constante.

e=

incremento del tamaño del problema

incremento de n para rendimiento constante

NUEVO: La isoeficiencia es la capacidad del sistema de mantener la eficiencia
constante cuando aumenta el número de procesadores.