Aceleração da legalização de circuitos integrados utilizando particionamento com k-d trees

Abstract

O avanço tecnológico viabiliza a fabricação de circuitos integrados formados por milhares de células. Devido a grande complexidade das regras de projeto, o posicionamento inicial das células desconsidera algumas dessas regras. A etapa de legalização é responsável por resolver algumas destas violações. Para preservar a qualidade inicial do posicionamento global, a legalização deve ser realizada de forma a minimizar a perturbação no posicionamento. O particionamento do circuito pode acelerar a legalização, pois reduz o tamanho da entrada para o algoritmo de legalização e também por permitir a legalização em paralelo das partições. Neste trabalho, será proposto o uso da estrutura de dados k-d tree para particionar o circuito. Como caso de uso, o algoritmo de legalização utilizado foi uma modificação do algoritmo clássico Abacus, juntamente com os circuitos das competições ICCAD2015 e ICCAD2017. Os resultados incluem um speedup de até 36 utilizando um processador com 4 núcleos, em relação a versão sequencial sem particionamento para os circuitos da competição ICCAD2015 CAD contest. O particionamento também foi capaz de reduzir o deslocamento médio das células em até 17% em relação a versão sem particionamento.

Abstract: Technological advances have enabled the manufacture of integrated circuits composed of millions of cells.Due to the high complexity of design rules, the initial placement of cells disregards some of these rules.The legalization step is responsible for solving some of those violations. In order to preserve the quality of the global placement, the legalization must try to minimize the placement perturbation. The partitioning of a circuit may speed up the legalization, because it reduces the input size for the algorithm and it also enables the legalization of partitions in parallel. In this work, we propose the use of the k-d tree data structure to partition the circuit. As a case of use, the legalization algorithm chosen was a modification of the classic Abacus, with the circuits from the ICCAD2015 and ICCAD2017 contests. Experimental results show a speedup of up to 36 using a processor with 4 cores, in relation to the sequential legalization without partitioning for the circuits of the ICCAD2015 CAD contest. The partitioning has also enabled the reduction of the average displacement of cells by up to 17% in relation to the non-partitioning version.