Jezz : an effective legalization algorithm for minimum overall displacement

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.

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.