Paralelizando a Fase de Roteamento de Circuitos Baseados em FPGAs

Este trabalho está focado na fase de roteamento de circuitos baseados em Field Programmable Gate Arrays (FPGAs). O roteamento é uma das etapas que mais consome tempo de toda a fase de projeto, justificando assim o desenvolvimento de uma abordagem paralela. Este trabalho se baseia na percepção de um desacopla- mento do grafo de roteamento, que é decorrente da imposição de restrições sobre uma dada arquitetura de FPG A, particionando assim seus recursos de roteamento em domínios disjuntos de trilhas.
Usando-se o paradigma de memória distribuída foi desenvolvida uma aplicação paralela, onde cada processador recebe um conjunto diferente de redes de sinal (nets) e o roteia em sua partição do grafo de roteamento. Resultados computacionais são apresentados e comparações realizadas com os melhores resultados existentes na literatura. Também foi desenvolvida uma nova heurística para o problema da árvore de Steiner mínima, visando a seu uso no roteamento em FPGAs. Formulações de programação inteira para o problema de roteamento global e suas relaxações são estudadas.