Estudo Comparativo de Técnicas de Escalonamento de Tarefas ...alvaroma/mestrado/disertacao/slides.pdf · Estudo Comparativo de T ecnicas de Escalonamento de Tarefas Dependentes para

Estudo Comparativo de Tecnicas de Escalonamento deTarefas Dependentes para Grades Computacionais

CandidatoAlvaro Henry Mamani Aliaga1

OrientadorAlfredo Goldman

Instituto de Matematica e EstatısticaDepartamento de Ciencia da Computacao

Universidade de Sao Paulo

[email protected]

22 de Agosto de 2011

1O aluno recebeu apoio financeiro do CNPq, processo 133147/2009-6

Roteiro

1 Introducao

2 Arquiteturas

3 Aplicacoes

4 Simulador

5 Algoritmos de Escalonamento

6 Metodologia

7 Resultados Experimentais

8 Conclusoes e Trabalhos Futuros

A. H. Mamani-Aliaga (IME-USP) Defesa de Mestrado 2 / 66

1 Introducao

2 Arquiteturas

3 Aplicacoes

4 Simulador


6 Metodologia




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


Escalonadores

EscalonadoresI OARI CondorI Torque

MiddlewaresI BoincI InteGradeI OurGridI XtremWeb


Escalonadores

EscalonadoresI OARI CondorI Torque

MiddlewaresI BoincI InteGradeI OurGrid

Algoritmos de Escalonamento

F WorkqueueF Workqueue with ReplicationF Storage Affinity

I XtremWeb


Motivacao

Necessidade de grande capacidade de processamento

Uso correto da capacidade do processamento

Escalonamento e um grande desafio pelas caracterısticas da grade

Varias abordagens de escalonamento propostas

O escalonamento em middlewares geralmente usa polıticas deescalonamento basicas


Objetivos

Objetivo geralI Comparar tecnicas de escalonamento para grades computacionais sobre

diferentes cenarios

Objetivos especıficosI Propor uma metodologia que baseada em caracterısticas tanto das

aplicacoes quanto das arquiteturas da grade seja possıvel decidir qualalgoritmo oferece melhor desempenho

I Determinar se para um dado tipo de aplicacao e possıvel umacomparacao usando escalabilidade


1 Introducao

2 Arquiteturas

3 Aplicacoes

4 Simulador


6 Metodologia




DAS-3

Distributed ASCISupercomputer 3

Arquitetura compostapor cinco aglomeradosheterogeneosgeograficamentedistribuıdos pelaHolanda

Possui 272processadores


Grid5000

Arquiteturacientıfica criadapara o estudo desistemas paralelos edistribuıdos de largaescala espalhadospelo territoriofrances

Possui mais de5000 processadores

Nos experimentossao usados 462processadores,agrupados em dozeaglomerados


GridPP

E uma arquiteturacolaborativa entrefısicos e cientistasda computacao de19 universidades doReino Unido, olaboratorioRutherford e oCERN

Possui mais de7948 processadores

Nos experimentossao usados 900processadores,agrupados em trezeaglomerados


SmallGrid

Caracterısticas da Arquitetura

Foram especificados dois aglomerados, com duas instancias:homogenea e heterogenea


SmallGrid

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 5,00A2-06 5,00 6,00A2-07 5,00 7,00A2-08 5,00 8,00A2-09 5,00 9,00


1 Introducao

2 Arquiteturas

3 Aplicacoes

4 Simulador


6 Metodologia




Aplicacoes

Montage

E usada para gerarmosaicos personalizadosdo ceu usando pontos demultiplas imagens deentrada


Aplicacoes

CyberShake

O projeto tem comoproposito calcular eanalisar os riscos deterremoto usando tecnicasde analise probabilısticade risco sısmico


Aplicacoes

Epigenomics

E usada no mapeamentodo estado epigenetico decelulas humanas sobreuma grande escalagenomica


