A proposta deste projeto é estudar técnicas e algoritmos relacionados à computação evolutiva e aos FPGAs visando o desenvolvimento de um sistema de hardware inteligente e com capacidade adaptativa. Muitas aplicações não comportam a utilização de PCs e acabam implementando soluções utilizando hardware de circuito impresso. Esses sistemas, no entanto, não apresentam possibilidade de atualização e acabam tornando-se obsoletos mesmo quando pequenas modificações ocorrem no problema. O sistema proposto visa agir nessa lacuna, apresentando a flexibilidade dos sistemas em hardware, porém com possibilidade de atualização. Para a implementação deste sistema é proposto o desenvolvimento de um algoritmo evolutivo (AE) que será utilizado para configurar um FPGA. O sistema funciona como descrito a seguir: Um AE evolui a configuração de um FPGA para que este torne-se um sistema de hardware dedicado à resolução de um problema, no entanto, o processo não é interrompido, permitindo ao sistema auto-adaptar-se caso haja uma modificação nesse problema. É importante que o sistema satisfaça critérios de eficiência computacional. Para isso é necessário estudar características dos FPGAs e dos AE para propor uma arquitetura de FPGA que gere uma representação de indivíduo eficiente e que limite o espaço de busca sem limitar o poder de resolução de problemas. Sobre essa representação, deve-se criar operadores eficientes e que possam ser implementados em um hardware de capacidade limitado.

O desenvolvimento do trabalho depende de conhecimentos de FPGAs, AEs e Teoria dos Grafos e Programação de Hardware. Estes tópicos foram estudados de forma introdutória e depois, aqueles com relevância para a abordagem proposta foram estudados mais profundamente. Depois de adquirida a base teórica necessária, foram propostas diversas abordagens para resolução do problema, envolvendo diversas estratégias evolutivas, operadores e representações. Essas abordagens foram sendo refinadas ou descartadas, conforme sua viabilidade ou eficiência, até que duas abordagens definitivas foram formalizadas. A primeira delas, mais complexa modela o FPGA como um grafo que é evoluído segundo os operadores e a representação nó profundidade. Essa abordagem foi posteriormente descartada por não poder ser aplicada ao FPGA que dispúnhamos. A segunda, mais simples, modela todas as características do FPGA como cadeias de bits, sobre os quais operadores tradicionais poderiam ser aplicados. Essa abordagem, muito próxima ao hardware, foi levada adiante e investigada profundamente por simulação em software até satisfazer os critérios de eficiência. Além disso, o sistema proposto foi implementado em um FPGA usando a linguagem VHDL. Essa implementação continha, em um único FPGA, os módulos de evolução, seleção, teste, interface e um FPGA “virtual” capaz de abrigar candidatos à solução. Esse sistema funcionava independente de qualquer outro computador, o que é um dos principais requisitos do sistema.

A abordagem escolhida testada exaustivamente e analisada sob o ponto de vista estatístico. Foram testados diversos operadores, com diversas freqüências de aplicação, métodos de seleção, tamanho de população e de FPGA. Para cada uma das combinações de parâmetros, foram realizados ao menos 200 execuções do AE. Esses dados foram analisados segundo do número de gerações necessárias, utilizando média, desvio médio, 1o 2o e 3o quartil, máximo e mínimo a fim de estudar não somente a eficiência, mas também a estabilidade e confiabilidade do método. Como resultado da análise, concluímos que a eficiência computacional foi superior à esperada, satisfazendo o critério de eficiência computacional e também apresentando estabilidade satisfatória. Os dados abaixo referem-se a uma população de 10 indivíduos para um FPGA de tamanho 64. Média 18.5 Desvio 8.5 Mínimo 3 Quartil 11 (1o) 15 (2o) 21 (3o) Máximo 141 Através desses dados podemos notar que apesar do máximo (141) não ser satisfatório o terceiro quartil é bastante baixo, indicando que 75% das execuções ficaram abaixo de 21 gerações, o que é um resultado melhor do que o esperado considerando a dificuldade do problema. Sobre o sistema implementado em FPGA, não foi possível realizar testes estatísticos devido ao seu isolamento, mas foi possível comprovar a viabilidade de implementar um sistema evolutivo completamente embarcado dentro de um hardware de baixa capacidade.

Os resultados obtidos na simulação indicam que o sistema proposto é viável. No entanto, a quantidade de parâmetros envolvidos e as combinações utilizadas nos testes indicam que muito ainda pode ser desenvolvido e melhorado em relação ao que foi realizado neste trabalho. Melhoras no sistema podem ser obtidas apenas otimizando os parâmetros em questão. Pode-se ainda explorar sobre a mesma representação escolhida, diversos operadores de mutação e crossover não experimentados, novos métodos de seleção e até mesmo novas estratégias evolutivas. A representação também pode ser refinada e outras representações mais complexas podem ser exploradas, tendo como objetivo a implementação em sistemas mais complexos do que o que foi usado nesse trabalho. A análise teórica realizada sobre a representação utilizando a notação nó-profundidade indica que essa abordagem é promissora sob o ponto de vista da eficiência do método, no entanto seria necessário aplicar sobre ela, técnicas de co-design e o sistema final deveria incluir alem de um hardware dedicado, um micro-processador embarcado em um FPGA. Essa proposta estava fora do escopo desse trabalho, mas é viável pode ser explorada. O sistema implementado em FPGA, apesar de simples, mostrou que os métodos e abordagens desenvolvidas podem ser transportados da simulação para sistemas reais. Esse sistema satisfaz todos os requisitos do projeto e pode ser considerado um modelo do sucesso da abordagem proposta.

Instituição de fomento: FAPESP e CNPQ

Trabalho de Iniciação Científica