{"id":3991,"date":"2016-03-03T10:40:48","date_gmt":"2016-03-03T12:40:48","guid":{"rendered":"http:\/\/inf.ufpel.edu.br\/site\/?p=3991"},"modified":"2016-03-03T10:40:48","modified_gmt":"2016-03-03T12:40:48","slug":"defesa-de-dissertacao-stephano-goncalves","status":"publish","type":"post","link":"https:\/\/wp.ufpel.edu.br\/computacao\/noticia\/defesa-de-dissertacao-stephano-goncalves\/","title":{"rendered":"Defesa de Disserta\u00e7\u00e3o &#8211; St\u00e8phano Gon\u00e7alves"},"content":{"rendered":"<p><strong>T\u00edtulo<\/strong>: Um Novo Algoritmo de Busca de Caminhos e uma Avalia\u00e7\u00e3o de sua Aplicabilidade no Roteamento Detalhado<\/p>\n<p><strong>Autor<\/strong>: ST\u00c8PHANO MACHADO MOREIRA GON\u00c7ALVES<\/p>\n<p><strong>Orienta\u00e7\u00e3o:<\/strong><\/p>\n<ul>\n<li>Felipe Marques, Orientador (Orientador, PPGC-UFPel)<\/li>\n<li>Leomar Soares da Rosa Junior (Co-orientador, PPGC-UFPel)<\/li>\n<\/ul>\n<p><strong>Banca Examinadora:<\/strong><\/p>\n<ul>\n<li>Paulo R. Ferreira Jr. (PPGC-UFPel)<\/li>\n<li>Rafael Soares (PPGC-UFPel)<\/li>\n<li>Marcelo Johann (UFRGS)<\/li>\n<\/ul>\n<p><strong>Data<\/strong>: 4 de Mar\u00e7o de 2016<\/p>\n<p><strong>Hora<\/strong>: 14:00<\/p>\n<p><strong>Local<\/strong>: Lab. 1 (Sala 445), 4\u00ba andar do Campus Porto<\/p>\n<p><strong>Resumo<\/strong>:<br \/>\nO processo de s\u00edntese de circuitos possui uma enorme complexidade envolvida, exigindo o uso de algoritmos para automatizar os procedimentos. Uma das etapas desse grande processo \u00e9 o roteamento, que visa determinar as rotas dos fios que conectam os componentes do circuito. Devido a grande dificuldade inerente ao problema, o roteamento \u00e9 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\u00e9ricos, mas que consigam lidar com as regras mais simples. Dos \u00faltimos mencionados, o algoritmo de Hetzel \u00e9 o estado da arte. Assim, considerando que o roteamento consome muito tempo, e que tempo tamb\u00e9m \u00e9 um fator importante para a s\u00edntese de circuitos, este trabalho prop\u00f5e um novo algoritmo de busca de caminhos gen\u00e9rico, chamado SG-Router, mas com capacidade de lidar com algumas das regras de projeto mais simples. O trabalho tamb\u00e9m apresenta uma s\u00e9rie de propostas de otimiza\u00e7\u00f5es de tempo e qualidade de busca para a vers\u00e3o preexistente do algoritmo, que funciona apenas no escopo bidimensional. Grande parte dessas otimiza\u00e7\u00f5es foram reaproveitadas no SG-Router. Os experimentos realizados na vers\u00e3o bidimensional melhorada apontam que o algoritmo garante o caminho \u00f3timo, e mostram que ele \u00e9 muito mais r\u00e1pido que o algoritmo de Hetzel, adaptado ao espa\u00e7o 2D. Os experimentos com o SG-Router mostraram um enorme ganho em desempenho em rela\u00e7\u00e3o ao algoritmo de Hetzel, para cen\u00e1rios de busca aleat\u00f3rios. Por\u00e9m, o algoritmo apresentou uma defici\u00eancia, que o limita de certa forma, o que se mostrou um empecilho para sua aplica\u00e7\u00e3o no roteamento detalhado. Contudo, o empecilho n\u00e3o \u00e9 definitivo e pode ser contornado. O trabalho tamb\u00e9m sugere futuras melhorias para o SG-Router, tornando-o um algoritmo promissor para o roteamento detalhado e para cen\u00e1rios de busca mais gen\u00e9ricos.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>T\u00edtulo: Um Novo Algoritmo de Busca de Caminhos e uma Avalia\u00e7\u00e3o de sua Aplicabilidade no Roteamento Detalhado Autor: ST\u00c8PHANO MACHADO MOREIRA GON\u00c7ALVES Orienta\u00e7\u00e3o: Felipe Marques, Orientador (Orientador, PPGC-UFPel) Leomar Soares da Rosa Junior (Co-orientador,&#46;&#46;&#46;<\/p>\n","protected":false},"author":881,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_publicize_message":"","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":true,"jetpack_social_options":{"image_generator_settings":{"template":"highway","default_image_id":0,"font":"","enabled":false},"version":2}},"categories":[17,23],"tags":[],"class_list":["post-3991","post","type-post","status-publish","format-standard","hentry","category-noticia","category-ppgc"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"jetpack_shortlink":"https:\/\/wp.me\/paGhNl-12n","_links":{"self":[{"href":"https:\/\/wp.ufpel.edu.br\/computacao\/wp-json\/wp\/v2\/posts\/3991","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/wp.ufpel.edu.br\/computacao\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/wp.ufpel.edu.br\/computacao\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/wp.ufpel.edu.br\/computacao\/wp-json\/wp\/v2\/users\/881"}],"replies":[{"embeddable":true,"href":"https:\/\/wp.ufpel.edu.br\/computacao\/wp-json\/wp\/v2\/comments?post=3991"}],"version-history":[{"count":0,"href":"https:\/\/wp.ufpel.edu.br\/computacao\/wp-json\/wp\/v2\/posts\/3991\/revisions"}],"wp:attachment":[{"href":"https:\/\/wp.ufpel.edu.br\/computacao\/wp-json\/wp\/v2\/media?parent=3991"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/wp.ufpel.edu.br\/computacao\/wp-json\/wp\/v2\/categories?post=3991"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/wp.ufpel.edu.br\/computacao\/wp-json\/wp\/v2\/tags?post=3991"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}