Digital Repository

A- A A+

Algoritmos para o posicionamento de células em circuitos VLSI

DSpace/Manakin Repository

Algoritmos para o posicionamento de células em circuitos VLSI

Show full item record

Statistics

Title Algoritmos para o posicionamento de células em circuitos VLSI
Author Hentschke, Renato Fernandes
Advisor Reis, Ricardo Augusto da Luz
Date 2002
Level Master
Institution Universidade Federal do Rio Grande do Sul. Instituto de Informática. Programa de Pós-Graduação em Computação.
Subject Algoritmos : Posicionamento
Cad : Microeletronica
Microeletronica
Sintese fisica
Abstract in Portuguese Este trabalho faz uma análise ampla sobre os algoritmos de posicionamento. Diversos são extraídos da literatura e de publicações recentes de posicionamento. Eles foram implementados para uma comparação mais precisa. Novos métodos são propostos, com resultados promissores. A maior parte dos algoritmos, ao contrário do que costuma encontrar-se na literatura, é explicada com detalhes de implementação, de forma que não fiquem questões em aberto. Isto só possível pela forte base de implementação por trás deste texto. O algorítmo de Fidduccia Mateyeses, por exemplo, é um algorítmo complexo e por isto foi explicado com detalhes de implementação. Assim como uma revisão de técnicas conhecidas e publicadas, este trabalho oferece algumas inovações no fluxo de posicionamento. Propõe-se um novo algorítimo para posicionamento inicial, bem como uma variação inédita do Cluster Growth que mostrta ótimos resultados. É apresentada uma série de evoluções ao algorítmo de Simulated Annealling: cálculo automático de temperatura inicial, funções de perturbação gulosas (direcionadas a força), combinação de funções de perturbação atingindo melhores resultados (em torno de 20%), otimização no cálculo de tamanho dos fios (avaliação das redes modificadas e aproveitamento de cálculos anteriores, com ganhos em torno de 45%). Todas estas modificações propiciam uma maior velocidade e convergência do método de Simulated Annealling. É mostrado que os algorítmos construtivos (incluindo o posicionador do Tropic, baseado em quadratura com Terminal Propagation) apresentam um resultado pior que o Simulated Annealling em termos de qualidade de posicionamento às custas de um longo tempo de CPD. Porém, o uso de técnicas propostas neste trabalho, em conjunto com outras técnicas propostas em outros trabalhos (como o trabalho de Lixin Su) podem acelerar o SA, de forma que a relação qualidade/tempo aumente.
Type Dissertation
URI http://hdl.handle.net/10183/2598
Files Description Format View
000373357.pdf (2.362Mb) Texto completo Adobe PDF View/Open

This item is licensed under a Creative Commons License

This item appears in the following Collection(s)


Show full item record

Browse



  • The author is the owner of the copyrights of the documents available in this repository and is prohibited under the law, the marketing of any kind without prior authorization.
    Graphic design by Caixola - Clube de Criação Fabico/UFRGS Powered by DSpace software, Version 1.8.1.