TMRorR: um novo algoritmo de escalonamento para o OurGrid que combina o uso de informação e replicação

Abstract

A distribuição de tarefas de forma eficiente em grades computacionais possui grandes desafios que devem ser considerados por um algoritmo de escalonamento. Esse desafios estão relacionados com as características das grades, como a escalabilidade, heterogeneidade, dinamicidade, entre outros. Dentre as diversas propostas de algoritmos de escalonamento existentes, grande parte utilizam da informação obtida do ambiente ou da replicação de tarefas como forma de atingir um desempenho satisfatório na execução das aplicações dentro da grade. Os algoritmos de escalonamento que dependem somente das informações para realizar o escalonamento estão restritos a ambientes em que as mesmas estejam disponíveis e sejam confiáveis. Já os algoritmos que utilizam somente de replicação não dependem de nenhuma informação. A existência de ambientes em que a presença de informação não é totalmente confiável ou não atende a todos os recursos da grade, motiva o surgimento de algoritmos que utilizam uma técnica híbrida. Neste caso a informação, quando disponível, é utilizada para realizar o escalonamento, porém, quando não, utiliza-se da replicação de tarefas. Este trabalho realiza um estudo acerca do escalonamento de tarefas realizado pelo WQR do OurGrid e apresenta um novo algoritmo para escalonamento de aplicações Bag-of-Tasks aqui denominado TMRorR (Task for More Reliable or Replicate).Este algoritmo utiliza uma técnica híbrida e, considera sempre que um recurso que possui informação é sempre mais confiável do um que não possui e, também, faz uma distinção entre recursos pertencentes ao domímio local e recursos pertencentes a outros domínios, tendo regras de escalonamento com algumas diferenças para ambos os casos. O algoritmo foi simulado utilizando o GridSim e implementado no OurGrid para realizar os experimentos. Comparando os resultados obtidos, eles mostraram um desepenho melhor do TMRorR em relação WQR na maioria dos casos, como também, uma redução no desperdício de ciclos de CPU com a realização de um controle maior na criação de réplicas.

An efficient distribution of tasks in computational grids has major challenges that have to be overcomed by a scheduling algorithm. These challenges are related to the characteristics of the environment, such, scalability, heterogeneity, dynamicity, among others. Most of the existing scheduling algorithms use information obtained from the environment or the replication of tasks in order to achieve a satisfactory performance in the execution of applications. Algorithms that rely on resource information to accomplish their task are restricted to environments in which such information is available and reliable all across the grid. On the other hand, algorithms that use replication could be used in any environment but they introduce a significant overhead to the scheduling. However, although reliable information is usually not available across the Grid because of the dynamicity of the resources, it’s possible to have updated resource information inside a local site. This motivates the development of algorithms that use a hybrid technique. In this case the information is used to perform the scheduling when available - for example in the local site - and only when it’s not available the scheduler uses replication, thus reducing its overhead. This work proposes such an hybrid algorithm called TMRorR - Task More Reliable or Replicate for the Ourgrid middleware. The algorithm was simulated with GridSim and implemented in OurGrid to perform the experiments. Obtained results showed a better performance of TMRorR in comparison to the Ourgrid scheduler in several scenarios and a reduction in the overhead of creating replica.