Mixed-cell-height circuits have become popular in advanced technologies for better power, area, routability, and performance tradeoffs. With technology and region constraints imposed by modern circuit designs, the mixed-cell-height legalization problem has become even more challenging. Additionally, an ideal legalization method should minimize both the average and maximum cell movements to preserve the quality of a given placement as much as possible. In this article, we present an effective and efficient mixed-cell-height legalization algorithm to consider technology and region constraints while minimizing the average and maximum cell movements. We first present a fence region handling technique to unify the fence regions and the default region. To obtain a desired cell assignment, we then propose a movement-aware cell reassignment method by iteratively reassigning cells in locally dense areas to their desired rows. After cell reassignment, a technology-aware legalization is presented to remove cell overlaps while satisfying the technology constraints. Finally, we propose a technology-aware refinement to further reduce the average and maximum cell movements without increasing the technology constraints violations. Compared with the champion of the 2017 CAD Contest at ICCAD and the state-of-the-art work, experimental results based on the 2017 CAD Contest at ICCAD benchmarks show that our algorithm achieves the best average and maximum cell movements and significantly fewer technology constraint violations, in a comparable runtime. The experimental results based on the modified 2015 ISPD Contest benchmarks also demonstrate the effectiveness of our algorithm in minimizing the average and maximum cell movements, compared with state-of-the-art mixed-cell-height legalizers.

With several divided stages, placement and routing are the most critical and challenging steps in VLSI physical design. To ensure that physical implementation problems can be manageable and converged in a reasonable runtime, placement/routing problems are usually further split into several sub-problems, which may cause conservative margin reservation and mis-correlation. Therefore, it is desirable to design an algorithm that can accurately and efficiently consider placement and routing simultaneously. In this paper, we propose a detailed placement and global routing co-optimization algorithm while considering complex routing constraints to avoid conservative margin reservation and mis-correlation in placement/routing stages. Firstly, we present a rapidly preprocessing technology based on R-tree to improve the initial routing results. After that, a BFS-based approximate optimal addressing algorithm in 3D is designed to find a proper destination for cell movement. We propose an optimal region selection algorithm based on the partial routing solution to jump out of the local optimal solution. Further, a fast partial net rip-up and rerouted algorithm is used in the process of cell movement. Finally, we adopt an efficient refinement technique to reduce the routing length further. Compared with the top 3 winners according to the 2020 ICCAD CAD contest benchmarks, the experimental results show that our algorithm achieves the best routing length reduction for all cases with a shorter runtime. On average, our algorithm can improve 0.7%, 1.5%, and 1.7% for the first, second, and third place, respectively. In addition, we can still obtain the best results after relaxing the maximum cell movement constraint, which further illustrates the effectiveness of our algorithm.

Along with device scaling, the drain-to-drain abutment (DDA) and fence region constraints arise as emerging challenges in modern circuit designs, incurring additional difficulties, especially for designs with mixed-cell-height standard cells which have prevailed in advanced technology. This article presents the first work to address the mixed-cell-height placement problem considering the DDA and fence region constraints from post-global placement throughout the detailed placement. Our algorithm consists of three major stages: 1) preprocessing; 2) legalization; and 3) detailed placement. At the preprocessing stage, we align cells to the desired rows that meet the region constraint, considering the total cell displacement and the distribution ratio of source nodes to drain nodes simultaneously. After deciding the cell ordering of every row, we first propose an interval concept to handle fixed macros and fence regions and then apply the robust modulus-based matrix splitting iteration method to remove all cell overlaps with minimized total displacement at the legalization stage. For detailed placement, unlike the existing works that can handle the DDA constraint only for single rows, we propose a satisfiability-based approach that considers the whole layout to fix the DDA violations more effectively. Besides, we further present an integer linear program (ILP)-based method to optimize the cell displacement without increasing the DDA violations. Compared with a shortest-path method, experimental results show that our proposed algorithm can significantly reduce cell violations, average cell displacement, and maximum cell displacement, in a comparable runtime.

With the increasing complexity of the field-programmable gate array (FPGA) architecture, heterogeneity and clock constraints have greatly challenged FPGA placement. In this paper, we present a high-performance placement algorithm for large-scale heterogeneous FPGAs with clock constraints. We first propose a connectivity-aware and type-balanced clustering method to construct the hierarchy and improve the scalability. In each hierarchy level, we develop a novel hybrid penalty and augmented Lagrangian method to formulate the heterogeneous and clock-aware placement as a sequence of unconstrained optimization subproblems and adopt the Adam method to solve each unconstrained optimization subproblem. Then, we present a matching-based IP blocks legalization to legalize the RAMs and DSPs, and a multi-stage packing technique is proposed to cluster FFs and LUTs into HCLBs. Finally, history-based legalization is developed to legalize CLBs in an FPGA. Based on the ISPD 2017 clock-aware FPGA placement contest benchmarks, experimental results show that our algorithm achieves the smallest routed wirelength for all the benchmarks among all published works in a reasonable runtime.

Macro placement is a crucial and complex task in chip design. In recent years, reinforcement learning (RL) has emerged as a promising approach for autonomously generating effective macro placement on a grid-based chip canvas. However, existing RL-based macro placers encounter challenges when handling macros of varying sizes and preplaced blocks, due to using coarse-grained grids leads to wastage of placement space, while employing fine-grained grids results in an exponentially growing solution space and significant computational overhead. This brief proposes a legalization-aided RL-based macro placement (LAMPlace) for mixed-size designs with preplaced blocks. LAMPlace leverages RL to generate a global macro placement that allows possible overlap, followed by a macro legalization algorithm to ensure the legality of macro placement. LAMPlace can effectively address macros of various sizes and preplaced blocks because the action mask generation algorithm in RL is well coupled with the macro legalization algorithm. Compared with the state-of-the-art works, experimental results on publicly mixed-size placement benchmarks show that LAMPlace is effective.

With the vertically stacked configuration and different technology processes imposed by stacked three-dimensional (3D) integration circuits (ICs), the placement problem has become more challenging. In this brief, we develop a high-performance 3D placement engine with physical-aware incremental partitioning for the stacked 3D ICs. We first propose a compact 2D global placement (GP) to find desired locations for all cells in a die, and then present a progressive density-driven partitioning to partition the netlist into two dies. After that, we propose an incremental half-perimeter wirelength (HPWL)-driven partitioning and a 3D GP to alternately optimize the partitioning and placement results. Finally, we present legalization and detailed placement methods to ensure the legality and further improve the solution. Compared with the top 3 teams of the ICCAD 2022 contest, experimental results on the contest benchmarks show that our algorithm achieves the best solution quality for every benchmark in a comparable runtime.