Este trabalho abor da um e studo de algoritmo s e arquiteturas de um Analisador de Interconexões. Várias alternativas possíveis são discutidas e uma análise de custo e desempenho é feita. Alguns dos algoritmos e arquiteturas propostos parecem ser novos se comparados à literatura publicada. Um dos algoritmos foi completamente simulado para auxiliar a análise de desempenho e para demonstrar a interface com o usuário em uma aplicação comercial. / This work deals with a study of algorithms and architectures of an Interconnection Analyzer. Several possible alternatives are discussed and an analysis of cost and performance is carried out. Some of the prop osed algorithms and architectures seems to be new when compared to the published literature. One of the algorithms was fully simulated to help the performance analysis and to demonstrate the user interface in a commercial application.

Este trabalho abor da um e studo de algoritmo s e arquiteturas de um Analisador de Interconexões. Várias alternativas possíveis são discutidas e uma análise de custo e desempenho é feita. Alguns dos algoritmos e arquiteturas propostos parecem ser novos se comparados à literatura publicada. Um dos algoritmos foi completamente simulado para auxiliar a análise de desempenho e para demonstrar a interface com o usuário em uma aplicação comercial. / This work deals with a study of algorithms and architectures of an Interconnection Analyzer. Several possible alternatives are discussed and an analysis of cost and performance is carried out. Some of the prop osed algorithms and architectures seems to be new when compared to the published literature. One of the algorithms was fully simulated to help the performance analysis and to demonstrate the user interface in a commercial application.

Este trabalho abor da um e studo de algoritmo s e arquiteturas de um Analisador de Interconexões. Várias alternativas possíveis são discutidas e uma análise de custo e desempenho é feita. Alguns dos algoritmos e arquiteturas propostos parecem ser novos se comparados à literatura publicada. Um dos algoritmos foi completamente simulado para auxiliar a análise de desempenho e para demonstrar a interface com o usuário em uma aplicação comercial. / This work deals with a study of algorithms and architectures of an Interconnection Analyzer. Several possible alternatives are discussed and an analysis of cost and performance is carried out. Some of the prop osed algorithms and architectures seems to be new when compared to the published literature. One of the algorithms was fully simulated to help the performance analysis and to demonstrate the user interface in a commercial application.

Este trabalho apresenta novos algoritmos para o roteamento de circuitos integrados, e discute sua aplicação em sistemas de síntese de leiaute. As interconexões têm grande impacto no desempenho de circuitos em tecnologias recentes, e os algoritmos propostos visam conferir maior controle sobre sua qualidade, e maior convergência na tarefa de encontrar uma solução aceitável. De todos os problemas de roteamento, dois são de especial importância: roteamento de redes uma a uma com algoritmos de pesquisa de caminhos, e o chamado roteamento de área. Para o primeiro, procura-se desenvolver um algoritmo de pesquisa de caminhos bidirecional e heurístico mais eficiente, LCS*, cuja aplicação em roteamento explora situações específicas que ocorrem neste domínio. Demonstra-se que o modelo de custo influencia fortemente o esforço de pesquisa, além de controlar a qualidade das rotas encontradas, e por esta razão um modelo mais preciso é proposto. Para roteamento de área, se estuda o desenvolvimento de uma nova classe de algoritmos sugerida em [JOH 94], denominados LEGAL. A viabilidade e a eficiência de tais algoritmos são demonstradas com três diferentes implementações. Devem ser também estudados mecanismos alternativos para gerenciar espaços e tratar modelos de grade não uniforme, avaliando-se suas vantagens e sua aplicabilidade em outros diferentes contextos.

