Embed Size (px)
Citation preview
Estudo Comparativo de Algoritmos de Escalonamentopara Grades Computacionais
Alvaro Henry Mamani Aliaga e Alfredo Goldman
Instituto de Matematica e EstatısticaDepartamento de Ciencia da Computacao
Universidade de Sao Paulo
{alvaroma,gold}@ime.usp.br
II Escola Regional de Alto Desempenho de Sao Paulo
Julho, 2011
Roteiro
1 Introducao
2 Algoritmos de Escalonamento
3 Aplicacoes
4 Arquitetura
5 Simulador
6 Resultados Experimentais
7 Conclusoes e Trabalhos Futuros
A. Mamani-Aliaga, A. Goldman (IME-USP) Compatacao de Algoritmos para Grades Julho 2011 2 / 27
1 Introducao
2 Algoritmos de Escalonamento
3 Aplicacoes
4 Arquitetura
5 Simulador
6 Resultados Experimentais
7 Conclusoes e Trabalhos Futuros
A. Mamani-Aliaga, A. Goldman (IME-USP) Compatacao de Algoritmos para Grades Julho 2011 3 / 27
Introducao
Necessidade de poder computacional: mineracao de dados, previsaodo tempo, processamento de imagens medicas, . . .
Aumento na disponibilidade de computadores poderosos e nainterligacao de redes de alta velocidade
Computacao em gradeUma alternativa para obter grande capacidade processamento
Escalonamento de tarefas consiste em alocar tarefas de uma aplicacaoem recursos computacionais, com o intuito de minimizar o Makespan
Aplicacoes com tarefas dependentes sao modeladas mediante umgrafo acıclico dirigido, G = (V ,E ), onde, G representa o DAG, V oconjunto de tarefas t e E o conjunto de dependencias entre cadatarefa da aplicacao
A. Mamani-Aliaga, A. Goldman (IME-USP) Compatacao de Algoritmos para Grades Julho 2011 4 / 27
1 Introducao
2 Algoritmos de Escalonamento
3 Aplicacoes
4 Arquitetura
5 Simulador
6 Resultados Experimentais
7 Conclusoes e Trabalhos Futuros
A. Mamani-Aliaga, A. Goldman (IME-USP) Compatacao de Algoritmos para Grades Julho 2011 5 / 27
HEFT, Heterogeneous Earliest Finish Time
Priorizacao de tarefas
Atribuir prioridade as tarefas
Calculo da prioridade, baseado na media dos custos de computacao ecustos de comunicacao
lista das tarefas
Selecao de recursos
Selecionar a tarefa ti da lista com maior prioridade
Para cada recurso r ∈ R e calculado o EST e EFT de cada tarefa ti
rj e alocada ao recurso que minimiza o EFT da tarefa ti
A. Mamani-Aliaga, A. Goldman (IME-USP) Compatacao de Algoritmos para Grades Julho 2011 6 / 27
Topcuouglu, Haluk et Al., Performance-Effective and Low-Complexity Task Schedulingfor Heterogeneous Computing, IEEE Trans. Parallel Distrib. Syst., 2002.
CPOP, Critical Path On a Processor
Priorizacao de tarefas
Atribuir prioridade as tarefas
Calculo das prioridades baseados no custo de computacao ecomunicacao
|CP| e o caminho crıtico
Selecao de recursos
PCP (critical-path processor)
Se a tarefa selecionada esta no caminho crıtico, entao e escalonadano recurso de caminho crıtico
ela e atribuıda a um recurso que minimiza o EFT
A. Mamani-Aliaga, A. Goldman (IME-USP) Compatacao de Algoritmos para Grades Julho 2011 7 / 27
Topcuouglu, Haluk et Al., Performance-Effective and Low-Complexity Task Schedulingfor Heterogeneous Computing, IEEE Trans. Parallel Distrib. Syst., 2002.
PCH, Path Clustering Heuristic
Selecao de tarefas e agrupamento
seleciona tarefas que formarao cada cluster que serao escalonadas nomesmo recurso
A primeira tarefa que compoe um cluster clsk e a tarefa naoescalonada com maior prioridade
Selecao de recursos
A selecao de recursos se da atraves do calculo de valores
qual recurso terminara a execucao do cluster em menor tempo
O fator que determina em qual recurso um cluster sera escalonado e oEST do sucessor da ultimo tarefa do cluster considerado
A. Mamani-Aliaga, A. Goldman (IME-USP) Compatacao de Algoritmos para Grades Julho 2011 8 / 27
Bittencourt, Luiz F et Al., Uma Heurıstica de Agrupamento de Caminhos paraEscalonamento de Tarefas em Grades Computacionais, SBRC, 2006.
1 Introducao
2 Algoritmos de Escalonamento
3 Aplicacoes
4 Arquitetura
5 Simulador
6 Resultados Experimentais
7 Conclusoes e Trabalhos Futuros
A. Mamani-Aliaga, A. Goldman (IME-USP) Compatacao de Algoritmos para Grades Julho 2011 9 / 27
Aplicacoes
Montage
E usada para gerarmosaicos personalizadosdo ceu usando pontos demultiplas imagens deentrada.
A. Mamani-Aliaga, A. Goldman (IME-USP) Compatacao de Algoritmos para Grades Julho 2011 10 / 27
Aplicacoes
Epigenomics
E usada no mapeamentodo estado epigenetico decelulas humanas sobreuma grande escalagenomica.
A. Mamani-Aliaga, A. Goldman (IME-USP) Compatacao de Algoritmos para Grades Julho 2011 11 / 27
1 Introducao
2 Algoritmos de Escalonamento
3 Aplicacoes
4 Arquitetura
5 Simulador
6 Resultados Experimentais
7 Conclusoes e Trabalhos Futuros
A. Mamani-Aliaga, A. Goldman (IME-USP) Compatacao de Algoritmos para Grades Julho 2011 12 / 27
Arquitetura
Caracterısticas da Arquitetura
Foram especificados dois aglomerados, com duas instancias:homogenea e heterogenea
Figura: Dois aglomerados usados na simulacao.
A. Mamani-Aliaga, A. Goldman (IME-USP) Compatacao de Algoritmos para Grades Julho 2011 13 / 27
Arquitetura
IdPoder Computacional (GFlops)Homogeneo Heterogeneo
A1-00 5,00 1,00A1-01 5,00 2,00A1-02 5,00 3,00A1-03 5,00 4,00A1-04 5,00 5,00A2-05 5,00 6,00A2-06 5,00 7,00A2-07 5,00 8,00A2-08 5,00 9,00A2-09 5,00 9,00
Tabela: Poder computacional dos recursos.
A. Mamani-Aliaga, A. Goldman (IME-USP) Compatacao de Algoritmos para Grades Julho 2011 14 / 27
1 Introducao
2 Algoritmos de Escalonamento
3 Aplicacoes
4 Arquitetura
5 Simulador
6 Resultados Experimentais
7 Conclusoes e Trabalhos Futuros
A. Mamani-Aliaga, A. Goldman (IME-USP) Compatacao de Algoritmos para Grades Julho 2011 15 / 27
Simulador SimGrid
A. Mamani-Aliaga, A. Goldman (IME-USP) Compatacao de Algoritmos para Grades Julho 2011 16 / 27
Casanova, Henri and Legrand, Arnaud and Quinson, Martin, SimGrid: a GenericFramework for Large-Scale Distributed Experiments, IEEE Computer Society, 2008.
1 Introducao
2 Algoritmos de Escalonamento
3 Aplicacoes
4 Arquitetura
5 Simulador
6 Resultados Experimentais
7 Conclusoes e Trabalhos Futuros
A. Mamani-Aliaga, A. Goldman (IME-USP) Compatacao de Algoritmos para Grades Julho 2011 17 / 27
Aplicacao Montage - Arquitetura Homogenea
0
200
400
600
800
1000
1200
1400
0 200 400 600 800 1000
Make
sp
an
# Tarefas
FIFOHEFTCPOP
PCH
Figura: Resultado da simulacao do Workflow Montage.
A. Mamani-Aliaga, A. Goldman (IME-USP) Compatacao de Algoritmos para Grades Julho 2011 18 / 27
Aplicacao Montage - Arquitetura Heterogenea
0
1000
2000
3000
4000
5000
6000
0 200 400 600 800 1000
Make
sp
an
# Tarefas
FIFOHEFTCPOP
PCH
Figura: Resultado da simulacao do Workflow Montage.
A. Mamani-Aliaga, A. Goldman (IME-USP) Compatacao de Algoritmos para Grades Julho 2011 19 / 27
Aplicacao Montage
Observamos que a estrategia FIFO somente apresenta bomdesempenho na arquitetura homogenea
O algoritmo PCH nao oferece bom desempenho em ambasarquiteturas
Os algoritmos HEFT e o CPOP apresentam bom desempenho emambas das arquiteturas com uma diferenca quase desprezıvel
A. Mamani-Aliaga, A. Goldman (IME-USP) Compatacao de Algoritmos para Grades Julho 2011 20 / 27
Aplicacao Epigenomics - Arquitetura Homogenea
0
50000
100000
150000
200000
250000
300000
350000
0 200 400 600 800 1000
Make
sp
an
# Tarefas
HEFTCPOP
PCH
Figura: Resultado da simulacao do Workflow Epigenomics.
A. Mamani-Aliaga, A. Goldman (IME-USP) Compatacao de Algoritmos para Grades Julho 2011 21 / 27
Aplicacao Epigenomics - Arquitetura Heterogenea
0
50000
100000
150000
200000
250000
300000
0 200 400 600 800 1000
Make
sp
an
# Tarefas
HEFTCPOP
PCH
Figura: Resultado da simulacao do Workflow Epigenomics.
A. Mamani-Aliaga, A. Goldman (IME-USP) Compatacao de Algoritmos para Grades Julho 2011 22 / 27
Aplicacao Epigenomics
O algoritmo PCH melhora o desempenho neste tipo de aplicacao.
O algoritmo CPOP conserva o bom desempenho em ambas dasarquiteturas.
O algoritmo HEFT apresenta bom desempenho na arquiteturaheterogenea, mas na arquitetura homogenea nao
A. Mamani-Aliaga, A. Goldman (IME-USP) Compatacao de Algoritmos para Grades Julho 2011 23 / 27
1 Introducao
2 Algoritmos de Escalonamento
3 Aplicacoes
4 Arquitetura
5 Simulador
6 Resultados Experimentais
7 Conclusoes e Trabalhos Futuros
A. Mamani-Aliaga, A. Goldman (IME-USP) Compatacao de Algoritmos para Grades Julho 2011 24 / 27
Conclusoes
Uma estrategia de tipo FIFO e adequada somente em arquiteturashomogeneas
Em arquiteturas heterogeneas e preciso um estudo tanto dos recursoscomputacionais quanto das tarefas
Os algoritmos HEFT e CPOP apresentaram desempenhos bons e aomesmo tempo similares na aplicacao Montage, enquanto o PCH nao
Em aplicacoes que possuem gargalos, como a aplicacao Montage, naoe conveniente o agrupamento de tarefas
A. Mamani-Aliaga, A. Goldman (IME-USP) Compatacao de Algoritmos para Grades Julho 2011 25 / 27
Trabalhos Futuros
E almejada a simulacao dos algoritmos em arquiteturas reais, porexemplo, DAS-3, Grid5000, GridPP, entre outras
Tambem, extensoes dos algoritmos para melhorar o desempenho emdeterminadas situacoes
A. Mamani-Aliaga, A. Goldman (IME-USP) Compatacao de Algoritmos para Grades Julho 2011 26 / 27
Muchas Gracias!!!
?Perguntas e sugestoes sao muito bem-vindas
A. Mamani-Aliaga, A. Goldman (IME-USP) Compatacao de Algoritmos para Grades Julho 2011 27 / 27
