4
Anais WSCAD 2005 Ambiente de Simulação de Escalonamento em Sistemas Distribuídos Hierárquicos Camilo Cardoso Figueira* Felipe Kraus* Cristina Boerest Instituto de Computação, Universidade Federal Fluminense (UFF) Niterói, RJ, Brasil {cfigueira,fkraus,boeres} @ic.uff:br Resumo Um dos objetivos de um escalonador de tarefas em um ambiente como as gr ades computacionais é a redução do tempo de execução da aplicação. Devi- do a distribuição geográfica dos recurs os da grade, faz-se necessário a criação de um sistema hierárquico de es- calonamento para que esses recursos possam ser explo- rados de forma eficiente. O sistema hierárquico adotado pelo projeto EasyGrid tem como base um escalona- mento htbrido, que mescla a utilização de escalonamen- to estáti co e dinâmico. Este trabalho propõe um ambiente de simulação de escalonamento dinâmico que visa aten- der estas necessidades, oferecendo uma ferramenta para desenvolvimento e análise de estrat égias de escalona- mento dinâmico e execução de aplicações em grades. 1. Introdução Atualmente, com a disseminação de redes de alta veloci- dade, é possível criar um ambiente computacional consti- tuído por um conjunto de computadores ou processadores heteroneos interconectados através desta rede e ofere- cer uma nova plataforma de computação: as Grades Com- putacionais [5, 6]. Nesses ambientes, é possível executar aplicações paralelas e distribuídas que necessitam de um alto poder computacional, poder este não disponível em um computador paralelo tradicional. As grades computacionais podem ser constituídas por c/usters de processadores, computadores pessoais, e até me smo supercomputadores, geograficamente dis- tribuídos. Em geral, esses ambientes possuem um grande número de processadores heterogêneos e comparti- lhados por diferentes usuários, sendo necessário que + Bolsistas de Iniciação Científica do CNPq/PIBIC (UFF) t Financiamento parcial com bolsa de Pesquisa - CNPQ 201 as aplicações dos usuários sejam cuidadosamente alo- cadas nos processadores distribuídos para se tirar proveito de toda essa potencialidade computacional. Para isso, é preciso implementar meios para tomar possível a execução de uma aplicação em um ambiente dis- tribuído de acordo com um escalonamento eficiente. Por ser o problema de escalonamento de aplicações, em sua forma geral, NP-Completo [9], toma-se necessário desen- volver heurísticas de escalonamento eficientes, assim como captar as características dominantes da aplicação e da ar- quitetura alvo. Entretanto, em computação distribuída, não se encontra disponível um modelo padrão de computa- dor distribuído em que as características que mais afetam o desempenho da execução de aplicações no sistema te- nham sido identificadas. Em linhas gerais, existem duas classes principais de escalonamento de tarefas em um ambiente dis- tribuído: estático e dinâmico. A diferença entre elas se dá de acordo com o momento em que as decisões do escalona- mento são tomadas. No escalonamento es tático, as decisões são efetuadas antes da execução da aplicação ser realiza- da, ou se ja, todas as tarefas são escalonadas antes do sis- tema iniciar a execução da aplicação. No escalonamento dinâmico, as decisões ocorrem ao longo da execução. Desta forma, na tentativa de minimizar o grau de intrusão do es- calonador na execução da aplicação, ele é acionado de tem- pos em tempos para escalonar parte da aplicação que ainda não foi executada. Esse processo se repete até comple- tar a execução de toda a aplicação. Uma terceira classe de escalonamento existente é o escalonamento híbrido, que é composto de duas etapas con- secutivas: a primeira de escalonamento estático e a segunda de escalonamento dinâmico. Esse escalonamento pos- s ui a vantagem de fornecer uma boa estimativa estática ini- cial do escalonamento, unido com a possível eficiência de um escalonador dinâmico de adaptar o escalona- mento em tempo de execução. Este trabalho descreve um framework para simulação de ambientes hierárquicos que utiliza escalonamento híbrido

Ambiente de Simulação de Escalonamento ... - lbd.dcc.ufmg.br · as seguintes características relevantes do sistema destino. Define-se como arquitetura P = ... plos considere a

Embed Size (px)

Citation preview

Anais WSCAD 2005

