Análise do particionamento de um projeto de redes de larga-escala em cluster de FPGAs

• Processo: 12/10140-1
• Modalidade de apoio: Bolsas no Exterior - Estágio de Pesquisa - Iniciação Científica
• Data de Início da vigência: 01 de setembro de 2012
• Data de Término da vigência: 31 de dezembro de 2012
• Área de conhecimento: Ciências Exatas e da Terra - Ciência da Computação - Sistemas de Computação
• Pesquisador responsável: Vanderlei Bonato
• Beneficiário: Andre Bannwart Perina
• Supervisor: João Manuel Paiva Cardoso
• Instituição Sede: Instituto de Ciências Matemáticas e de Computação (ICMC). Universidade de São Paulo (USP). São Carlos , SP, Brasil
• Instituição Anfitriã: Universidade do Porto (UP), Portugal
• Vinculado à bolsa: 11/20053-6 - Representação de algoritmos evolutivos em cluster de FPGAs para projetos de redes de larga-escala, BP.IC
• Assunto(s): Algoritmos Computação reconfigurável Computação evolutiva
• Palavra(s)-Chave do Pesquisador: Algoritmos Evolutivos | computação evolutiva | Computação Reconfigurável | Problemas de Projeto de Redes | Arquitetura de Hardware

Resumo

Vários problemas do mundo real estão relacionados ao projeto de redes, como projeto de circuitos de energia elétrica, malhas viárias, redes de telecomunicações, entre outros. Em geral, esses problemas podem ser modelados por meio de grafos, que manipulam milhares ou milhões de nós (variáveis de entrada), tornando impraticável a obtenção de soluções em tempo real. Esses cenários são classificados como Problemas de Projeto de Redes (PPRs), que envolvem problemas combinatórios em que se busca encontrar a rede de grafo mais adequada (menor custo, tempo, trajeto). A solução desses problemas é, em geral, computacionalmente complexa. Nesse sentido, metaheurísticas como Algoritmos Evolutivos (AEs) têm sido amplamente investigadas. Diversas pesquisas mostram que o desempenho de AEs para PPRs pode ser aumentado significativamente por meio de representações mais apropriada. O objetivo do projeto de Iniciação Científica vinculado à este pedido é expandir para até 100 mil nós uma implementação já feita por GOIS (2011) em um FPGA (Field-Programmable Gate Array), este sendo capaz de processar até 512 nós baseada em uma representação denominada nó-profundidade (RNP). Assim para alcançar o número desejado, será utilizada uma plataforma de computação composta por um Cluster de FPGAs. O objetivo deste estágio no exterior é de propor uma solução eficiente e flexível para o particionamento da implementação atual. Porém, tal particionamento deve ser analisado com cautela de modo a conseguir um resultado ótimo onde o circuito esteja melhor distribuído, utilizando menos recursos por nó de grafo e com a velocidade não comprometida pela comunicação. Este trabalho adicional será justamente encontrar a melhor maneira de se particionar e otimizar o circuito. (AU)