Este trabalho apresenta novos algoritmos para o roteamento de circuitos integrados, e discute sua aplicação em sistemas de síntese de leiaute. As interconexões têm grande impacto no desempenho de circuitos em tecnologias recentes, e os algoritmos propostos visam conferir maior controle sobre sua qualidade, e maior convergência na tarefa de encontrar uma solução aceitável. De todos os problemas de roteamento, dois são de especial importância: roteamento de redes uma a uma com algoritmos de pesquisa de caminhos, e o chamado roteamento de área. Para o primeiro, procura-se desenvolver um algoritmo de pesquisa de caminhos bidirecional e heurístico mais eficiente, LCS*, cuja aplicação em roteamento explora situações específicas que ocorrem neste domínio. Demonstra-se que o modelo de custo influencia fortemente o esforço de pesquisa, além de controlar a qualidade das rotas encontradas, e por esta razão um modelo mais preciso é proposto. Para roteamento de área, se estuda o desenvolvimento de uma nova classe de algoritmos sugerida em [JOH 94], denominados LEGAL. A viabilidade e a eficiência de tais algoritmos são demonstradas com três diferentes implementações. Devem ser também estudados mecanismos alternativos para gerenciar espaços e tratar modelos de grade não uniforme, avaliando-se suas vantagens e sua aplicabilidade em outros diferentes contextos.

Este trabalho apresenta novos algoritmos para o roteamento de circuitos integrados, e discute sua aplicação em sistemas de síntese de leiaute. As interconexões têm grande impacto no desempenho de circuitos em tecnologias recentes, e os algoritmos propostos visam conferir maior controle sobre sua qualidade, e maior convergência na tarefa de encontrar uma solução aceitável. De todos os problemas de roteamento, dois são de especial importância: roteamento de redes uma a uma com algoritmos de pesquisa de caminhos, e o chamado roteamento de área. Para o primeiro, procura-se desenvolver um algoritmo de pesquisa de caminhos bidirecional e heurístico mais eficiente, LCS*, cuja aplicação em roteamento explora situações específicas que ocorrem neste domínio. Demonstra-se que o modelo de custo influencia fortemente o esforço de pesquisa, além de controlar a qualidade das rotas encontradas, e por esta razão um modelo mais preciso é proposto. Para roteamento de área, se estuda o desenvolvimento de uma nova classe de algoritmos sugerida em [JOH 94], denominados LEGAL. A viabilidade e a eficiência de tais algoritmos são demonstradas com três diferentes implementações. Devem ser também estudados mecanismos alternativos para gerenciar espaços e tratar modelos de grade não uniforme, avaliando-se suas vantagens e sua aplicabilidade em outros diferentes contextos.

