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.

The fast-growing capacity and complexity are challenging for FPGA global placement. Besides, while many recent studies have focused on the eDensity-based placement as its great efficiency and quality, they suffer from redundant frequency translation. This paper presents a CNN-inspired analytical placement algorithm to effectively handle the redundant frequency translation problem for large-scale FPGAs. Specifically, we compute the density penalty by a fully-connected propagation and gradient to a discrete differential convolution backward. With the FPGA heterogeneity, vectorization plays a vital role in self-adjusting the density penalty factor and the learning rate. In addition, a pseudo net model is used to further optimize the site constraints by establishing connections between blocks and their nearest available regions. Finally, we formulate a refined objective function and a degree-specific gradient preconditioning to achieve a robust, high-quality solution. Experimental results show that our algorithm achieves an 8% reduction on HPWL and 15% less global placement runtime on average over leading commercial tools.

Placement and routing are two key problems in VLSI physical design. However, there may be out of sync between the two problems with congestion and routing resources. Therefore, it is desirable to design an efficient and highly coupled placement and routing engine. This paper proposes an incremental 3D global routing engine considering cell movement and complex routing constraints to relocate cells and reroute nets. We develop an efficient movement evaluation method to find desired locations and estimated routing resources for each cell. Then, we adopt an iterative approach to move cells to reduce routing resources. To reduce the time consumption of rerouting, we propose two technologies (searching space reduction and data structure optimization) to speed up the rerouting process. Compared with the participating teams at the 2020 CAD Contest at ICCAD based on the contest benchmarks, experiment results show that our proposed algorithm achieves the best runtime and routing resources while satisfying all the routing constraints.