Problemas de otimização de alocação de máquinas virtuais para computação em nuvem

• Processo: 15/08438-0
• Modalidade de apoio: Bolsas no Brasil - Iniciação Científica
• Data de Início da vigência: 01 de junho de 2015
• Data de Término da vigência: 01 de agosto de 2016
• Área de conhecimento: Ciências Exatas e da Terra - Ciência da Computação - Teoria da Computação
• Pesquisador responsável: Cid Carvalho de Souza
• Beneficiário: Matheus de Souza Ataide
• Instituição Sede: Instituto de Computação (IC). Universidade Estadual de Campinas (UNICAMP). Campinas , SP, Brasil
• Bolsa(s) vinculada(s): 15/23270-9 - Heurísticas GRASP para problemas de alocação em computação em nuvem, BE.EP.IC
• Assunto(s): Computação em nuvem Otimização combinatória Problemas de otimização Heurística Máquina virtual
• Palavra(s)-Chave do Pesquisador: Computação em Nuvem | Grasp | heuristicas | Otimização Combinatória | Otimização Combinatória

Resumo

A computação em nuvem está cada vez mais presente em nosso cotidiano, não só para usuário doméstico, mas também nas áreas empresarial, comercial e acadêmica. Por compartilhar recursos e ter custo proporcional ao uso, a computação em nuvem promete um melhor uso da infraestrutura computacional e economia de gastos. Entretanto, para atingir um alto nível de utilização dos recursos, é inevitável que os componentes de uma dada aplicação sejam alocados a máquinas virtuais de forma não contígua. Desse modo, esses componentes podem acabar em máquinas físicas muito distantes na nuvem. Essas discrepâncias em distância podem causar grandes variações na latência média entre os componentes. Para um grande número de aplicações essas diferenças de latência têm um elevado impacto no desempenho computacional, o qual depende fundamentalmente do modo como é feito o mapeamento dos componentes da aplicação dada sobre as máquinas na nuvem. Problemas de otimização relacionados a este mapeamento foram discutidos em artigos científicos recentes por Zou et Al. (2012). Além de mostrar que tais problemas são NP-difíceis, os autores propuseram e testaram algumas heurísticas gulosas para resolvê-los, comparando os seus resultados com soluções geradas de modo puramente aleatório. Analisando estes resultados, percebeu-se o potencial de se empregar uma heurística que combinasse estas duas características para se chegar a soluções ainda melhores que aquelas encontradas até aqui. Uma heurística que surge naturalmente como candidata nesta situação é o GRASP (acrônimo do inglês Greedy Randomized Adaptive Search Procedure). Assim, o objetivo do presente projeto de iniciação é investigar o uso do GRASP na solução dos problemas tratados no artigo científica de Zou et al. 2012.