Search

Submitted by Simone Maisonave (simonemaisonave@hotmail.com) on 2022-08-26T13:13:28Z No. of bitstreams: 2 license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) Dissertacao_Stephano_Machado_Moreira_Goncalves.pdf: 2108746 bytes, checksum: ac81be6b020d26b5057b1702dfd896e3 (MD5) Approved for entry into archive by Simone Maisonave (simonemaisonave@hotmail.com) on 2022-08-26T13:13:37Z (GMT) No. of bitstreams: 2 license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) Dissertacao_Stephano_Machado_Moreira_Goncalves.pdf: 2108746 bytes, checksum: ac81be6b020d26b5057b1702dfd896e3 (MD5) Made available in DSpace on 2022-08-26T13:13:37Z (GMT). No. of bitstreams: 2 license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) Dissertacao_Stephano_Machado_Moreira_Goncalves.pdf: 2108746 bytes, checksum: ac81be6b020d26b5057b1702dfd896e3 (MD5) Previous issue date: 2016-03-04 Fundação de Amparo à Pesquisa do Estado do Rio Grande do Sul - FAPERGS 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. The process of circuit synthesis has an enormous complexity involved, requiring the use of algorithms to automate the procedures. One of the stages of this long process is the routing, which aims to determine the wiring routes connecting the circuit components. The routing step is divided in global and detailed routing. In detailed routing, path-search algorithms on grids are used to determine the wiring routes. However, it is expected that these algorithms are able to handle at least the most basic design rules. Thus, considering that routing is very time consuming, this paper proposes a new generic path-search algorithm on three-dimensional grids, called SG-Router, able to handle some of the simpler design rules. The goal of the proposal is to perform a comparison, regarding runtime and path quality, with Hetzel’s algorithm, which is the state of the art of the generic path-search algorithms on grid, used in detailed routing. The paper also presents some proposals of optimizations, regarding time and search quality of the already existing version of the algorithm, which works only in two-dimensional scope. Most of these optimizations were reused in the SG-Router. The experiments performed on the improved two-dimensional version of the algorithm showed that the algorithm obtained the optimal path in all searches. The algorithm was faster than Hetzel’s algorithm, adapted to 2D space, presenting a speedup between 2,68 and 7522. The experiments with the SG-Router in random search scenarios showed a speedup of at least 11, for scenarios with more obstacles, and up to 1857, for average scenarios. The algorithm presented a deficiency to handle scenarios similar to labyrinths, since in these cases the algorithm can easily cause memory overflow. This problem prevented the use of the algorithm in detailed routing. However, the drawback is not final and can be bypassed. This work also suggests future improvements to the SG-Router, making it a promising algorithm for the detailed routing and more generic search scenarios.