Aplicacoes

Ligo

E usada para detectarondas gravitacionaisproduzidas por varioseventos no universo


1 Introducao

2 Arquiteturas

3 Aplicacoes

4 Simulador


6 Metodologia




Simulador SimGrid


Casanova, Henri and Legrand, Arnaud and Quinson, Martin, SimGrid: a GenericFramework for Large-Scale Distributed Experiments, IEEE Computer Society, 2008.

1 Introducao

2 Arquiteturas

3 Aplicacoes

4 Simulador


6 Metodologia




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 de 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


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


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


Bittencourt, Luiz F et Al., Uma Heurıstica de Agrupamento de Caminhos paraEscalonamento de Tarefas em Grades Computacionais, SBRC, 2006.

1 Introducao

2 Arquiteturas

3 Aplicacoes

4 Simulador


6 Metodologia




Analise das Aplicacoes

Distinguimos dois tipos: Aplicacao Regular e Aplicacao Irregular

Por cada aplicacao temos um conjunto de “tracos de execucao”(traces)

A soma dos tempos de execucao das tarefas (wi ) de um traco edenominada “carga do trabalho” (workload)

A carga de trabalho W (TA) de um traco de execucao de umaaplicacao TA de tamanho n e dado por:

W (TA) =n∑

i=1

wi







W (TA) =n∑

i=1

wi







W (TA) =n∑

i=1

wi



Dada uma aplicacao A, se TA,n e o conjunto de tracos de tamanho n,a media da carga do trabalho W (A, n) de uma aplicacao de cadainstancia de tamanho n e dado por:

W (A, n) =1

|TA,n|∑

T∈TA,n

W (T )

Dada uma aplicacao A, chamamos a aplicacao de irregular se ∃n,mcom n < m tal que W (A, n) > W (A,m)



Dada uma aplicacao A, se TA,n e o conjunto de tracos de tamanho n,a media da carga do trabalho W (A, n) de uma aplicacao de cadainstancia de tamanho n e dado por:

W (A, n) =1

|TA,n|∑

T∈TA,n

W (T )

Dada uma aplicacao A, chamamos a aplicacao de irregular se ∃n,mcom n < m tal que W (A, n) > W (A,m)



0.2

0.4

0.6

0.8

1

1.2

1.4

0 100 200 300 400 500 600 700 800 900 1000

log(W

(A,n

)/(W

(A,5

0))

)

Número de Tarefas

MontageCyberShakeEpigenomics

Ligo


Principais Questoes que Direcionam aos Experimentos

Criterio Metricas Questoes & Configuracoes

Desempenho A soma total dos Makespans Uma nocao geral do algoritmocom o melhor desempenho

Escalabilidade Media do Makespan pelonumero de tarefas e nos dagrade

A avaliacao e feita paraaplicacoes regulares sobre todasas grades

Adaptabilidade Taxa entre o total doMakespan por grade e poraplicacao

O intuito e identificar quais algo-ritmos sao mais adaptativos so-bre diferentes arquiteturas

Distribuicao daCarga do Tra-balho

Numero de tarefas por nosda grade e tempo necessariopara a comunicacao entreelas

O intuito e entender qual algo-ritmo e o melhor na distribuicaoda carga do trabalho


1 Introducao

2 Arquiteturas

3 Aplicacoes

4 Simulador


6 Metodologia




Desempenho - SmallGrid Homogenea

5

5.5

6

6.5

7

7.5

MONTAGE CYBERSHAKE EPIGENOMICS LIGO

log(s

um

(makespans))

HEFTCPOP

PCH


Desempenho - SmallGrid Heterogenea

5

5.5

6

6.5

7

7.5


log(s

um

(makespans))

HEFTCPOP

PCH


Desempenho - DAS-3

4.5

5

5.5

6

6.5

7


log(s

um

(makespans))

HEFTCPOP

PCH


Desempenho - Grid5000

4.5

