Dissertação de Mestrado:
Alocação e Mapeamento de Ips Para Redes Embutidas Utilizando Algoritmos Evolucionários Multiobjetivos

Marcus Vinícius Carvalho da Silva

PEL
Orientador
Profa. Nadia Nedjah , Ph.D., 1997, UMIST, Grã-Bretanha - Currículo Lattesk
Coorientador
Profa. Luiza De Macedo Mourelle , Ph.D., 1998, UMIST, Grã-Bretanha - Currículo Lattesk
Banca
* Profa. Nadia Nedjah , Ph.D., 1997, UMIST, Grã-Bretanha - Currículo Lattesk
* Profa. Luiza De Macedo Mourelle , Ph.D., 1998, UMIST, Grã-Bretanha - Currículo Lattesk
* Prof. Dr. Heitor Silvério Lopes - UTFPR
* Profa. Dra. Priscila Machado Vieira Lima - COPPE/UFRJ
Data - hora da defesa
30/04/2009
Resumo
No projeto de redes embutidas baseado em plataforma, a aloca¸c˜ao e o mapeamento de IPs s˜ao duas etapas t´ıpicas e de alta complexidade. Ferramentas de aux´ılio s˜ao essenciais para o desenvolvimento de projetos baseados em plataforma. A aloca¸c˜ao de IPs consiste em alocar os IPs adequados para executarem as tarefas de uma aplica¸c˜ao espec´ıfica. Baseado em caracter´ısticas da aplica¸c˜ao e em caracter´ısticas dos IPs dispon´ıveis, deve-se escolher o melhor conjunto de IPs capaz de executar a aplica¸c˜ao. O mapeamento de IPs consiste na organiza¸c˜ao do espa¸co f´ısico que os IPs ocupar˜ao da rede embutida. Baseado em caracter´ısticas de comunica¸c˜ao entre IPs e da plataforma de destino, deve-se escolher o melhor mapeamento poss´ıvel. Estas etapas de projeto s˜ao consideradas problemas de alta complexidade e dif´ıceis de serem resolvidos at´e mesmo por ferramentas computacionais. Nesta disserta¸c˜ao, o melhor conjunto de IPs e o melhor mapeamento ser˜ao aqueles que ocupam a menor ´area, apresentam o menor consumo de energia e executam a aplica¸c˜ao espec´ıfica no menor tempo poss´ıvel. Para encontrar solu¸c˜oes que atinjam estes objetivos, ´e proposta uma aloca¸c˜ao evolutiva de IPs e um mapeamento evolutivo de IPs, utilizando algoritmos evolucion´arios multiobjetivos. Estes algoritmos representam uma t´ecnica estoc´astica de busca e otimiza¸c˜ao voltada para problemas de otimiza¸c˜ao multiobjetivo, como ´e o caso dos problemas de aloca¸c˜ao e mapeamento de IPs. Os algoritmos utilizados s˜ao o NSGA-II e o microGA. Na etapa de aloca¸c˜ao evolutiva de IPs, estes algoritmos recebem os dados de IPs, obtidos de um reposit´orio, e os dados das tarefas da aplica¸c˜ao, obtidos do grafo de tarefas da aplica¸c˜ao. A combina¸c˜ao destes dados forma indiv´ıduos que representam solu¸c˜oes para o problema e ser˜ao submetidos a operadores gen´eticos. Na etapa de mapeamento evolutivo de IPs, os algoritmos recebem as aloca¸c˜oes de IPs, obtidas da etapa anterior, e dados da plataforma da rede embutida, onde as aloca¸c˜oes ser˜ao mapeadas. Para preservar caracter´ısticas dos indiv´ıduos adquiridas durante a etapa de aloca¸c˜ao, ´e proposto um operador gen´etico de recombina¸c˜ao por deslocamento, inspirado no mecanismo biol´ogico de partenogˆenese, e um operador gen´etico de muta¸c˜ao interna. Fatores de impacto no desempenho da rede embutida s˜ao analisados e utilizados para avaliar as solu¸c˜oes obtidas por ambos os algoritmos. Os resultados obtidos mostram-se competitivos com os de outra ferramenta de mapeamento. Uma compara¸c˜ao de desempenho entre as implementa¸c˜oes do NSGA-II e o microGA ´e realizada com base na quantidade de aloca¸c˜oes e mapeamentos ´otimos obtidos e os tempos de busca de cada algoritmo. Palavras-chave: redes embutidas, aloca¸c˜ao de IPs, mapeamento de IPs, otimiza¸c˜ao multiobjetivo, algoritmos gen´eticos.

Download do Trabalho