Este trabalho apresenta a implementação de um roteador global de circuitos integrados capaz de tratar os problemas de roteamento atuais, utilizando como referência para avaliação os circuitos de benchmark publicados durante as competições de roteamento global realizadas no ACM International Symposium on Physical Design 2007 e 2008. O roteador global desenvolvido utiliza como ferramenta principal a técnica de ripup and reroute associada às técnicas de roteamento monotônico e maze routing, ambas com grande histórico de uso nas ferramentas acadêmicas descritas também neste trabalho. O desenvolvimento da ferramenta também possui características diferenciadas e únicas, com um novo método de ordenamento das redes durante a fase de rip-up and reroute. Para a geração dos resultados foram definidas duas versões diferentes da ferramenta, sendo estas duas versões analisadas com duas diferentes técnicas de construção das árvores de roteamento, gerando no total quatro configurações da ferramenta. Como decisão de projeto, a versão principal utilizada no desenvolvimento e discussão dos resultados é a versão que prioriza a qualidade do roteamento, utilizando MSTs para construção das árvores de roteamento. Os resultados mostram que o roteador global desenvolvido é capaz de gerar resultados com boa qualidade mesmo sem fazer uso de técnicas de identificação de áreas de congestionamento, sem otimizações pós-roteamento e sem nenhuma forma de ajuste (tuning) para os diferentes circuitos de benchmark, apesar de ainda ter tempo de execução acima dos apresentados por outras ferramentas acadêmicas. O foco durante o processo de desenvolvimento e implementação da ferramenta foram os circuitos mais recentes, entretanto a ferramenta obteve ótimos resultados também para os circuitos publicados no ISPD 1998, gerando soluções com qualidade similar ou melhor que as reportadas na literatura. A diferença dos resultados deste trabalho em relação aos melhores resultados dos roteadores globais com código disponível, para circuitos 3D lançados no ISPD 2008 é de, em média, 1,78%1 na métrica de comprimento de fio sem considerar o custo das vias e de 15,56% considerando o custo da via como uma unidade de comprimento de fio (ISPD 2008), para a versão voltada a qualidade de roteamento. Já para a versão da ferramenta que busca a convergência o mais rápido possível a diferença foi de 3,39% e 16,32%, respectivamente. As maiores diferenças são encontradas nos circuitos mais difíceis de gerar uma solução sem violações. Isso mostra como as técnicas de identificação de região podem contribuir tanto para uma convergência mais rápida quanto para evitar que fios passem por rotas desnecessárias durante a fase de negociação. Na métrica que avalia as vias como custo de uma unidade de comprimento, os resultados obtidos apresentam em média 18,67% maior comprimento de fio que os melhores resultados da literatura, sendo que dois circuitos com solução sem violações2 apresentam resultado com violações utilizando a ferramenta desenvolvida neste trabalho. / This work describes the implementation of an integrated circuit global router capable of handling the current routing problems, using as a reference the evaluation of benchmark circuits from the two global routing contests held in ISPD 2007 and 2008. The developed global router uses rip-up and reroute as the main technique associated with monotonic and maze routing techniques, both with large history of use in academic tools, also described in this work. The tool also has distinctive and unique characteristics, with a new method of net ordering during the rip-up and reroute stage. In order to generate the results were defined two different versions of the tool analyzed with two different techniques of routing tree construction, generating a total of four configurations. As a design decision, the major version used in the development and discussion of results is the version that prioritizes the routing quality, using MSTs for tree construction. The results show that the global router developed is able to generate good results even without making use of techniques to identify congestion areas, without post-routing optimizations and without any form of tuning for the different benchmark circuits, despite having run time above other academic tools. The focus during the development and implementation of the tool were the newer circuits, however the tool also obtained excellent results for the circuits released in ISPD 1998, generating solutions with similar quality or better than those reported in the literature. The difference in the results of this work over the best results generated with the available code global routers for 3D circuits released in ISPD 2008 is, on average, 2.53% in wirelength metric without considering the cost of vias and 18.34% considering the cost of the vias as one wirelength unit (ISPD 2008), for the best routing quality version. As for the version of the tool that seeks convergence as soon as possible the difference was 3.82% and 17.03%, respectively. The largest differences were found in the most difficult circuits to generate a solution without violations. This shows how the techniques of congested region identification can contribute to both a faster convergence and to avoid unnecessary wire detours during the negotiation phase. In the metric that evaluates the cost of vias as one wirelength unit, the results show an average of 22.5% greater wirelength than the best results found in literature. Also, the developed global router was unable to find a violation free solution for two circuits that are known to have a violation free solution3.

