Search

Fogging and proximity effects (FPEs) are two major factors that cause inaccurate exposure and layout pattern distortions in e-beam lithography. In this article, we propose an analytical placement algorithm that considers both FPEs. We formulate the global placement problem as a separable minimization problem with linear constraints, where different objectives can be tackled one by one in an alternating fashion. Then, we propose a novel proximal group alternating direction method of multipliers (ADMM) to solve the separable minimization problem with two subproblems, where the first subproblem (associated with wirelength and density) is solved by the steepest descent method without line search, and the second one (associated with the FPEs) is handled by an analytical scheme. We prove the property of global convergence of the proximal group ADMM method. Finally, the FPEs-aware legalization and detailed placement are employed to legalize and improve the placement result. The experimental results show that our algorithm is effective and efficient for the addressed problem. Our algorithm achieved 5.7% smaller fogging variation, 6.8% lower proximity variation, and 5.4% lower runtime with a minor wirelength overhead compared with the state-of-the-art work. [ABSTRACT FROM AUTHOR]

Mixed-cell-height standard cells are prevailingly used in advanced technologies to achieve better design tradeoffs among timing, power, and routability. As feature size decreases, the placement of cells with multiple threshold voltages may violate the complex minimum-implant-area (MIA) layer rule arising from the limitations of patterning technologies. Existing works consider the mixed-cell-height placement problem only during legalization or handle the MIA constraints during detailed placement. In this article, we address the mixed-cell-height placement problem with MIA constraints in two major stages: 1) post-global placement (Post-GP) and 2) MIA-aware legalization. In the Post-GP stage, we first present a continuous and differentiable cost function to address the Vdd/Vss alignment constraints and add weighted pseudonets to MIA-violation cells dynamically. Then, we propose a proximal optimization method based on the given global placement result to simultaneously consider Vdd/Vss alignment constraints, MIA constraints, cell distribution, cell displacement, and total wirelength. In the MIA-aware legalization stage, we develop a graph-based method to cluster cells of specific threshold voltages and apply a strip-packing-based binary linear programming to reshape cells. Then, we propose a matching-based technique to resolve intrarow MIA violations and reduce filler insertion. Furthermore, we formulate inter-row MIA-aware legalization as a quadratic programming problem, which is efficiently solved by a modulus-based matrix splitting iteration method. Finally, MIA-aware cell allocation and refinement are performed to further improve the result. Experimental results show that without any extra area overhead, our algorithm still can achieve 5.4% shorter final total wirelength than the state-of-the-art work. [ABSTRACT FROM AUTHOR]

Metal fill insertion has become an essential step in reducing dielectric thickness variation and improving pattern uniformity, which is important in mitigating process variations, thereby achieving better manufacturing yield. However, metal fills could induce coupling capacitance, which is not often considered in existing works that typically focus more on pattern density uniformity, incurring significant problems in timing closure. However, it is a great challenge to consider three types of capacitances (i.e., area, fringe, and lateral capacitances) with design rules and density constraints at the fill insertion stage simultaneously. This article presents an efficient timing-aware fill insertion algorithm for minimizing the total capacitance and fill amount, considering the density constraints. First, we present an initial metal fill insertion and design-rule-aware legalization to obtain an initial fill insertion solution quickly. Second, from critical conductors to powers/grounds in a circuit, we divide conductors into different equivalent paths and then construct a capacitance graph to reduce the capacitance of each equivalent path globally. Third, we propose a density-aware coupling capacitance optimization method and a fast Monte Carlo-based fill selection to further reduce the coupling capacitance between any pair of conductors. Finally, we present a density-aware fill deletion method to reduce the fill amount. We evaluate the performance of our algorithm on the benchmarks of the 2018 CAD Contest at ICCAD and its official contest evaluator. Compared with the first-place team of the contest and the state-of-the-artwork, experimental results show that our algorithm achieves the lowest total capacitance and the least fill amount in a comparable runtime. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

The common objective of very large-scale integration (VLSI) placement problem is to minimize the total wirelength, which is calculated by the total half-perimeter wirelength (HPWL). Since the HPWL is not differentiable, various differentiable wirelength approximation functions have been proposed in analytical placement methods. In this paper, we reformulate the HPWL as an l1 -norm model of the wirelength function, which is exact but nonsmooth. Based on the l1 -norm wirelength model and exact calculation of overlapping areas between cells and bins, a nonsmooth optimization model is proposed for the VLSI global placement problem, and a subgradient method is proposed for solving the nonsmooth optimization problem. Moreover, local convergence of the subgradient method is proved under some suitable conditions. In addition, two enhanced techniques, i.e., an adaptive parameter to control the step size and a cautious strategy for increasing the penalty parameter, are also used in the nonsmooth optimization method. In order to make the placement method scalable, a multilevel framework is adopted. In the clustering stage, the best choice clustering algorithm is modified according to the l1 -norm wirelength model to cluster the cells, and the nonsmooth optimization method is recursively used in the declustering stage. Comparisons of experimental results on the International Symposium on Physical Design (ISPD) 2005 and 2006 benchmarks show that the global placement method is promising. [ABSTRACT FROM PUBLISHER]