Repositório Digital

A- A A+

Jezz : an effective legalization algorithm for minimum overall displacement

.

Jezz : an effective legalization algorithm for minimum overall displacement

Mostrar registro completo

Estatísticas

Título Jezz : an effective legalization algorithm for minimum overall displacement
Autor Puget, Julia Casarin
Orientador Reis, Ricardo Augusto da Luz
Co-orientador Flach, Guilherme Augusto
Data 2015
Nível Graduação
Instituição Universidade Federal do Rio Grande do Sul. Instituto de Informática. Curso de Ciência da Computação: Ênfase em Engenharia da Computação: Bacharelado.
Assunto Circuitos integrados : Microeletrônica
Microeletronica
[en] Disturbance
[en] Disturbance
[en] Incremental
[en] Legalization
[en] Legalization
[en] Microelectronics
[en] Minimum
[en] Placement
[en] Placement
[en] Standard-cell
Abstract Legalization is one of the three stages in which logic gate placement is subdivided in the physical synthesis of an integrated circuit. This stage consists of selecting positions considered to be valid for the logic gates, that is, positions that are alligned to the rows that divide the circuit area and where there is no overlapping among the gates. In addition to organizing the logic gates in valid positions, a well made legalization needs to provide a smooth transition between global placement, the first stage of placement, and detailed placement, the last stage, in such a way that the solution that had been reached in global placement is modified the least possible. In this work, a study on the legalization algorithms is performed, covering algorithms present today and a classic one. Also, a legalization algorithm called Jezz is proposed. To verify the effectiveness of it, a comparison between it and two others has been made, being these two Tetris (HILL, 2002), which is a classical algorithm, and Abacus (SPINDLER; SCHLICHTMANN; JOHANNES, 2008), which is an algorithm that is simmilar to Jezz, and that had been proposed as an algorithm superior to Tetris when it comes to overall displacement of the logic gates with respect to their original positions pre-legalization. Jezz is similar to Abacus, being the main difference between them that, whilst Jezz uses a linear function (Manhattan distance) to calculate the cost of displacing cells, Abacus uses a quadratic function.
Resumo Legalização é um dos três estágios em que se subdivide o posicionamento de portas lógicas na síntese física de um circuito integrado. Esse estágio consiste na seleção de posições consideradas válidas para as portas lógicas, ou seja, posições que estejam alinhadas às bandas divisoras do circuito, e em que não haja sobreposições. Além de organizar as portas lógicas em posições válidas, uma legalização bem feita necessita prover uma transição suave entre o posicionamento global, o primeiro estágio do posicionamento, e o posicionamento detalhado, o último estágio, de forma que a solução alcançada no posicionamento global seja modificada o mínimo possível. Neste trabalho, é feito um estudo sobre os algoritmos de legalização presentes na atualidade, suas diferenças, e também é proposto um algoritmo de legalização chamado Jezz. Para comprovar a eficiência de tal algoritmo, foi realizada uma comparação entre ele e outros dois algoritmos de legalização, Tetris (HILL, 2002), que é um algoritmo clássico, e Abacus (SPINDLER; SCHLICHTMANN; JOHANNES, 2008), que é um algoritmo semelhante a Jezz, que havia sido proposto como um algoritmo superior a Tetris no tocante ao distanciamento total das portas lógicas em relação às suas posições originais. Jezz é um algoritmo semelhante ao Abacus, sendo a diferença básica entre eles de que Jezz usa uma função linear (distância de Manhattan) para calcular o custo de mover células, enquanto Abacus usa uma função quadrática.
Tipo Trabalho de conclusão de graduação
URI http://hdl.handle.net/10183/126056
Arquivos Descrição Formato
000971920.pdf (929.9Kb) Texto completo Adobe PDF Visualizar/abrir

Este item está licenciado na Creative Commons License

Este item aparece na(s) seguinte(s) coleção(ões)


Mostrar registro completo

Percorrer



  • O autor é titular dos direitos autorais dos documentos disponíveis neste repositório e é vedada, nos termos da lei, a comercialização de qualquer espécie sem sua autorização prévia.
    Projeto gráfico elaborado pelo Caixola - Clube de Criação Fabico/UFRGS Powered by DSpace software, Version 1.8.1.