Uma nuvem privada oportunista para execução de aplicações Bag-of-Tasks

Este trabalho é o resultado de pesquisa e desenvolvimento realizado no LSD por Abmar Barros, Patrícia Alanis, Francisco Brasileiro e Marcos Nóbrega. Foi publicado no XXXI Simpósio Brasileiro de Redes de Computadores e Sistemas Distribuídos (SBRC 2013).

Atualmente a Computação na Nuvem (Cloud Computing) é um dos principais paradigmas da computação, no qual recursos computacionais são oferecidos como serviços. Considerando o modelo de Infraestrutura como Serviço (IaaS), motivações distintas levam o usuário a utilizar nuvens públicas, onde solicita máquinas, redes e armazenamento sob demanda de provedores, ou implantar uma nuvem privada, que requer um investimento em infraestrutura para a aquisição de datacenters próprios e faz sentido para aplicações corporativas que necessitam de uma alta garantia do serviço. Existem classes de aplicações que se beneficiariam de uma infraestrutura não dedicada de nuvem, que é o caso de aplicações BoT (Bag-of-Tasks), que são aplicações paralelas que as tarefas são independentes entre si.

O paradigma de nuvens públicas, que oferece baixa QoS, não encontra uma analogia no cenário típico de implantação de nuvem privada. Além disso, os usuários finais, de uma forma geral, não estão acostumados com a interface da nuvem, que, a priori, se resume a uma coleção de instâncias com acesso SSH.

Este trabalho apresenta uma abordagem baseada em uma nuvem privada utilizando o software Eucalyptus, porém de uma forma oportunista, que permite descobrir e utilizar recursos ociosos que pertencem a uma infraestrutura física local, para isso reimplementamos o Node Controller (NC), um componente responsável por executar ações sobre os recursos físicos, que em sua implementação original limita o uso para os hipervisores XEN e KVM, e impõe uma série de requisitos de sistema para sua implantação que em um ambiente heterogêneo se torna inviável. O componente foi reimplementado em Java, uma vez que este dependeria apenas de uma JVM, e utiiliza o VirtualBox como hipervisor, já que seus executáveis estão disponíveis para uma série de sistema operacionais (Linux, Windows e MacOS) e não têm requisitos de hardware. A figura a seguir apresenta a arquitetura do NC oportunista apresentado neste trabalho.

O segundo problema citado refere-se a dificuldade de adaptação de usuários finais com a interface de nuvem, e para viabilizar a utilização da nuvem oportunista por pesquisadores de diferentes áreas, este trabalho apresenta um broker de nuvem, capaz de executar aplicações BoT na nuvem de forma transparente. A arquitetura do broker é constituída por dois componentes: o broker deamon, uma aplicação REST que executa em segundo plano e é responsável por escalonar tarefas, requisitar instâncias, transferir arquivos e executar comandos, e o broker client, uma interface onde o usuário pode submeter tarefas e recuperar informações de estados. A figura a seguir mostra um exemplo de aplicação BoT que pode ser submetida ao broker.

Para mais detalhes sobre a arquitetura da solução, e sobre o funcionamento do broker de nuvem veja o nosso artigo Uma nuvem privada oportunista para execução de aplicações Bag-of-Tasks.

Estratégias de Obtenção de um Item Máximo em Computação por Humanos

Este trabalho foi publicado no XXXI Simpósio Brasileiro de Redes de Computadores e Sistemas Distribuídos (SBRC 2013). É resultado da pesquisa de Iniciação Científica de Jeymisson Oliveira, desenvolvida com o auxílio de Lesandro Ponciano, Nazareno Andrade e Francisco Brasileiro.

Existem problemas que não são bem resolvidos com os sistemas computacionais atuais, por exemplo, encontrar onde está o wally na imagem abaixo é uma tarefa que não é resolvida de forma satisfatória (em termos de tempo e precisão) por computadores. Sistemas de computação por humanos tratam justamente desses problemas e visam orquestrar o trabalho de um grupo de trabalhadores com o objetivo de resolver um problema que não poderia ser resolvido de forma satisfatória com os  sistemas computacionais atuais.

Dentre os diversos problemas que a computação por humanos lida um problema bastante comum é a escolha de um item máximo. Como, por exemplo, a escolha de uma melhor tradução em um conjunto de traduções candidatas. Esse problema torna-se mais  complexo na medida em que a quantidade de frases aumenta. A solução mais simples para esse problema é comparar todos os candidatos e o candidato que for dito como máximo no maior número das comparações que participou é o item máximo. O problema dessa solução é que à medida em que os itens candidatos aumentam, são necessárias muitas comparações para se obter o item máximo.

O objetivo do nosso trabalho é tornar mais eficiente em termos de quantidade de tarefas necessárias para a obtenção do item máximo. Para isso nós propomos uma estratégia de eliminação múltipla de itens candidatos que objetiva eliminar múltiplos itens candidatos em uma comparação e com isso reduzir a quantidade de comparações necessárias para se obter o item máximo.

Quantidade de tarefas para se obter o item máximo

Economia de tarefas com eliminação múltipla

Para avaliar os benefícios da estratégia de eliminação múltipla nós analisamos  três algoritmos de obtenção de um item máximo existentes na literatura, o Tournament Selection(TS), 2-Max, e Tournament Max, e modelamos a quantidade de tarefas necessárias para a obtenção de um item máximo com a estratégia e sem  a estratégia de eliminação múltipla. Nesse caso obtivemos a quantidade de tarefas necessárias para se obter o item máximo para cada um dos algoritmos 2-Max, TM e TS, e a quantidade de tarefas necessárias com os algoritmos modificados 2-Max2 e TM2 para utilizarem a estratégia de eliminação múltipla. Portanto pudemos observar que a economia  obtida com relação ao número de tarefas quando utilizamos o algoritmo modificado 2-max2 no lugar do algoritmo do estado da arte 2-Max chega à níveis maiores que 50% à medida em que o número de itens candidatos |S| aumenta. 

Por fim para avaliar a utilização da estratégia de eliminação múltipla, nós desenvolvemos uma aplicação de obtenção de um item máximo que foi realizada por 108 trabalhadores, e possuía 520 comparações. Cada comparação deveria ser realizada no mínimo 3 vezes. Nessa aplicação os trabalhadores deveriam selecionar qual  das imagens possui a grade vermelha que melhor se encaixa entre as linhas e colunas das tabelas ou optar pela utilização da eliminação múltipla selecionando um botão que eliminaria as duas imagens. Com os resultados desse experimento, pudemos concluir que os trabalhadores convergem com relação à utilização da eliminação múltipla quando os itens não se adequam como item máximo (grades vermelhas que não se encaixam de maneira alguma entre as linhas e colunas das tabelas) e que eles também convergem em escolher um dos itens quando ele atende aos requisitos de um item máximo. Portanto há evidências de que a estratégia de eliminação múltipla proposta além de gerar uma economia com relação a quantidade de tarefas necessárias não insere erros na computação de obtenção de um item máximo.

A aplicação utilizada para experimento nesse trabalho está acessível aqui. Para mais detalhes veja nosso artigo Estratégias de Obtenção de um Item Máximo em Computação por Humanos.