Ambiente de Simulação de Escalonamento em Sistemas Distribuídos Hierárquicos

Camilo Cardoso Figueira* Felipe Kraus* Cristina Boerest Instituto de Computação, Universidade Federal Fluminense (UFF)

Niterói, RJ, Brasil { cfigueira,fkraus,boeres} @ic.uff:br

Resumo

Um dos objetivos de um escalonador de tarefas em um ambiente como as grades computacionais é a redução do tempo de execução da aplicação. Devi­do a distribuição geográfica dos recursos da grade, faz-se necessário a criação de um sistema hierárquico de es­calonamento para que esses recursos possam ser explo­rados de forma eficiente. O sistema hierárquico adotado pelo projeto EasyGrid tem como base um escalona­mento htbrido, que mescla a utilização de escalonamen­to estático e dinâmico. Este trabalho propõe um ambiente de simulação de escalonamento dinâmico que visa aten­der estas necessidades, oferecendo uma ferramenta para desenvolvimento e análise de estratégias de escalona­mento dinâmico e execução de aplicações em grades.

1. Introdução

Atualmente, com a disseminação de redes de alta veloci­dade, é possível criar um ambiente computacional consti­tuído por um conjunto de computadores ou processadores heterogêneos interconectados através desta rede e ofere­cer uma nova plataforma de computação: as Grades Com­putacionais [5, 6]. Nesses ambientes, é possível executar aplicações paralelas e distribuídas que necessitam de um alto poder computacional, poder este não disponível em um computador paralelo tradicional.

As grades computacionais podem ser constituídas por c/usters de processadores, computadores pessoais, e até mesmo supercomputadores, geograficamente dis­tribuídos. Em geral, esses ambientes possuem um grande número de processadores heterogêneos e comparti­lhados por diferentes usuários, sendo necessário que

+ Bolsistas de Iniciação Científica do CNPq/PIBIC (UFF)

t Financiamento parcial com bolsa de Pesquisa - CNPQ

201

as aplicações dos usuários sejam cuidadosamente alo­cadas nos processadores distribuídos para se tirar proveito de toda essa potencialidade computacional.

Para isso, é preciso implementar meios para tomar possível a execução de uma aplicação em um ambiente dis­tribuído de acordo com um escalonamento eficiente. Por ser o problema de escalonamento de aplicações, em sua forma geral, NP-Completo [9], toma-se necessário desen­volver heurísticas de escalonamento eficientes, assim como captar as características dominantes da aplicação e da ar­quitetura alvo. Entretanto, em computação distribuída, não se encontra disponível um modelo padrão de computa­dor distribuído em que as características que mais afetam o desempenho da execução de aplicações no sistema te­nham sido identificadas.

Em linhas gerais, existem duas classes principais de escalonamento de tarefas em um ambiente dis­tribuído: estático e dinâmico. A diferença entre elas se dá de acordo com o momento em que as decisões do escalona­mento são tomadas. No escalonamento estático, as decisões são efetuadas antes da execução da aplicação ser realiza­da, ou seja, todas as tarefas são escalonadas antes do sis­tema iniciar a execução da aplicação. No escalonamento dinâmico, as decisões ocorrem ao longo da execução. Desta forma, na tentativa de minimizar o grau de intrusão do es­calonador na execução da aplicação, ele é acionado de tem­pos em tempos para escalonar parte da aplicação que ainda não foi executada. Esse processo se repete até comple­tar a execução de toda a aplicação.

Uma terceira classe de escalonamento existente é o escalonamento híbrido, que é composto de duas etapas con­secutivas: a primeira de escalonamento estático e a segunda de escalonamento dinâmico. Esse escalonamento pos­sui a vantagem de fornecer uma boa estimativa estática ini­cial do escalonamento, unido com a possível eficiência de um escalonador dinâmico de adaptar o escalona­mento em tempo de execução.

Este trabalho descreve um framework para simulação de ambientes hierárquicos que utiliza escalonamento híbrido

Anais WSCAD 2005

em grades computacionais. O objetivo principal é prover um ambiente de análise de diversas políticas de escalona­mento dinâmico.

2. O Portal EasyGrid

