Algorithms to improve area density utilization, routability and timing during detailed placement and legalization of VLSI circuits

Abstract

Placement is a challenging stage in the Very Large-Scale Integration (VLSI) physical design flow. In modern VLSI designs, several design restrictions have been imposed to address the complexity of advanced Complementary Metal-Oxide Semiconductor (CMOS) fabrication nodes. Design restrictions have a considerable influence on achieving the optimized circuit solution. The quality of the placement solution has a significant impact on circuit performance. In placement, achieving circuit requirements of timing and routability is a very challenging task. Timing and routability requirements are especially hard to achieve in circuits which have regions with high-density area utilization. Moreover, the quality of placement has a direct influence on circuit quality and optimization effort of Clock Tree Synthesis (CTS), routing, and post-placement algorithms. In this thesis, the first contribution is an incremental timing-driven placement algorithm subject to routability. The proposed timing-driven placement algorithm relies on net and path characteristics to compute optimized-timing cell positions. Optimized-timing positions are accepted only if these positions are inside regions free of routing violation. The second contribution is a cell spreading algorithm. The objective is to move cells out of high-density regions considering adverse side effects on moved cells. The proposed cell spreading algorithm relies on network flow and branch and cut techniques to minimize high-density regions.Area flows are moved from high-density to low-density regions with optimized cost paths. Therefore, cell concentration is reduced, and white spaces are opened in high-density regions with minimized adverse side effects on moved cells. Legalization, detailed placement, and post-placement algorithms can use these white spaces to further optimize the placement solution. In high-density regions, white spaces are limited resources. In the traditional placement flow (global placement, legalization, and detailed placement), the placement optimization is limited by the strict placement flow. The proposed cell spreading algorithms can be integrated into a mixed placement flow that is composed of interleaved legalization and detailed placement algorithms. In this mixed placement flow, the restriction to optimize detailed placement in a legalized netlist can be relaxed. Detailed placement algorithms can achieve further placement optimization with less restricted placement formulation. The focus of legalization algorithms can only be to fix cell overlap with minimized adverse effects on placement, instead of also fix density area violation. The proposed cell spreading algorithm is applied in legalization and detailed placement stages to optimize area density utilization. The proposed legalization algorithm has achieved improvement on average (30%) and maximum (350%) cell displacement compared to the state of the arts legalization algorithms. In detailed placement, the proposed algorithm has been evaluated in industrial and academic placement flows. In industrial placement flow, the proposed cell spreading algorithm has achieved improvement in cell displacement, power consumption, and timing. The proposed cell spreading algorithm can improve the quality of placement in mixed placement flow in both industrial and academic environments. The proposed algorithm provides a uniform cell distribution placement in constrained designs with minimized minimized adverse side effects on moved cells.

O posicionamento é um estágio desafiante no fluxo de projeto físico para integrar circuitos VLSI (sigla do inglês Very Large-Scale Integration (VLSI)). Em projetos modernos de circuitos VLSI, diversas restrições de projeto são impostas para visar a complexidade dos avançados nodos de fabricação CMOS (sigla do inglês). As restrições de projeto têm uma considerável influência em obter soluções otimizadas de circuitos. A qualidade do posicionamento tem uma significativa influência no desempenho do circuito. No posicionamento, obter os requisitos do circuito em tempo de propagação e rotabilidade é uma tarefa desafiante. Requerimentos de tempo de propagação e rotabilidade são especialmente difíceis de obter em circuitos que tem regiões com alta densidade de utilização de área. Além disso, a qualidade do posicionamento tem influência direta na qualidade do circuito e no esforço de otimização dos algoritmos de síntese da árvore de relógio (sigla do inglês CTS), roteamento e pós-posicionamento otimização. A primeira contribuição apresentada nessa tese é um algoritmo incremental de posicionamento para otimizar violações no tempo de propagação sujeito a rotabilidade. O algoritmo proposto é baseado em características das redes e dos caminhos de dados para computar posições otimizadas para as células. Continua) Posições otimizadas são aceitas somente se elas estão dentro de regiões livres de violações de roteamento. A segunda contribuição apresentada nessa tese é um algoritmo de espalhamento de células. O objetivo é mover células fora de regiões com alta densidade de área considerando efeitos adversos nas células movidas. O algoritmo proposto é baseado em técnicas de network flow e branch and cut para minimizar regiões com alta densidade de área. Fluxos de área são movidos de regiões com alta densidade de área para regiões com baixa densidade de área com caminhos com custo otimizado. Assim sendo, a concentração de células é reduzida e espaços são abertos em regiões com alta densidade de área com minimizado efeitos adversos nas células movidas. Algoritmos de legalização, posicionamento detalhado e pós-posicionamento podem utilizar esses espaços abertos para otimizar mais a solução de posicionamento. Em regiões com alta densidade de área, espaços são recursos limitados. No fluxo de posicionamento tradicional (posicionamento global, legalização e posicionamento detalhado), a otimização do posicionamento é limitada pelo fluxo tradicional. O algoritmo proposto de espalhamento de células pode ser integrado em um fluxo misto de posicionamento que é composto de algoritmos intercalados de legalização e posicionamento detalhado. Nesse fluxo de posicionamento misto, a restrição para otimizar posicionamento detalhado em uma netlist legalizada pode ser relaxada. Algoritmos de posicionamento detalhado podem obter melhor posicionamento com uma formulação de posicionamento menos restrita. O foco dos algoritmos de legalização pode ser somente remover sobreposição de células com efeitos adversos minimizados no posicionamento ao invés de também minimizar violações de densidade de utilização de área. O algoritmo proposto de espalhamento de células é aplicado nos estágios de legalização e posicionamento detalhado para otimizar densidade de utilização de área. O algoritmo proposto de legalização obteve melhoria no espalhamento médio (30%) e máximo (350%) de células comparado com algoritmos de legalização estado da arte. No posicionamento detalhado, o algoritmo proposto foi avaliado em fluxos de posicionamento industrial e acadêmico. No fluxo de posicionamento industrial, o algoritmo proposto melhorou espalhamento de células, potência dissipada e tempo de propagação. O algoritmo proposto de espalhamento de células pode melhorar a qualidade do posicionamento em fluxos de posicionamento mistos em ambiente industrial e acadêmico. O algoritmo proposto fornece posicionamento com distribuição uniforme de células em projetos limitados com efeitos adversos minimizados nas células movidas.