| Resumo: |
O processo de síntese de circuitos possui uma enorme complexidade envolvida, exigindo o uso de algoritmos para automatizar os procedimentos. Uma das etapas desse grande processo é o roteamento, que visa determinar as rotas dos fios que conectam os componentes do circuito. O roteamento é subdividido em roteamento global e detalhado. No roteamento detalhado, são utilizados algoritmos de busca de caminhos em grade para definir as rotas dos fios. Contudo, é esperado que tais algoritmos possam lidar com pelo menos as regras de projeto mais básicas. Assim, considerando que o roteamento é responsável por grande parte do tempo envolvido na síntese de circuitos, este trabalho propõe um novo algoritmo de busca de caminhos genérico em grades tridimensionais, chamado SG-Router, com a capacidade de lidar com algumas das regras de projeto mais simples. O objetivo da proposta é realizar uma comparação de tempo de execução e qualidade de caminho com o algoritmo de Hetzel, estado da arte dos algoritmos de busca genéricos em grade utilizados no roteamento detalhado. O trabalho também apresenta uma série de propostas de otimizações de tempo e de qualidade de busca para a versão preexistente do algoritmo, que funciona apenas no escopo bidimensional. Grande parte dessas otimizações foram reaproveitadas no SG-Router. Os experimentos realizados na versão bidimensional melhorada mostraram que o algoritmo obteve o caminho ótimo em todas as buscas. O algoritmo se mostrou mais rápido que o algoritmo de Hetzel, adaptado ao espaço 2D, com um ganho em tempo de execução entre 2,68 a 7522 vezes mais rápido. Os experimentos com o SG-Router em cenários de busca com obstáculos aleatórios mostraram um ganho em desempenho de pelo menos 11, para os cenários com mais obstáculos, e de até 1897, para os cenários médios. O algoritmo apresentou uma deficiência para lidar com cenários semelhantes a labirintos, pois nesses casos o algoritmo apresenta uma facilidade para ocasionar estouros de memória. Esse problema impediu sua aplicação no roteamento detalhado. Contudo, o empecilho não é definitivo e pode ser contornado. O trabalho também sugere futuras melhorias para o SG-Router, tornando-o um algoritmo promissor para o roteamento detalhado e para cenários de busca mais genéricos. |
|---|