Este trabalho apresenta a implementação de um roteador global de circuitos integrados capaz de tratar os problemas de roteamento atuais, utilizando como referência para avaliação os circuitos de benchmark publicados durante as competições de roteamento global realizadas no ACM International Symposium on Physical Design 2007 e 2008. O roteador global desenvolvido utiliza como ferramenta principal a técnica de ripup and reroute associada às técnicas de roteamento monotônico e maze routing, ambas com grande histórico de uso nas ferramentas acadêmicas descritas também neste trabalho. O desenvolvimento da ferramenta também possui características diferenciadas e únicas, com um novo método de ordenamento das redes durante a fase de rip-up and reroute. Para a geração dos resultados foram definidas duas versões diferentes da ferramenta, sendo estas duas versões analisadas com duas diferentes técnicas de construção das árvores de roteamento, gerando no total quatro configurações da ferramenta. Como decisão de projeto, a versão principal utilizada no desenvolvimento e discussão dos resultados é a versão que prioriza a qualidade do roteamento, utilizando MSTs para construção das árvores de roteamento. Os resultados mostram que o roteador global desenvolvido é capaz de gerar resultados com boa qualidade mesmo sem fazer uso de técnicas de identificação de áreas de congestionamento, sem otimizações pós-roteamento e sem nenhuma forma de ajuste (tuning) para os diferentes circuitos de benchmark, apesar de ainda ter tempo de execução acima dos apresentados por outras ferramentas acadêmicas. O foco durante o processo de desenvolvimento e implementação da ferramenta foram os circuitos mais recentes, entretanto a ferramenta obteve ótimos resultados também para os circuitos publicados no ISPD 1998, gerando soluções com qualidade similar ou melhor que as reportadas na literatura. A diferença dos resultados deste trabalho em relação aos melhores resultados dos roteadores globais com código disponível, para circuitos 3D lançados no ISPD 2008 é de, em média, 1,78%1 na métrica de comprimento de fio sem considerar o custo das vias e de 15,56% considerando o custo da via como uma unidade de comprimento de fio (ISPD 2008), para a versão voltada a qualidade de roteamento. Já para a versão da ferramenta que busca a convergência o mais rápido possível a diferença foi de 3,39% e 16,32%, respectivamente. As maiores diferenças são encontradas nos circuitos mais difíceis de gerar uma solução sem violações. Isso mostra como as técnicas de identificação de região podem contribuir tanto para uma convergência mais rápida quanto para evitar que fios passem por rotas desnecessárias durante a fase de negociação. Na métrica que avalia as vias como custo de uma unidade de comprimento, os resultados obtidos apresentam em média 18,67% maior comprimento de fio que os melhores resultados da literatura, sendo que dois circuitos com solução sem violações2 apresentam resultado com violações utilizando a ferramenta desenvolvida neste trabalho. / This work describes the implementation of an integrated circuit global router capable of handling the current routing problems, using as a reference the evaluation of benchmark circuits from the two global routing contests held in ISPD 2007 and 2008. The developed global router uses rip-up and reroute as the main technique associated with monotonic and maze routing techniques, both with large history of use in academic tools, also described in this work. The tool also has distinctive and unique characteristics, with a new method of net ordering during the rip-up and reroute stage. In order to generate the results were defined two different versions of the tool analyzed with two different techniques of routing tree construction, generating a total of four configurations. As a design decision, the major version used in the development and discussion of results is the version that prioritizes the routing quality, using MSTs for tree construction. The results show that the global router developed is able to generate good results even without making use of techniques to identify congestion areas, without post-routing optimizations and without any form of tuning for the different benchmark circuits, despite having run time above other academic tools. The focus during the development and implementation of the tool were the newer circuits, however the tool also obtained excellent results for the circuits released in ISPD 1998, generating solutions with similar quality or better than those reported in the literature. The difference in the results of this work over the best results generated with the available code global routers for 3D circuits released in ISPD 2008 is, on average, 2.53% in wirelength metric without considering the cost of vias and 18.34% considering the cost of the vias as one wirelength unit (ISPD 2008), for the best routing quality version. As for the version of the tool that seeks convergence as soon as possible the difference was 3.82% and 17.03%, respectively. The largest differences were found in the most difficult circuits to generate a solution without violations. This shows how the techniques of congested region identification can contribute to both a faster convergence and to avoid unnecessary wire detours during the negotiation phase. In the metric that evaluates the cost of vias as one wirelength unit, the results show an average of 22.5% greater wirelength than the best results found in literature. Also, the developed global router was unable to find a violation free solution for two circuits that are known to have a violation free solution3.

