14 October 2021 in IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
As interconnects dominate circuit performance in modern field programmable gate arrays (FPGAs), placement becomes a crucial stage for timing closure. Traditional FPGA placers seldom consider the timing constraints and, thus, may lead to illegal routing solutions. In this article, we present an incremental timing-driven placement flow for advanced FPGAs. First, a timing-based global placement strategy is designed to guide heterogeneous blocks to desired locations with satisfied timing constraints. Then, a timing-aware packing algorithm is developed to mitigate the design complexity while improving the timing results. Finally, we propose a critical path-based optimization method to generate optimized layout without timing violations. We evaluate our algorithm based on industrial circuits using an advanced FPGA device. The experimental results show that our placer achieves a 5.1% improvement in worst slack and produce placements that require 16.7% less time to route when compared with the leading commercial tool Xilinx Vivado.
28 September 2022 in IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
Placement and routing are two critical problems in very large-scale integration physical design. However, there may be out-of-sync between the two problems considering congestion and wirelength. Therefore, it is desirable to design an efficient and highly coupled placement and routing engine to narrow the gap and minimize the mismatch between placement and routing. This article proposes an incremental 3-D global routing engine considering cell movement and complex routing constraints to relocate cells and reroute nets. We first apply a queue-based congestion-aware 3-D maze routing with routing height restriction to improve the initial routing solution. Efficient multinet-based location estimation is then presented to find the best location for each cell in multiple cell movement rounds. In each step of cell movement, we reroute nets for all candidate cell locations in parallel using a guided stack-based 3-D routing algorithm while considering the routing constraints. Finally, we adopt an edge-adjusting technique to improve the routed wirelength further. Compared with the champion of the 2020 CAD Contest at ICCAD (Hu et al., 2020) and the state-of-the-art works, experiment results based on the contest benchmarks show that our proposed algorithm achieves the best routing wirelength and competitive runtime without maximum cell movement constraint.
19 March 2026 in ACM Transactions on Design Automation of Electronic Systems
Compliance with design rule constraints constitutes a fundamental prerequisite for successful fabrication in advanced integrated circuit design. As foundries progressively introduce process-specific customization for better performance, new design rule challenges emerge across the device layers, such as implant layer constraints in the designs with multiple threshold voltages, and the trim poly layer constraints in the self-aligned double patterning (SADP). Conventional methodologies typically address such topological constraints in the legalization stage. In addition, filler insertion during chip finishing serves to improve manufacturability, such as a more uniform chip surface and a more robust power integrity. However, improper filler insertion might undermine the previous legalized layout. This work presents a co-optimization framework in the legalization and filler insertion stage, adaptable to multi-layer constraint scenarios. We model the filler insertion problem as a multi-branch tree and develop a dynamic programming-based pre-pruning algorithm, which is also able to detect violations in the legalization stage. To reduce runtime, two violation detectors are introduced for legalization, including a look-up table (LUT) inference method and a greedy scanning algorithm. These components are systematically integrated into a co-optimization framework, with configurable parameterization to ensure scalability across diverse constraints. Experimental results show that our algorithm can significantly reduce the number of violations compared with state-of-the-art work and the commercial tool.