1Cluster Computing
Análisis del Rendimiento de un Cluster de
Computadoras para Aplicaciones Paralelas
Arturo Díaz PérezSantiago Domínguez, David Araujo Díaz, Ulises
Zaldívar Colado y Armando Flores IbarraSección de Computación
Departamento de Ingeniería Eléctrica
CINVESTAV-IPN
Av. Instituto Politécnico Nacional No. 2508
Col. San Pedro Zacatenco
México, D. F. CP 07300
Tel. (5)747 3800 Ext. 3755
e-mail: [email protected]
2Cluster Computing
Los Microprocesadores de Hoy
Conjuntos de InstruccionesRISC, CISC, Multimedia, Vector Processing (SIMD)
Sistemas de memoria avanzadoscaches (L1, L2 y L3)soporte para memoria virtual
Paralelismo a nivel de instrucciones ILPpipelining, superscalar, vectors, VLIW
Soporte para sistemas de I/OTecnología de interconexiónProcesamiento paralelo básico
3Cluster Computing Programs
Inst
ruct
ion
Issu
es p
er c
ycle
0
20
40
60
80
100
120
140
160
gcc espresso li fpppp doducd tomcatv
54.862.6
17.9
75.2
118.7
150.1
Integer: 18 - 60
FP: 75 - 150
IPC
Límites a ILP: Procesador Ideal
4Cluster Computing
Program
Instr
ucti
on
issu
es p
er
cycle
0
10
20
30
40
50
60
gcc expresso li fpppp doducd tomcatv
10
15
12
52
17
56
10
15
12
47
16
10
1311
35
15
34
910 11
22
12
8 8 9
14
9
14
6 6 68
79
4 4 4 5 46
3 2 3 3 3 3
45
22
Perfect disambiguation (HW), 1K Selective Prediction, 16 entry return, 64 registers, issue as many as window
Integer: 6 - 12
FP: 8 - 45
IPC
Estudio más Realista
64 16256Infinite 32128 8 4
5Cluster Computing
Alternativas Cómputo Paralelo
Alternativa al cómputo de alto rendimiento
Computadoras Paralelas Multiprocesadores Multicomputadoras Alto Costo
Cluster Computing Rendimiento comparable al de arquitecturas paralelas Bajo costo
Antecedentes Históricos PVM Beowulf MPI
6Cluster Computing
Cluster Computing
P M
C
P M
C
P M
C
Red de Interconexión
7Cluster Computing
Diseño de Arquitecturas Paralelas
Objetivo: Tener un sistema balanceado en cuanto a
cómputo,acceso a memoria,red de interconexión, ymecanismos de sincronización
8Cluster Computing
Ejecución de Programas Paralelos
P1P0 P2 P3
Tiempo
Cómputo
Sincronización
Comunicación
Ocio
Tp = Tcómputo + Tcomunicación + Tsincronización + Tocio
}{ pPp
total TmaxT
p
s
TT
S*
9Cluster Computing
Tiempo de Ejecución Tiempo de cómputo
Inherente al problema
Tiempo de ocio Diseño del programa o algoritmo
Tiempo de comunicación Patrones de comunicación bien definidos Comunicación punto a punto Comunicación colectiva Características de la arquitectura
Tiempo de sincronización Diseño del programa o algoritmo Características de la arquitectura
10Cluster Computing
Comunicación
send();
Proceso 1
recv();
Proceso 2
buffer del mensajeTiempoProcesocontinúa Lee el buffer
del mensaje
LatenciaTiempo de arranque de las comunicaciones
Ancho de bandaVelocidad para transferir una unidad de datos
11Cluster Computing
Broadcast
Proceso 1
bcast(); bcast();
Proceso 2
bcast();
Proceso n
12Cluster Computing
Reducción
Proceso 2
reduce();
Proceso 1
reduce();
Proceso n
reduce();
+
13Cluster Computing
Scatter
Proceso 2
scatter();
Proceso n
scatter();
Proceso 1
scatter();
14Cluster Computing
Gather
Proceso 2
gather();
Proceso 1
gather();
Proceso n
gather();
15Cluster Computing
Sincronización
P0 P1 P2 Pn-1
Tiempo
Activo
EsperandoBarrera
16Cluster Computing
Configuraciones Evaluadas
Cluster de 8 Computadoras Pentium II 450 MhzSwitch FastEthernet 100 MbpsHub FastEthernet 100 Mbps
SP2: 8 procesadores POWER2 Super Chip 120 MhzSwitch Lucent Technologies 122 MBpsEthernet 10 Mbps
17Cluster Computing
Cluster y SP2
18Cluster Computing
Cluster y SP2 Switches
19Cluster Computing
Pruebas de RendimientoComunicación punto a punto: Un par
Latencia y ancho de banda pico
Comunicación punto a punto: Pares simultáneosContención y congestión en la red
Operaciones colectivasBroadcastReduceScatterGather
Operación de SincronizaciónBarrera
20Cluster Computing
Casos de Estudio
Multiplicación de matricesAplicación aritmética entera
Solución de sistemas de ecuaciones linealesAplicación con un balance entre aritmética
entera y de punto flotante
Transformada rápida de FourierAplicación dominada por la aritmética de
punto flotante
21Cluster Computing
Comunicación Punto a PuntoTiempo de Comunicación
0.0001
0.001
0.01
0.1
1
10
1 10 100 1000 10000 100000 1000000
Longitud del Mensaje
Tie
mp
o d
e T
ran
sm
isió
n (
se
gs
.)
Switch FastEth
Hub FastEth
Switch SP2
Ethernet SP2
22Cluster Computing
Comunicación Punto a PuntoPares de Comunicación
0.0001
0.001
0.01
0.1
1
10
100
1 10 100 1000 10000 100000 1000000
Longitud del Mensaje
Ba
nd
wid
th (
Mb
ps
)
Switch FastEth
Hub FastEth
Switch SP2
Ethernet SP2
23Cluster Computing
ContenciónPares de Comunicación
0.0001
0.001
0.01
0.1
1
10
1 10 100 1000 10000 100000 1000000
Longitud del Mensaje
Tie
mp
o d
e T
ran
sm
isió
n (
se
gs
.)
Switch FastEth
Hub FastEth
Switch SP2
Ethernet SP2
24Cluster Computing
ContenciónPares de Comunicación
0.0001
0.001
0.01
0.1
1
10
100
1 10 100 1000 10000 100000 1000000
Longitud del Mensaje
Ba
nd
wid
th (
Mb
ps
)
Switch FastEth
Hub FastEth
Switch SP2
Ethernet SP2
25Cluster Computing
BroadcastBroadcast
0.0001
0.001
0.01
0.1
1
10
2 3 4 5 6 7 8
Número de Procesadores
Tie
mp
o d
e T
ran
sm
isió
n (
se
gs
.)
Switch FastEth
Hub FastEth
Switch SP2
Ethernet SP2
26Cluster Computing
ReducciónReduce
0.0001
0.001
0.01
0.1
1
10
2 3 4 5 6 7 8
Número de Procesadores
Tie
mp
o d
e T
ran
sm
isió
n (
se
gs
.)
Switch FastEth
Hub FastEth
Switch SP2
Ethernet SP2
27Cluster Computing
ScatterScatter
0.0001
0.001
0.01
0.1
1
10
2 3 4 5 6 7 8
Número de Procesadores
Tie
mp
o d
e T
ran
sm
isió
n (
se
gs
.)
Switch FastEth
Hub FastEth
Switch SP2
Ethernet SP2
28Cluster Computing
GatherGather
0.0001
0.001
0.01
0.1
1
10
2 3 4 5 6 7 8
Número de Procesadores
Tie
mp
o d
e T
ran
sm
isió
n (
se
gs
.)
Switch FastEth
Hub FastEth
Switch SP2
Ethernet SP2
29Cluster Computing
SincronizaciónSincronización
0.0001
0.001
0.01
0.1
2 3 4 5 6 7 8
Número de Procesadores
Tie
mp
o d
e T
ran
sm
isió
n (
se
gs
.)
Switch FastEth
Hub FastEth
Switch SP2
Ethernet SP2
30Cluster Computing
Parámetros Observados
Descripción Latencia BW (unpar)
BW (variospares)
Switch 100Mbps
197 seg 76.8 Mbps 62.4 Mbps
Hub 100 Mbps 190 seg 70.4 Mbps 16.9 Mbps
Switch SP2976 Mbps
321 seg 78.4 Mbps 74.9 Mbps
Hub 10 Mbps 455 seg 7.6 Mbps 1.84 Mbps
31Cluster Computing
Multiplicación de Matrices
IBM SP2 vs Beowulf Multiplicación de Matrices.
0.0
1.0
2.0
3.0
4.0
5.0
6.0
7.0
8.0
9.0
1 2 3 4 5 6 7 8
Procesadores (p)
Ac
ele
rac
ión
(S
)
Ideal
Beowulf
IBM SP2
n=1024
32Cluster Computing
Eliminación Gaussiana
IBM SP2 vs Beowulf Eliminación Gaussiana.
0.0
1.0
2.0
3.0
4.0
5.0
6.0
7.0
8.0
9.0
1 2 3 4 5 6 7 8
Procesadores (p)
Ac
ele
rac
ión
(S
)
Ideal
Beowulf
IBM SP2
n=512
33Cluster Computing
Transformada Rápida de Fourier
IBM SP2 vs Beowulf Transformada Rápida de Fourier.
0.0
1.0
2.0
3.0
4.0
5.0
6.0
7.0
8.0
9.0
1 2 3 4 5 6 7 8
Procesadores (p)
Ac
ele
rac
ión
(S
)
Ideal
Beowulf
IBM SP2
n=512
34Cluster Computing
Conclusiones
El rendimiento del cluster es, en términos generales, comparable al de la SP2Balance entre cómputo con aritmética entera
y aritmética de punto flotanteDebido a la arquitectura de los
procesadoresPara aplicaciones intensivas en cómputo con
punto flotante se pueden usar procesadores más adecuados
35Cluster Computing
ConclusionesLos parámetros de comunicación
observados son inferiores a los especificados debido al trabajo adicional
El rendimiento en las comunicaciones es comparable entre las dos arquitecturas para mensajes cortos y moderadosPara mensajes suficientemente largos, el switch de la
SP2 empieza a reportar un comportamiento mejor al de los dispositivos de comunicación convencionales
Es necesario hacer una trabajo de caracterización para cada cluster construidoPermite sintonizar los parámetros de cada instalación