Analytical detailed placement algorithm for critical paths

O posicionamento das portas lógicas tem papel fundamental na qualidade de um circuito digital. A qualidade do posicionamento impacta diretamente na tamanho do circuito, no tempo de propagação dos sinais, consumo de energia, área com problemas de aquecimento, demanda de recursos de roteamento, etc. Desse modo, algoritmos de posicionamento de portas lógicas tem sido investigado por muitas décadas em busca de soluções de posicionamento com melhor qualidade e com o menor tempo de execução possível. Além disso, o posicionamento de portas lógicas é um problema de otimização combinatorial e ele é um dos problemas pertencentes a classe NP-Difícil. Desse modo, obter a solução ótima em tempo computalcional razoável é praticamente impossível. Portanto, a investigação de técnicas e algoritmos que provenham melhores soluções do que as obtidas atualmente para o posicionamento de portas lógicas é de fundamental importância para o contínuo avanço da indústria de microeletrônica. Neste trabalho foi proposto um algoritmo de posicionamento analítico detalhado para minimizar as violações no tempo de propagação dos sinais de dados. O algoritmo proposto é uma adaptação de um algoritmo de posicionamento analítico quadrático da etapa de posicionamento global para atuar sobre as portas lógicas combinacionais dos caminhos críticos na etapa de posicionamento detalhado. As portas lógicas movimentadas pela formulação propostas são aquelas combinacionais pertencentes aos caminhos críticos e aquelas que são vizinhas no primeiro nível lógico das pertencentes aos caminhos críticos. O algoritmo proposto opera somente sobre os caminhos com violações no tempo de propagação de late dos sinais de dados. A validação experimental do algoritmo proposto mostrou que as violações de Worst Negative Slack (WNS) e Total Negative Slack (TNS) foram reduzidas, respectivamente, em até 47,9% e 59,6% no tempo de propagação dos sinais de dados. Portanto, a qualidade do posicionamento detalhado incrementa em até 5%. Por outro lado, as violações de Average Bin Utilization (ABU) incrementam em até 5,5%. O algoritmo de posicionamento analítico detalhado opera sobre no máximo 1% do total de portas lógicas dos circuitos analisados.The logical gates placement has a fundamental impact on the placement quality of the circuit. The placement quality impacts directly on circuit size, timing propagation, power consumption, hotspot areas, etc. Therefore, placement algorithms have been researched for a long time to improve placement quality with less runtime to find a good solution to the placement problem. In this work was proposed an analytical detailed placement algorithm to minimize timing propagation violations. The proposed algorithm was adapted from a quadratic algorithm of the global placement step to handle critical paths in detailed placement step. Detailed quadratic algorithm moves gates in critical paths and the gates in the first deep logical level of the ones in critical paths that are the immediate neighbors. The detailed analytical algorithm works only in combinational gates that are part of critical paths and for ones in late critical paths. The experimental validation of the proposed detailed analytical algorithm shows a reduction in WNS and TNS violation, respectively, up to 47.9% and 59.6% in timing propagation. Therefore, detailed placement quality had improved up to 5%. Otherwise, ABU penalty also increased up to 5.5%. In our formulation is moved up to 1% of the total number of gates in the benchmarks