Dissertação (mestrado) - Universidade Federal de Santa Catarina, Centro Tecnológico, Programa de Pós-Graduação em Ciência da Computação, Florianópolis, 2017. / Made available in DSpace on 2017-06-27T04:21:26Z (GMT). No. of bitstreams: 1
345871.pdf: 3595709 bytes, checksum: f2160b79087e6603d6e09bd965793c84 (MD5)
Previous issue date: 2017 / Na síntese física de circuitos integrados, a etapa de legalização é responsável por remover sobreposições de células e alinhá-las com as linhas e colunas do circuito, enquanto minimiza o deslocamento das células. Esta etapa é aplicada não somente após o posicionamento global, mas também após etapas de otimização incremental tais como posicionamento incremental guiado por atraso, gate sizing e inserção de buffers. Quando utilizada em técnicas de otimização incremental, a legalização pode ser aplicada como um passo final, após cada iteração da otimização,ou de maneira incremental, após cada transformação no posicionamento. Infelizmente, técnicas recentes de legalização incremental utilizam estruturas de dados que não são adequadas para o armazenamento de informações sobre geometrias. Além disso, apesar de diferentes estratégias de legalização serem utilizadas por diferentes trabalhos de otimização incremental, estes trabalhos não apresentam resultados quantitativos do impacto destas estratégias no tempo de execução e qualidade da solução final. Este trabalho propõe uma técnica de legalização incremental utilizando uma estrutura de dados chamada R-tree, projetada para o armazenamento de informações sobre geometrias, permitindo buscas espaciais rápidas. A técnica proposta foi comparada atécnicas do estado da arte em legalização incremental, assim como às estratégias de legalização final e iterativa. Os resultados experimentais mostram que a técnica proposta é pelo menos 6 vezes mais rápida e realiza o mesmo número de legalizações quando comparado a outras técnicas de legalização incremental do estado da arte. Além disso, o algoritmo proposto é mais rápido que as estratégias de legalização final e iterativa, enquanto resulta em uma solução com perfil de densidade e comprimento das interconexões semelhante.<br> / Abstract : In the physical synthesis of digital circuits, circuit legalization removes overlaps and keeps cell alignment with circuit rows and sites while minimizing total cell displacement. Legalization is applied not only after global placement, but also after incremental optimization steps like incremental timing-driven placement, gate sizing, and buffer insertion. In the case of incremental optimization techniques, the legalization stepcan be applied as a final step, after each optimization iteration or incrementally, after each cell movement. Unfortunately, recent incremental legalization techniques employ data structures that are not suitable for handling geometry information. In addition, despite different legalization strategies are used by different works on incremental optimization, those works do not present quantitative results on how those strategies impact on the runtime and quality of the final solution. This work proposes a new legalization technique that relies on an R-tree, a data structure tailored to efficient geometry information storage, which allows for fast spatial search. The proposed technique was compared to state-of-the-art incremental legalization techniques, as well as to the final and iterative legalization strategies. Experimental results show that the proposed technique is at least 6 times faster and performs as many successful legalizations when compared to the related work on incremental legalization. In addition, it is faster than both the other two legalization strategies, while resulting in a solution with similar density profile and circuit wirelength.
| Identifer | oai:union.ndltd.org:IBICT/oai:repositorio.ufsc.br:123456789/176785 |
| Date | January 2017 |
| Creators | Oliveira Netto, Renan |
| Contributors | Universidade Federal de Santa Catarina, Güntzel, José Luís Almada |
| Source Sets | IBICT Brazilian ETDs |
| Language | Portuguese |
| Detected Language | Portuguese |
| Type | info:eu-repo/semantics/publishedVersion, info:eu-repo/semantics/masterThesis |
| Format | 81 p.| il., gráfs., tabs. |
| Source | reponame:Repositório Institucional da UFSC, instname:Universidade Federal de Santa Catarina, instacron:UFSC |
| Rights | info:eu-repo/semantics/openAccess |
Page generated in 0.0021 seconds