O trabalho proposto foi desenvolvido como parte da fer­ramenta de avaliação de algoritmos de escalonamento do Projeto EasyGrid, o Scheduling Portal (2, 4]. Nesse Por­tal, a execução de aplicações, de acordo com uma deter­minada polftica de escalonamento dinâmico, é realizada através de simulações. A ferramenta SimGrid [7. 3] foi uti­lizada para implementar a versão inicial do escalonador hibrido. Este trabalho tem como objetivo implementar a versão do simulador de escalonador hibrido distribuído, de forma hierárquica.

3. Modelos Considerados

A aplicação, a arquitetura e a política de escalonamen­to são dados necessários para a execução do simulador de escalonador hibrido. A implementação do ambiente de simulação conta ainda com uma ferramenta de simulação, o SimGrid, além das bibliotecas de comunicação através de threads (pthread.h) e a plataforma de comunicação MP/ [8].

As aplicações analisadas neste trabalho são repre­sentadas por um grafo acíclico direcionado (GAD). Um GAD é denotado por G = (V,E,E,w), onde V = { vo, v1 , .. . , Vn-d é o conjunto de vértices que repre­sentamas tarefaseE = {{v; ,vj) lvi , Vj E V} é o conjunto de arcos que representam as relações de precedência en­tre as tarefas. Denota-se por E( v;), o peso de execução de uma tarefa v; E V e por w( v; , v i), o peso de dados asso­ciado ao arco (v; , Vj) E E, que representa a quantidade de dados transmitida de v; para vi . A seguir serão descri­tas as classes de aplicações que foram utilizadas ao longo deste trabalho.

Árvores Binárias Completas ( Out-tree ). Represen­tam aplicações como difusão e divisão e conquista, onde os dados migram da raiz até as folhas.

Árvores Binárias Reversas Completas (ln-tree). Repre­sentam algoritmos em que os dados partem das folhas em direção à raiz havendo uma redução nas operações, como na soma em paralelo.

Diamantes (Di). É um bom representante de aplicações como decomposição LU e multiplicação de matrizes.

Randômicos (Ran). Estes grafos são gerados aleatoria­mente e têm como objetivo representar uma aplicação pa­ralela qualquer para que se possa avaliar o desempenho de uma heurística de escalonamento sobre grafos com estru­turas irregulares.

202

O modelo arquitetura! adotado neste trabalho especifica as seguintes características relevantes do sistema destino. Define-se como arquitetura P = {po, Pt , ... , Pq- d o con­junto de q processadores, sendo h(p;) o fator de hetero­geneidade do processador p;. Assim, o tempo de execução de uma tarefa vi em um processador p; é dada por E( Vj) x h(p;). Para duas tarefas u e v adjacentes que foram alo­cadas em processadores distintos Pu e Pv respectivamente, o custo de comunicação entre u e v será w( u, v ) x L, onde a latência L é o fator multiplicativo de comunicação em qual­quer canal do sistema. Esse atraso corresponde ao tempo de transmissão por byte em um canal de comunicação.

A fim de representar a hierarquia das grades computa­cionais, o sistema é modelado de tal maneira que os pro­cessadores alocados geograficamente próximos serão agru­pados em conjuntos. A cada conjunto de r processadores, r :5 q, totalmente interconectados será dado o nome de si te. Dentro de um site, apenas um processador estará apto a en­viar e receber mensagens de outros processadores fora do site. Tal processador deverá repassar estas mensagens para os demais processadores do site e também será responsável por algumas funções que serão vistas a seguir. ·

4. Framework de Escalonamento Hierárquico

Este trabalho descreve o simulador de Framework de Escalonamento Hierárquico, framework este pro­posto em [2], que visa viabilizar o escalonamento de aplicações paralelas em grades computacionais ten­tando diminuir o overhead dos custos de comunicação en­tre os processadores. Essa hierarquia possui três níveis dis­tintos, cada um com sua classe de escalonador. No primeiro nível da hierarquia de escalonamento existe apenas um pro­cesso, que será chamado de Escalonador Global. No segundo nível da hierarquia encontram-se os Escalonado­res Locais e, por último, no terceiro nível encontram-se os Escalonadores da Máquina. Cada escalonador pos­sui uma função distinta dentro da hierarquia de escalona­mento, cuja simulação será descrita a seguir. É importante lembrar que este trabalho trata da simulação desta pro­posta hierárquica e distribuída de escalonadores dinâmicos.

O Escalonador Global é um processo alocado em um único processador p; que conterá todas as informações necessárias ao escalonamento, tais como o escalonamento estático inicial, os processadores onde estão executando os Escalonadores Locais de cada site e a aplicação. O Escalo­nador Global comandará todo o escalonamento dinâmico, sendo posto em execução a cada evento de escalonamento (definido em [1]). Durante um evento de escalonamento, enquanto o Escalonador Global estiver executando, ele de­cidirá quais tarefas da aplicação serão re-escalonadas e em que sites essas tarefas deverão ser alocadas. Após tomar essa decisão, o Escalonador Global irá disparar uma thread

Anais WSCAD 2005

simulando um Escalonador Local, passando para elas as tarefas que deverão executar dentro de seus sites. A criação das threads (Escalonadores Locais) é implementado pela biblioteca pthread.h.

Os Escalonadores Locais são threads responsáveis pelo recebimento das tarefas a serem executadas no seu respec­tivo site, só existindo um Escalonador Local por site. Eles são encarregados pela comunicação interna no site. Para isso, essas threads enviam mensagens através de links para os Escalonadores da Máquina. Os links e a maneira como as mensagens são enviadas são implementados nas bibliote­cas do SimGrid [7, 3]. Os Escalonadores Locais também são responsáveis pelo envio de informações ao Escalonador Global após a execução das tarefas nos Escalonadores da Máquina. A comunicação das threads com o Escalonador Global é implementado pela biblioteca pthread.h.

Os Escalonadores da Máquina executam em to­dos os outros processadores do site e são implementados utilizando o SimGrid [7, 3]. Eles são responsáveis por e­xecutar as tarefas da aplicação e retomar os resultados para o Escalonador Local. As associações do escalo­namento e a execução das tarefas realizadas por esses escalonadores são implementadas através do uso de métodos das bibliotecas do SimGrid [7, 3], tais como SG..ScheduleTaskOnResource e SG..Simulate.

4.1. Descrição de Caso

A seguir serão mostrados exemplos do funcionamento do Framework de Escalonamento Hierárquico. Para tais exem­plos considere a hierarquia de escalonamento mostrada na Figura I onde é possível visualizar a distribuição dos pro­cessos escalonadores entre as máquinas da grade, com seus respectivos fatores de heterogeneidade h(Pi)· Neste caso, a latência L entre as máquinas de um mesmo site é unitária enquanto que entre sites esse valor duplica.

Exemplo l. Para esse primeiro exemplo, considere o GAD da Figura 2(a) que representa uma aplicação In-tree. O escalonamento estático inicial das tarefas foi realizado uti­lizando o algoritmo List-Scheduling (configurável) [4], e seu resultado pode ser visto na Figura 3(a).

Suponha que por algum motivo após o início da execução da aplicação (de acordo com o escalonamento estático) ocorra uma sobrecarga de trabalho no proces­sador p6 , fazendo com que h (p6 ) passe a ser 3, triplicando o tempo de execução da tarefa v2, inicialmente alo­cada a ele. No momento inicial da execução da aplicação na Grade, durante o primeiro evento de escalonamen­to, o escalonador dinãmico seleciona um bloco de tarefas para ser re-escalonado de acordo com políticas estu­dadas em [1]. Para o primeiro bloco, v0, Vt. v2 e v3, utilizando a política de escolha do processador que mini­miza o tempo de fim da execução da tarefa em um proces-

203

Figura 1. Esquema representativo da hierar­quia de escalonamento.

Figura 2. Aplicação ln-tree (a) e Diamante (b)onde, e(vi) = 1,\ivi E V e w(vi,vi) = 1,\i(vi,Vj) E E .

sador, o Escalonador Local do site I irá re-escalonar a tarefa v2 para o processador p5 . Nos demais eventos de escalo­namento, o escalonador dinãmico não irá reescalonar ne­nhuma tarefa. Na Figura 3 (b), pode-se observar a alocação das tarefas após o re-escalonamento. Se o escalona­dor dinãmico não estivesse em execução, o escalonamento estático proposto inicialmente não seria satisfatório, devi­do ao fato de que a sobrecarga do processador p6 atrasaria toda a execução da aplicação. No caso em que o esca­lonador dinâmico decidir re-escalonar uma tarefa entre sites, o Escalonador Global também participará deste pro­cesso.

Exemplo 2. Para o segundo considere o GAD da Figura 2(b) que representa uma aplicação Diamante. O escalonamento estático inicial das tarefas foi realizado uti­lizando o algoritmo HEFT (configurável) [4], e seu resul­tado pode ser visto na Figura 4(a).

Da mesma forma, o processador p5 passa a ter uma carga adicional como anteriormente, triplicando o tempo de execução das tarefas inicialmente alocadas a ele. Ou-

Anais WSCAD 2005

o

2

s

6 (a) (b)

Figura 3. Alocação do GAD ln-tree (a) estática e (b) dinâmica.

(a)

Figura 4. Alocação do GAD Diamante (a) estática e (b) dinâmica.

rante a execução da aplicação na Grade, em cada evento de escalonamento, o escalonador dinâmico se­leciona o bloco de tarefas e o re-escalona, utilizando a mesma política dinâmica descrita no exemplo ante­rior. Na Figura 4(b), pode-se observar o resultado do re-escalonamento. Se o escalonador dinâmico não es­tivesse em execução, o escalonamento estático proposto inicialmente não seria satis fatório, levando a um tempo de execução igual a 14.

204

5. Conclusões

Além de descrever um simulador de framework hierárquico para escalonamento dinâmico em grades com­putacionais, este trabalho propõe a simulação de um am­biente para análise de diversas políticas de escalonamento de tarefas. Este ambiente possibilitará a avaliação de de­sempenho de heurísticas de escalonamento híbridas, com a análise de todas as classes de aplicações citadas anterior­mente. Os testes de desempenho têm por objetivo comparar os resultados das políticas de escalonamento dinâmico pro­postas em [I] e adaptadas para o Framework EasyGrid.

As propostas apresentadas neste trabalho estão em fase de desenvolvimento, já sendo possível observar a eficiência da utilização de rhreads na simulação de execuções de políticas dinâmicas de escalonamento. O simulador des­crito já é capaz de obter o tempo total de execução de uma aplicação em uma grade, utilizando a mesma política de escalonamento em todos os sites. Porém, uma das metas principais do projeto é a avaliação do desem­penho de aplicações considerando sites com diferentes políticas de escalonamento dinâmico.

Referências

[1) C. Boeres, A. Lima, and V. Rebello. Hybrid task schedul­ing: lntegrating static and dynamic heuristics. In Proc. of the 15th Symposium on Compllter Architecture and High Per­fonnance Computing (SBAC-PAD 2003), pages 199-106, São Paulo, Brazi1, November 2003. IEEE Computer Society Press.

[2) C. Boeres and V. E. F. Rebello. EasyGrid: Towards a frame­work for the automatic grid enab1ing of legacy MPI app1ica­tions. Concurrency and Computation: Practice and Experi­ence, 16(5):425-432, Apri12004.

[3) H. Casanova. Simgrid: a toolkit for the simu1ation of appli­cation scheduling. Proc. of 1st IEEEIACM l nt. Symposium on C/uster Compllting and the Grid, May 2001.

[4] A. Fonseca and B. Vianna. Um ambiente para desen­volvimento e avaliação de algoritmos de escalonamento para grades tradicionais. Monografia Final de Curso, Graduação em Ciência da Computaçcio, Agosto 2004.

[5) I. Foster and C. Kesse1man, editors. The GR/D: Blueprint f or a New Compllting lnfrastructure. Morgan Kaufmann, 1999.

[6) I. Foster, C. Kesselman, and S. Tuecke. The anatomy of the Grid: Enab1ing scalable virtual organizations. lnt. Journa/ Su­percompwer Applications, 15(3):200-220, 2001.

[7) A. Legrand. L. Marchai, and H. Casanova. Schedu1ing distributed applications: the simgrid simulation framework. Proc. of 3rd IEEEIACM lnt. Symposium on C/uster Complll­ing and the Grid, 2003.

[8] Message Passing Forum. MPI: A Message Passing Interface. Technical report, University ofTennessee, 1995.

[9) J. D. Ullman. Np-complete schedu1ing problems. Journal of Computerand System Sciences, 10:384-393, 1975.