Balance de Carga Adaptable bajo
Cómputo Paralelo en Clusters
Miguel A. Castro García
Directores
Jorge Buenabad Chávez (CINVESTAV)
Graciela Román Alonso (UAMI)
Contenido
Antecedentes
 Planteamiento del problema
 Objetivo
 Soluciones reportadas por otros autores
 Soluciones propuestas en la investigación
 Resultados
 Publicaciones
 Trabajo futuro y conclusiones

03/10/2015 02:26 p.m.
Seminario de Doctorado 2003
Sección Computación
2
Antecedentes (1)

Demanda de cómputo

Predicción del clima

Evolución de galaxias
03/10/2015 02:26 p.m.
Seminario de Doctorado 2003
Sección Computación
3
Antecedentes (2)

Cómputo paralelo
03/10/2015 02:26 p.m.
Seminario de Doctorado 2003
Sección Computación
4
Antecedentes (3)

Taxonomía de Flynn

SIMD (Single Instruction Multiple Data)





Aplicaciones específicas
Arreglos de procesadores específicos
Una unidad de control
Costo Alto
MIMD (Multiple Instruction Multiple Data)





Aplicaciones generales
Hardware de comunicación específico
Altamente Costosas
Varias unidades de control
Alguien se debe encargar de la asignación de carga
03/10/2015 02:26 p.m.
Seminario de Doctorado 2003
Sección Computación
5
Antecedentes (4)

Arquitecturas MIMD

Shared Memory Multiprocessor System


Message-Passing Multicomputer


Intel Paragon, IBM SP-2
Distributed Shared Memory


Pentium “quad pack”, Cray T3E
AP3000 Fujitsu
Modelos de programación


Memoria compartida
Intercambio de mensajes
03/10/2015 02:26 p.m.
Seminario de Doctorado 2003
Sección Computación
6
Clusters

Arquitectura
1
pacífico1
2
pacífico2
8
pacífico8
9
pacífico9
Linux
Linux
Linux
Linux
bus

Características



Precio menor
Componentes de propósito general
Escalables
03/10/2015 02:26 p.m.
Seminario de Doctorado 2003
Sección Computación
7
Pregunta

¿Basta con tener un cluster para hacer
cómputo paralelo?
03/10/2015 02:26 p.m.
Seminario de Doctorado 2003
Sección Computación
8
Problema de la Asignación de Carga
aplicación
divide
N procesos
M procesadores
03/10/2015 02:26 p.m.
Seminario de Doctorado 2003
Sección Computación
9
Problema de la Asignación de Carga
Conjunto de
datos de la
aplicación
divide
N datos
M procesadores
1 proceso por procesador
03/10/2015 02:26 p.m.
Seminario de Doctorado 2003
Sección Computación
10
Tipos de Asignación (1)


Características de la aplicación
Características de la arquitectura
Asignación Estática

Ej. Suma de matrices
111
222
03/10/2015 02:26 p.m.
+
444
666
=
Seminario de Doctorado 2003
Sección Computación
555
888
11
Tipos de Asignación (2)



Uso del procesador de manera no determinista
Cluster heterogéneo
Multiusuario
Asignación Dinámica
03/10/2015 02:26 p.m.
Seminario de Doctorado 2003
Sección Computación
12
Ejemplo de una aplicación paralela
Se tiene un conjunto de datos
Se dividen los datos equitativamente entre los nodos
Repite
{
Hacer cálculos sobre los datos
Se comunican todos en un punto
}
Pero……
La cantidad de datos aumenta o disminuye
El tiempo de procesamiento de cada dato es diferente
03/10/2015 02:26 p.m.
Seminario de Doctorado 2003
Sección Computación
13
Balance de carga (1)

Definición

Redistribución de tareas balanceando
la carga de los nodos para lograr un
mejor rendimiento
03/10/2015 02:26 p.m.
Seminario de Doctorado 2003
Sección Computación
14
Balance de carga (2)

global
Elemento de información
parcial

Elemento de control
centralizado
distribuido
tipo de elementos  tipo de algoritmo
03/10/2015 02:26 p.m.
Seminario de Doctorado 2003
Sección Computación
15
Balance de carga (3)

Métricas

Frecuencia de colecta de información
03/10/2015 02:26 p.m.
Seminario de Doctorado 2003
Sección Computación
16
Balance de carga (4)

Métricas

Fronteras de carga
F1
descargado
descargado
recibir carga
03/10/2015 02:26 p.m.
F
F2
carga sobrecargado
sobrecargado
normal
transferir carga
Seminario de Doctorado 2003
Sección Computación
% uso del
procesador
17
Balance de carga (5)

Algoritmo adaptable


Automático
Tiempo de ejecución
F1
descargado
F2
sobre
carga
carga sobrecargado
cargado
normal
normal
% uso del
procesador
03/10/2015 02:26 p.m.
Seminario de Doctorado 2003
Sección Computación
18
Parámetros
Frecuencia de colecta de información
 Fronteras de carga

03/10/2015 02:26 p.m.
Seminario de Doctorado 2003
Sección Computación
19
Objetivo