5

5.5

6

6.5

7


log(s

um

(makespans))

HEFTCPOP

PCH


Desempenho - GridPP

4.5

5

5.5

6

6.5

7


log(s

um

(makespans))

HEFTCPOP

PCH


Escalabilidade: (i) Montage - SmallGrid Homogenea

0

200

400

600

800

1000

1200

1400

0 100 200 300 400 500 600 700 800 900 1000

Makespan

Número de Tarefas

HEFTCPOP

PCH


Escalabilidade: (i) Montage - SmallGrid Heterogenea

0

200

400

600

800

1000

1200

1400

0 100 200 300 400 500 600 700 800 900 1000

Makespan

Número de Tarefas

HEFTCPOP

PCH


Escalabilidade: (i) Montage - DAS-3

0

100

200

300

400

500

600

700

0 100 200 300 400 500 600 700 800 900 1000

Makespan

Número de Tarefas

HEFTCPOP

PCH


Escalabilidade: (i) Montage - Grid5000

0

100

200

300

400

500

600

700

0 100 200 300 400 500 600 700 800 900 1000

Makespan

Número de Tarefas

HEFTCPOP

PCH


Escalabilidade: (i) Montage - GridPP

0

100

200

300

400

500

600

700

0 100 200 300 400 500 600 700 800 900 1000

Makespan

Número de Tarefas

HEFTCPOP

PCH


Escalabilidade: (i) CyberShake - SmallGrid Homogenea

0

20000

40000

60000

80000

100000

120000

140000

0 100 200 300 400 500 600 700 800 900 1000

Makespan

Número de Tarefas

HEFTCPOP

PCH


Escalabilidade: (i) CyberShake - SmallGrid Heterogenea

0

20000

40000

60000

80000

100000

120000

140000

0 100 200 300 400 500 600 700 800 900 1000

Makespan

Número de Tarefas

HEFTCPOP

PCH


Escalabilidade: (i) CyberShake - DAS-3

1000

1500

2000

2500

3000

3500

4000

4500

5000

0 100 200 300 400 500 600 700 800 900 1000

Makespan

Número de Tarefas

HEFTCPOP

PCH


Escalabilidade: (i) CyberShake - Grid5000

1000

1500

2000

2500

3000

3500

4000

4500

5000

0 100 200 300 400 500 600 700 800 900 1000

Makespan

Número de Tarefas

HEFTCPOP

PCH


Escalabilidade: (i) CyberShake - GridPP

1000

1500

2000

2500

3000

3500

4000

4500

5000

0 100 200 300 400 500 600 700 800 900 1000

Makespan

Número de Tarefas

HEFTCPOP

PCH


Escalabilidade: (i) Ligo - SmallGrid Homogenea

0

5000

10000

15000

20000

25000

0 100 200 300 400 500 600 700 800 900 1000

Makespan

Número de Tarefas

HEFTCPOP

PCH


Escalabilidade: (i) Ligo - SmallGrid Heterogenea

0

5000

10000

15000

20000

25000

0 100 200 300 400 500 600 700 800 900 1000

Makespan

Número de Tarefas

HEFTCPOP

PCH


Escalabilidade: (i) Ligo - DAS-3

1000

1500

2000

2500

3000

3500

4000

4500

0 100 200 300 400 500 600 700 800 900 1000

Makespan

Número de Tarefas

HEFTCPOP

PCH


Escalabilidade: (i) Ligo - Grid5000

1000

1500

2000

2500

3000

3500

4000

4500

0 100 200 300 400 500 600 700 800 900 1000

Makespan

Número de Tarefas

HEFTCPOP

PCH


Escalabilidade: (i) Ligo - GridPP

1000

1500

2000

2500

3000

3500

4000

4500

0 100 200 300 400 500 600 700 800 900 1000

Makespan

Número de Tarefas

HEFTCPOP

PCH


Adaptabilidade

