Defesa de Dissertação – Stèphano Gonçalves

por ·

Título: Um Novo Algoritmo de Busca de Caminhos e uma Avaliação de sua Aplicabilidade no Roteamento Detalhado

Autor: STÈPHANO MACHADO MOREIRA GONÇALVES

Orientação:

  • Felipe Marques, Orientador (Orientador, PPGC-UFPel)
  • Leomar Soares da Rosa Junior (Co-orientador, PPGC-UFPel)

Banca Examinadora:

  • Paulo R. Ferreira Jr. (PPGC-UFPel)
  • Rafael Soares (PPGC-UFPel)
  • Marcelo Johann (UFRGS)

Data: 4 de Março de 2016

Hora: 14:00

Local: Lab. 1 (Sala 445), 4º andar do Campus Porto

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. Devido a grande dificuldade inerente ao problema, o roteamento é dividido em duas etapas: roteamento global e roteamento detalhado. O roteamento detalhado tem como objetivo definir as rotas dos fios, respeitando as regras de projeto impostas pela tecnologia utilizada. Para isso, podem ser utilizados algoritmos de busca de caminhos especializados para atender grande parte das regras, ou algoritmos mais genéricos, mas que consigam lidar com as regras mais simples. Dos últimos mencionados, o algoritmo de Hetzel é o estado da arte. Assim, considerando que o roteamento consome muito tempo, e que tempo também é um fator importante para a síntese de circuitos, este trabalho propõe um novo algoritmo de busca de caminhos genérico, chamado SG-Router, mas com capacidade de lidar com algumas das regras de projeto mais simples. O trabalho também apresenta uma série de propostas de otimizações de tempo e 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 apontam que o algoritmo garante o caminho ótimo, e mostram que ele é muito mais rápido que o algoritmo de Hetzel, adaptado ao espaço 2D. Os experimentos com o SG-Router mostraram um enorme ganho em desempenho em relação ao algoritmo de Hetzel, para cenários de busca aleatórios. Porém, o algoritmo apresentou uma deficiência, que o limita de certa forma, o que se mostrou um empecilho para 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.