Desarrollo de un servicio de balance de
datos adaptable en clusters para
aplicaciones irregulares: Adaptive Load
Balancing Service (ALBS)
03/10/2015 02:26 p.m.
Seminario de Doctorado 2003
Sección Computación
20
Soluciones reportadas por otros autores

Herramientas que hacen balance
Nivel
MOSIX
Tipo de
carga
Tipo de algoritmo
Info
Control
Adaptable
Prog.
Paralela
S.O
procesos
parcial
distribuido
√
X
PVM
aplicación
procesos
X
centralizado
X
√
MPI
aplicación
procesos
X
X
X
√
ATHAPASCAN
aplicación
hilos
global
centralizado
X
√
ZOLTAN
aplicación
datos
X
√
POOGAL
aplicación
datos
√
X
03/10/2015 02:26 p.m.
varios
global
centralizado
Seminario de Doctorado 2003
Sección Computación
21
Propuesta (1)

Creación de un mecanismo de balance de
datos de fácil uso para aplicaciones
irregulares
Se tiene un conjunto de datos
Se dividen los datos equitativamente entre los nodos
Repite
{
Hacer cálculos sobre los datos
Se comunican todos en un punto
BALANCEAR DATOS()
}
03/10/2015 02:26 p.m.
Seminario de Doctorado 2003
Sección Computación
22
Propuesta de Interfaz entre el balance y
la aplicación dinámica (2)
Se tiene un conjunto de datos
Se dividen los datos equitativamente entre los nodos
Repite
{
Hacer cálculos sobre los datos
Enviar conjunto de datos a balancear(mínimomáximo)
Se comunican todos en un punto
Recibir conjunto de datos balanceados()
}
03/10/2015 02:26 p.m.
Seminario de Doctorado 2003
Sección Computación
23
Propuesta del mecanismo de balance
Nodo A
Nodo B
Aplicación
Aplicación
Datos
Datos
Datos
Distribuidor
Contabilizador
Distribuidor
Administrador
Estado de
carga local
03/10/2015 02:26 p.m.
Administrador
Estados de
carga remota
Seminario de Doctorado 2003
Sección Computación
Contabilizador
Estado de
carga local
24
Plataforma de comparación

MPI


Athapascan




Balance de procesos
Balance de hilos
Sincronización
MPI
ALBS (Adaptive Load Balancing Service)




Balance datos
1 proceso por procesador
Paso de Mensajes
MPI
03/10/2015 02:26 p.m.
Seminario de Doctorado 2003
Sección Computación
25
Resultados (1)

Algoritmo evolutivo paralelo
Tiempo (segundos)
Cluster dedicado
120
115
110
105
100
95
90
85
80
sin balance
con balance
1 2 3 4 5 6 7 8 9 10
Corridas
03/10/2015 02:26 p.m.
Seminario de Doctorado 2003
Sección Computación
26
Resultados (2)

Algoritmo evolutivo paralelo
Tiempo (segundos)
Cluster no dedicado
220
200
180
sin balance
160
con balance
140
120
100
1 2 3 4 5 6 7 8 9 10
Corridas
03/10/2015 02:26 p.m.
Seminario de Doctorado 2003
Sección Computación
27
Publicaciones
Servicio de balance de carga, LAFMI,
Primera Escuela Franco-Mexicana de
Sistemas Distribuidos, Jalapa Ver. (2002)
 Integration of a Load Balancing
Mechanism into a Parallel Evolutionary
Algorithm(ISSADS 2004), Guadalajara Jal.
(consideración)
 Load Balancing for Image Processing
Applications (PDCS 2004), San Francisco
Cal.(proceso)

03/10/2015 02:26 p.m.
Seminario de Doctorado 2003
Sección Computación
28
¿Qué esta hecho y qué hace falta?
1. Estudio y Evaluación de las herramientas Zoltan, Athapascan, etc. así
como el tipo de aplicaciones que se ejecutan en estas
2. Diseño del servicio de asignación y balance de carga
3. Construcción del servicio
4. Construcción del ambiente de comparación
5. Evaluación del desempeño del servicio
6. Elaboración de reportes y escritura de la Tesis
7. Revisión y Corrección de Tesis
1 Cuat.
2003
2 Cuat.
2003
3 Cuat.
2003
1 Cuat.
2004
2 Cuat.
2004
3 Cuat.
2004
1 Cuat.
2005
1, 2
2, 3
3, 4
4, 5
5, 6
5, 6, 7
6, 7
03/10/2015 02:26 p.m.
Seminario de Doctorado 2003
Sección Computación
29
Conclusiones
Se presentó una propuesta de balance de
datos para aplicaciones irregulares
 Es conveniente tener un servicio adaptable
de balance de carga
 El servicio se puede extender a otro tipo
de aplicaciones
 Se consideró una plataforma de
comparación en base a balance de
procesos, hilos y datos para aplicaciones
irregulares

03/10/2015 02:26 p.m.
Seminario de Doctorado 2003
Sección Computación
30
Descargar

Servicio de Balance de Carga Adaptable para Arquitecturas