BDBComp
Parceria:
SBC
Algoritmos de Escalonamento de Tarefas em Grades Computacionais

Epifanio Dinis BenitezGerson G. H. Cavalheiro

O advento de arquiteturas paralelas (ex. clusters) possibilitou que aplicac¸ ~oes de´areas como a f´?sica e a biologia pudessem gerar resultados interessantes para a pesquisa.Este fato deu origem ao interesse dos pesquisadores em desenvolver algoritmos mais eficientesque por sua vez, necessitariam de uma arquitetura com abundantes recursos dearmazenamento e processamento. Devido a essa e outras situac¸ ~oes, surgiu a computac¸ ~aoem grade (grid computing) [CIR 2003]. Sua estrutura est ´a composta por m´aquinas geograficamentedistribu´?das, em escala regional e mundial, e apresenta um modelo computacionalformado por servidores de aplicac¸ ~ao ASP's (Application Service Provider) ede servidores de armazenamento SSP's (Storage Service Provider). Esta estrutura tornavi´avel a execuc¸ ~ao de aplicac¸ ~oes - tipicamente de simulac¸ ~ao - que geram uma grandequantidade de dados, os quais devem ser distribu´?dos a outras m´aquinas, explorando deforma cr´?tica os recursos de rede. Desta forma, a rede se torna a limitac¸ ~ao do desempenhoglobal do sistema. A soluc¸ ~ao a esta limitac¸ ~ao se encontra no desenvolvimento dealgoritmos de escalonamento que minimizem ao m´aximo o custo de comunicac¸ ~ao entreas m´aquinas que participam da execuc¸ ~ao da aplicac¸ ~ao, resultando em um ganho dedesempenho global da aplicac¸ ~ao e reduzindo o impacto global no uso da rede.Apesar desta limitac¸ ~ao, ambientes conhecidos [COS 2004, AND 2003] tentamobter ganho de desempenho atrav´es do escalonamento de tarefas desconsiderandoinformac¸ ~oes importantes como o custo de comunicac¸ ~ao e computac¸ ~ao das tarefas. Entreesses algoritmos est~ao o WQ (WorkQueue) e o WQ-R (WorkQueue with replication).Nossa proposta consiste em minimizar o tempo de comunicac¸ ~ao entre tarefas atrav´es daextens~ao do algoritmo DSC (Dominant Sequence Clustering) adaptando-o `a computac¸ ~aoem grade. Diferente dos demais algoritmos, este realiza o escalonamendo baseado eminformac¸ ~oes como o custo de processamento e comunicac¸ ~ao das tarefas.Na pr ´oxima sec¸ ~ao se encontram descritos os algoritmos de escalonamento citadosanteriormente. Na seq¨u^encia ´e apresentada a extens~ao do algoritmo DSC, seguidapor uma avaliac¸ ~ao de desempenho para validar o uso do algoritmo DSC como base deimplementac¸ ~ao, e finalmente, as conclus~oes.

http://www.lbd.dcc.ufmg.br/colecoes/erad-rs/2006/0037.pdf

Caso o link acima esteja inválido, faça uma busca pelo texto completo na Web: Buscar na Web

Biblioteca Digital Brasileira de Computação - Contato: bdbcomp@lbd.dcc.ufmg.br
     Mantida por:
LBD