HEFT (Das3, G5k) (G5k, Gpp)

Montage 1,65 0,76CyberShake 0,59 0,93Epigenomics 1,68 0,74Ligo 1,82 0,70

CPOP (Das3, G5k) (G5k, Gpp)


PCH (Das3, G5k) (G5k, Gpp)



Distribuicao da Carga de TrabalhoMontage - DAS-3 - HEFT


Distribuicao da Carga de TrabalhoMontage - DAS-3 - CPOP


Distribuicao da Carga de TrabalhoMontage - DAS-3 - PCH


Distribuicao da Carga de TrabalhoMontage - Grid5000 - HEFT


Distribuicao da Carga de TrabalhoMontage - Grid5000 - CPOP


Distribuicao da Carga de TrabalhoMontage - Grid5000 - PCH


Distribuicao da Carga de TrabalhoLigo - DAS-3 - HEFT


Distribuicao da Carga de TrabalhoLigo - DAS-3 - CPOP


Distribuicao da Carga de TrabalhoLigo - DAS-3 - PCH


1 Introducao

2 Arquiteturas

3 Aplicacoes

4 Simulador


6 Metodologia




Conclusoes

Na literatura foram propostos diferentes algoritmos de escalonamento

A escolha de um algoritmo de escalonamento que tenha ascaracterısticas necessarias para obter um desempenho bom em umdeterminado cenario e indispensavel

Ao comparar algoritmos de escalonamento deve seguir principalmentequatro criterios:

I DesempenhoI EscalabilidadeI AdaptabilidadeI Distribuicao da Carga do Trabalho

E importante entender e saber qual e o tipo de aplicacao, pode ser dedois tipos: Aplicacao Regular e Aplicacao Irregular

Em aplicacoes irregulares e mais difıcil medir escalabilidade


Conclusoes

O algoritmo HEFT possui um bom desempenho na maioria dos casos,apresentando uma estabilidade

Os algoritmos CPOP e PCH, apresentaram um desempenho bomsobre determinadas circunstancias

No caso do algoritmo CPOP possui uma dependencia sobre aestrutura da aplicacao e da arquitetura, dado que escalona as tarefasdo caminho crıtico

O algoritmo PCH agrupa as tarefas e escalona cada grupo noprocessador que oferece o melhor tempo de termino. Esse criterioperde sentido em tipos de aplicacoes com tarefas de sincronizacaocrıtica


Contribuicoes

1 Classificacao dos tipos de aplicacoes para grade com tarefasdependentes: (i) regulares e (ii) irregulares

2 Uma metodologia para fazer comparacao de algoritmos deescalonamento, baseado em determinadas configuracoes e metricas

3 Atualizacao, modelagem e especificacao para a simulacao dasarquiteturas para grade: (i) DAS-3, (ii) Grid5000 e (iii) GridPP, sobreo simulador SimGrid v3.5

4 Repositorio de imagens dos resultados do escalonamento, criadas nassimulacoes dos algoritmos


Trabalhos Futuros

Sugerimos ter um maior conjunto de aplicacoes, tanto em tamanhoquanto em forma da estrutura. Como uma alternativa existe o uso deum gerador randomico de grafos de aplicacoes

Arquiteturas com processadores com varios nucleos, este tipo deexperimentos nao foi abordado pelo fato do simulador ainda naosuportar este tipo de arquiteturas


Muito Obrigado

Orientador Alfredo Goldman

Banca: Profa. Dra. Liria Matsumoto Sato e Prof. Dr. PhilippeNavaux

Projeto SimGrid e Projeto Pegasus

Famılia e amigos ( , , , )

Colegas do LCPD

Ao IME(professores e funcionarios).


Documents

Estudo Comparativo de Técnicas de Escalonamento de Tarefas ...alvaroma/mestrado/disertacao/slides.pdf · Estudo Comparativo de T ecnicas de Escalonamento de Tarefas Dependentes para