Improving the VLSI circuit design flow through cell movements during global routing

Abstract

O projeto de circuitos integrados Very Large-Scale Integration (VLSI) atualmente contém tarefas extremamente complexas e por isso, deve seguir um fluxo estritamente utilizando ferramentas computacionais sofisticadas designadas Electronic Design Automation (EDA). Devido à complexidade dos circuitos contemporâneos, a descrição física tornou-se um passo crucial para alcançar o fechamento do projeto. Neste contexto, os processos de posicionamento e roteamento são partes fundamentais da propriedade física, uma vez que impactam diretamente o desempenho, a área, o consumo de energia e a confiabilidade do circuito. Para lidar com tal complexidade dos circuitos VLSI modernos, as etapas de posicionamento e roteamento são normalmente abordadas separadamente, aplicando-se uma abordagem de \"divisão e conquista\". Infelizmente, devido ao aumento contínuo da complexidade das regras de projeto, a convergência de soluções pode sofrer desalinhamento, e os efeitos de um posicionamento insatisfatório serão notados tão somente durante o roteamento, quando o posicionamento for considerado fixo. Esta tese apresenta uma técnica chamada ILPGRC, que significa \"ILP-Based Global Routing Optimization With Cell Movements\". O núcleo da técnica ILPGRC é composto por um modelo de Programação Linear Inteira (ILP) que simultaneamente move células e re-roteia as interconexões. A técnica ILPGRC permite a realocação de células que podem levar a problemas de roteamento, sem comprometer a qualidade em relação ao número de VIAs (Vertical Interconnection Access), comprimento das interconexões e visíveis de regras de projeto (Design Rule Violations - DRVs). Esta tese também propõe uma estratégia de particionamento chamada Checkered Paneling, que reduz o tamanho de entrada do modelo ILP, tornando esta abordagem escalável. A estratégia de Checkered Paneling também permite a execução de vários modelos ILP em paralelo, fornecendo assistência para grandes circuitos. Além disso, esta tese apresenta uma abordagem baseada em cluster de Gcells para legalizar a solução com o mínimo de perturbação. O método proposto é testado nos benchmarks da competição ACM/IEEE International Symposium on Physical Design (ISPD) 2018 e 2019 dentro de um fluxo de síntese física composto por ferramentas acadêmicas de posicionamento e roteamento do estado da arte. Os resultados após o roteamento detalhado mostram que a técnica ILPGRC pode reduzir, em média, o número de VIAs em 4,69%, com menos de 1% de impacto no comprimento das interconexões. Além disso, o ILPGRC reduz o número de DRVs na maioria dos casos, sem deixar interconexões incompletas. Comparando ILPGRC com o estado de trabalho da arte CRP 2.0, ILPGRC reduz o número de VIAs em 5,61% em média, enquanto o CRP 2.0 atinge apenas 3,59% de redução, assumindo a mesma referência, com um impacto semelhante no comprimento das interconexões.

Abstract: The design of current Very Large-Scale Integrated (VLSI) circuits is an extremely complex task and, therefore, must follow a strict flow using sophisticated computational tools referred to as Electronic Design Automation (EDA). Due to the complexity of contemporary circuits, physical synthesis has become a crucial step for achieving design closure. In this context, the placement and routing processes are key parts of the physical synthesis since they directly impact the circuit performance, area, power consumption, and reliability. To handle the high complexity of modern VLSI circuits, placement and routing steps are typically tackled separately by applying a divide-and-conquer approach. Unfortunately, due to the continuous increase of design rules complexity, the convergence of solutions can suffer from misalignment, and the effects of an unsatisfactory placement will be noticed only during routing when the placement would be considered fixed. This thesis presents a technique called ILPGRC, which stands for ?ILP-Based Global Routing Optimization With Cell Movements\". The core of ILPGRC is composed of an Integer Linear Programming (ILP) model that simultaneously moves cells and reroutes the nets. ILPGRC enables the relocation of cells that can lead to routing issues without compromising the quality concerning the number of VIAs, wirelength, and Design Rule Violations (DRVs). This thesis also proposes a partitioning strategy named Checkered paneling, which reduces the input size of the ILP model, making this approach scalable. The Checkered paneling strategy enables the execution of multiple ILP models in parallel, providing a speedup for large circuits. Additionally, this thesis presents a GCell cluster-based approach to legalize the solution with minimum disturbance and displacement. The proposed method is tested on the ACM/IEEE International Symposium on Physical Design (ISPD) 2018 and 2019 contest benchmarks within a physical synthesis flow composed of state-of-the-art place and route academic tools. The results after the detailed routing show that ILPGRC can reduce, on average, the number of VIAs by 4.69% with less than 1% impact on wirelength. Furthermore, ILPGRC reduces the number of DRVs in most cases with no open nets left. Comparing ILPGRC with the so-far state-of-the-art work CRP 2.0, ILPGRC reduces, on average, the number of VIAs by 5.61% while CRP 2.0 only achieves 3.59% assuming the same baseline, with a similar impact in the wirelength. This comparison indicates that ILPGRC is the best approach to optimize the detailed routing solution through cell movements during global routing, working as an additional step between global routing and detailed routing in the physical design flow.