Heurísticas GRASP para problemas de alocação em computação em nuvem

• Processo: 15/23270-9
• Modalidade de apoio: Bolsas no Exterior - Estágio de Pesquisa - Iniciação Científica
• Data de Início da vigência: 16 de janeiro de 2016
• Data de Término da vigência: 15 de março 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
• Supervisor: Marcos Antonio Vaz Salles
• Instituição Sede: Instituto de Computação (IC). Universidade Estadual de Campinas (UNICAMP). Campinas , SP, Brasil
• Instituição Anfitriã: University of Copenhagen, Copenhagen, Dinamarca
• Vinculado à bolsa: 15/08438-0 - Problemas de otimização de alocação de máquinas virtuais para computação em nuvem, BP.IC
• Assunto(s): Computação em nuvem Otimização combinatória Heurística
• Palavra(s)-Chave do Pesquisador: Computação em Nuvem | Grasp | heuristicas | Otimização Combinatória | Otimização Combinatória

Resumo

Esse documento apresenta o projeto de pesquisa para problemas de alocação em computação em nuvem, para ser desenvolvido pelo estudante Matheus Ataide no Departamento de Ciência da Computação (DIKU) da Universidade de Copenhagen sob supervisão do Professor Marcos Salles. A computação em nuvem se consolidou como grande modelo computacional nos últimos anos. 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 é investigar o uso do GRASP na solução dos problemas tratados no artigo científica de Zou et al. 2012. Durante sua visita ao DIKU, é esperado principalmente que o estudante realize experimentos computacionais e escreva relatórios analisando os resultados obtidos com o objetivo de publica-los em conferências e/ou jornais científicos. (AU)