Estudo Comparativo de Algoritmos de Escalonamento para ...alvaroma/pdf/erad11_slides.pdf · para...

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