Framework P2P para execução de tarefas bag-of-tasks com múltiplas políticas de alocação em ambientes distribuídos heterogêneos

Abstract

Aplicações em áreas como genômica comparativa, em neurociências ou de controle de tráfego aéreo têm a característica de requerem grande quantidade de processamento de modo a obterem os resultados. Muitas vezes, essas aplicações são executadas em Desktop grids, que são uma plataforma baseada em máquinas de uso geral, mas que em grande escala tem potencial de atingirem grande quantidade de processamento. As aplicações em grid são em geral aplicações complexas, que executam em um número grande e heterogêneo de nós não dedicados, disponíveis em domínios administrativos distintos. As abordagens atuais de utilização dos recursos em desktop grids são centralizadas, possuindo geralmente escalabilidade limitada. O modelo Peer-to-Peer (P2P) evoluiu simultaneamente e em paralelo aos interesses da computação em grid. Devido à característica descentralizada da arquitetura P2P, ela tem sido utilizada como solução complementar à arquitetura em grid. Observa-se, então, uma convergência entre a computação em grid e a arquitetura P2P, juntando as melhores características de cada tecnologia. Nesse contexto, a alocação de tarefas é um problema importante que visa atribuir tarefas a um conjunto de recursos, objetivando maximizar o uso dos recursos. A alocação de tarefas em ambientes descentralizados é complexa, uma vez que não há uma visão global do sistema. Nessa dissertação, propomos e avaliamos um framework flexível para alocação descentralizada de tarefas em ambiente de grid com múltiplas políticas de alocação. Além do framework, propomos e avaliamos duas políticas de alocação de tarefas baseadas em Work Stealing: Work Stealing with Replication (WSR) e Local Work Stealing with Replication (LWSR). O protótipo do framework proposto foi desenvolvido utilizando JXTA como middleware e o Chord como overlay P2P. Entretanto, o framework é flexível pois não está acoplado nem ao middleware de rede nem ao overlay P2P utilizado. Os resultados obtidos em um ambiente heterogêneo composto de 16 máquinas dispostas em dois laboratórios, executando aplicações de controle de tráfego aéreo, mostraram que o tempo de execução da aplicação pode ser sensivelmente reduzido com o nosso framework. Um speedup de 11,86 foi obtido para uma aplicação composta de 180 tarefas, reduzindo o tempo de execução seqüencial da melhor máquina de 22,35 minutos para 1,8 minutos, com 16 máquinas. _______________________________________________________________________________ ABSTRACT

Applications in fields, such as genomics, neuroscience or air traffic control, usually require large amounts of processing power to obtain results. In many times, these applications run on desktop grids, which are a platform based on generalpurpose machines that has the potential to reach large amount of processing. Grid applications, in general, are complex applications running on large and heterogeneous non-dedicated nodes, available in different administrative domains. Current approaches to use resource in desktop grids are centralized, having limited scalability. The interest in the Peer-to-Peer (P2P) model grew simultaneously and in parallel to those interests of grid computing. Therefore, we observe nowadays, a convergence between grid computing and P2P computing, aiming to provide the best characteristics of each technology. In this context, task allocation is one important problem where tasks are assigned to a set of resources, aiming to maximize resource usage. Task allocation in a decentralized environment is complex since there is no global view of the system. In this dissertation, we propose and evaluate a flexible framework for decentralized task allocation in a grid environment with multiple allocation policies. Besides the framework, we propose and evaluate allocation tasks based on Work Stealing: Work Stealing with Replication (WSR) and Local Work Stealing with Replication (LWSR). The prototype of the proposed framework was implemented on top of the JXTA middleware using the Chord as overlay. Nevertheless, the proposed framework is flexible because it is decoupled from both the P2P middleware and the P2P overlay. The results obtained in a heterogeneous environment composed of 16 machines arranged in two campus-wide laboratories, executing air traffic control applications show that the execution time can be sensibly reduced with our framework. A speedup of 11.86 was obtained with an application composed of 180 tasks, reducing the sequential execution time of the best machine from 22.35 minutes to 1.8 minutes, with 16 machines.