Escalonamento estático de tarefas em ambientes computacionais heterogêneos sob o modelo logP

Numerous applications require more performance than event state-of-the- art sequencial computers can provide in order to be executed in acceptable time frames. With high costs of acquisition and maintenance of supercomputers, cheaper parallel computing alternatives such as Computing Clusters, and more recently Computational Grids, are now becoming the computing systems of choice within research centers, companies and universities. On these platforms, the efficient scheduling of the tasks of a parallel application is crucial to obtaining good performance. This work studies the problem of scheduling tasks in systems of distributed heterogeneous resources which communicative via message passing. The processing costs to send and to receive messages (traditional ignored by scheduling algorithms) can dramatically influence the execution time of parallel applications. In this dissertation three new strategies are proposed to enable list scheduling heuristics to handle these overhead costs appropriately in order to generate efficient schedules of environments such as Clusters and Computational Grids. Based on the logP model, results show that two of the proposed strategies provide significant improvements over the only existing approach known in the literature.Atualmente diversas aplicações necessitam de poder computacional superior ao que um computador seqüencial podem fornecer para serem executadas em tempos aceitáveis. Face aos altos custos dos supercomputadores, alternativas como schulsters e, mais recentemente, os grids computacionais estabeleceram-se como formas de agregar poder computacional a custos acessíveis. O objetivo de um grid é agregar equipamentos, distribuídos, heterogêneos e compartilhados formando uma constelação de recursos interconectados por redes de alta velocidade. Nessa via láctea de recursos é esperado um comportamento tipicamente dinâmico, uma vez que a disponibilidade dos mesmos nem sempre pode ser garantida, Sob esses aspectos, é imperativo que a execução das aplicações paralelas seja eficiente, ou seja, o paralelismo nelas existentes seja convenientemente explorados para que o potencial latente da grade possa ser totalmente aproveitado. O problema é tratado em termos de escalonamento de tarefas, alvo de muitos estudos e foco desta pesquisa. Devido ao comportamento instável do ambiente é necessário um escalonador dinâmico para realizar a alocação das tarefas aos recursos durante a execução da aplicação. Uma estratégia para aliviar a carga de trabalho do escalonador dinâmico é incorporar um pré-escalonamento de tarefas, através de um escalonador estático, assim ao dinâmico restará apenas os ajustes finais momentâneos. O objetivo do trabalho é propor um escalonador estático para ambientes com características semelhantes às grades computacionais. A abordagem escolhida para o problema apresenta uma heurística da classe de list scheduling para um número limitado de processadores heterogêneos. Durante a pesquisa foi possível observar que existem inúmeras heurísticas formuladas para ambientes homogêneos, e bem menos para ambientes heterogêneos. Entretanto quase todas são formuladas em modelos de comunicação inapropriados para plataformas de clusters e grades. Por essa razão, resolveu-se adotar um modelo mais realístico como o logP que considera parâmetros que permitem o cálculo preciso do custo das comunicações. A nova heurística é uma extensão da metodologia proposta por Kalinowski, Kort e Trystam adaptada para ambientes heterogêneos e implementada em quatro versões. A investigação consiste em avaliar políticas alternativas para minimizar os efeitos adversos que as sobrecargas decorrentes das comunicações causam ao makespan das aplicações paralelas