Este trabalho apresenta a implementação de um roteador global de circuitos integrados capaz de tratar os problemas de roteamento atuais, utilizando como referência para avaliação os circuitos de benchmark publicados durante as competições de roteamento global realizadas no ACM International Symposium on Physical Design 2007 e 2008. O roteador global desenvolvido utiliza como ferramenta principal a técnica de ripup and reroute associada às técnicas de roteamento monotônico e maze routing, ambas com grande histórico de uso nas ferramentas acadêmicas descritas também neste trabalho. O desenvolvimento da ferramenta também possui características diferenciadas e únicas, com um novo método de ordenamento das redes durante a fase de rip-up and reroute. Para a geração dos resultados foram definidas duas versões diferentes da ferramenta, sendo estas duas versões analisadas com duas diferentes técnicas de construção das árvores de roteamento, gerando no total quatro configurações da ferramenta. Como decisão de projeto, a versão principal utilizada no desenvolvimento e discussão dos resultados é a versão que prioriza a qualidade do roteamento, utilizando MSTs para construção das árvores de roteamento. Os resultados mostram que o roteador global desenvolvido é capaz de gerar resultados com boa qualidade mesmo sem fazer uso de técnicas de identificação de áreas de congestionamento, sem otimizações pós-roteamento e sem nenhuma forma de ajuste (tuning) para os diferentes circuitos de benchmark, apesar de ainda ter tempo de execução acima dos apresentados por outras ferramentas acadêmicas. O foco durante o processo de desenvolvimento e implementação da ferramenta foram os circuitos mais recentes, entretanto a ferramenta obteve ótimos resultados também para os circuitos publicados no ISPD 1998, gerando soluções com qualidade similar ou melhor que as reportadas na literatura. A diferença dos resultados deste trabalho em relação aos melhores resultados dos roteadores globais com código disponível, para circuitos 3D lançados no ISPD 2008 é de, em média, 1,78%1 na métrica de comprimento de fio sem considerar o custo das vias e de 15,56% considerando o custo da via como uma unidade de comprimento de fio (ISPD 2008), para a versão voltada a qualidade de roteamento. Já para a versão da ferramenta que busca a convergência o mais rápido possível a diferença foi de 3,39% e 16,32%, respectivamente. As maiores diferenças são encontradas nos circuitos mais difíceis de gerar uma solução sem violações. Isso mostra como as técnicas de identificação de região podem contribuir tanto para uma convergência mais rápida quanto para evitar que fios passem por rotas desnecessárias durante a fase de negociação. Na métrica que avalia as vias como custo de uma unidade de comprimento, os resultados obtidos apresentam em média 18,67% maior comprimento de fio que os melhores resultados da literatura, sendo que dois circuitos com solução sem violações2 apresentam resultado com violações utilizando a ferramenta desenvolvida neste trabalho. / This work describes the implementation of an integrated circuit global router capable of handling the current routing problems, using as a reference the evaluation of benchmark circuits from the two global routing contests held in ISPD 2007 and 2008. The developed global router uses rip-up and reroute as the main technique associated with monotonic and maze routing techniques, both with large history of use in academic tools, also described in this work. The tool also has distinctive and unique characteristics, with a new method of net ordering during the rip-up and reroute stage. In order to generate the results were defined two different versions of the tool analyzed with two different techniques of routing tree construction, generating a total of four configurations. As a design decision, the major version used in the development and discussion of results is the version that prioritizes the routing quality, using MSTs for tree construction. The results show that the global router developed is able to generate good results even without making use of techniques to identify congestion areas, without post-routing optimizations and without any form of tuning for the different benchmark circuits, despite having run time above other academic tools. The focus during the development and implementation of the tool were the newer circuits, however the tool also obtained excellent results for the circuits released in ISPD 1998, generating solutions with similar quality or better than those reported in the literature. The difference in the results of this work over the best results generated with the available code global routers for 3D circuits released in ISPD 2008 is, on average, 2.53% in wirelength metric without considering the cost of vias and 18.34% considering the cost of the vias as one wirelength unit (ISPD 2008), for the best routing quality version. As for the version of the tool that seeks convergence as soon as possible the difference was 3.82% and 17.03%, respectively. The largest differences were found in the most difficult circuits to generate a solution without violations. This shows how the techniques of congested region identification can contribute to both a faster convergence and to avoid unnecessary wire detours during the negotiation phase. In the metric that evaluates the cost of vias as one wirelength unit, the results show an average of 22.5% greater wirelength than the best results found in literature. Also, the developed global router was unable to find a violation free solution for two circuits that are known to have a violation free solution3.