Electron beam lithography (EBL) is a very promising candidate for integrated circuit (IC) fabrication beyond the 10 nm technology node. To address its throughput issue, the Character Projection (CP) technique has been proposed, and its stencil planning can be optimized with aware of overlapping characters. However, the top level 2D stencil planning problem has been proved to be an NP-hard problem. As its most essential step, the 1D row ordering is believed hard as well, and no polynomial time optimal solution has been provided so far. In this paper, we propose a polynomial time optimal algorithm to solve the row ordering problem, which serves as the major subroutine for the entire stencil planning problem. Proof and experimental results are also provided to verify the correctness and efficiency of our algorithm.

Directed Self-Assembly (DSA) is a promising technique for contacts/vias patterning in 7 nm technology nodes. In DSA process, groups of contact holes/vias are generated by the self-assembly process guided by the `guiding templates'. The guiding templates are patterned by conventional optical lithography process such as 193 nm immersion lithography. As a result, the patterning fidelity and variation in the template shapes is very likely to affect the final contact holes/vias. While feasible in principle, rigorous DSA process simulation is unacceptably slow for full chip verification in practice. This paper proposes a machine learning based verification that can predict the pitch size of the contact holes and the hole centers. Given a set of training data that consists of simulated template and contact hole patterns, our method is able to learn a highly accurate predictive model for pitch size and hole location. To build a statistical model for prediction, we utilize computer vision techniques to extract various geometric and image features. We conduct extensive experiments to explore the effectiveness of the proposed features, and compare several machine learning algorithms to achieve an effective and efficient prediction. The experimental results show that compared to the minutes or even hours of simulation time in rigorous methods, our best prediction model achieves very promising results (RMSE = 0.135 pitch grid) with less than one second of training and predicting runtime overhead.

Directed Self-Assembly (DSA) is a promising technique for contacts/vias patterning, where groups of contacts/vias are patterned by guiding templates. As the templates are patterned by traditional lithography, their shapes may vary due to the process variations, which will ultimately affect the contacts/vias even for the same type of template. Due to the complexity of the DSA process, rigorous process simulation is unacceptably slow for full chip verification. This paper formulate several critical problems in DSA verification, and proposes a design automation methodology that consists of a data preparation and a model learning stage. We present a novel DSA model with Point Correspondence and Segment Distance features for robust learning. Following the methodology, we propose an effective machine learning (ML) based method for DSA hotspot detection. The results of our initial experiments have already demonstrated the high-efficiency of our ML-based approach with over 85% detection accuracy. Compared to the minutes or even hours of simulation time in rigorous method, the methodology in this paper validates the research potential along this direction.

FinFET transistors have great advantages over traditional planar MOSFET transistors in high performance and low power applications. Major foundries are adopting the Fin-FET technology for CMOS semiconductor device fabrication in the 16 nm technology node and beyond. Edge device degradation is among the major challenges for the FinFET process. To avoid such degradation, dummy gates are needed on device edges, and the dummy gates have to be tied to power rails in order not to introduce unconnected parasitic transistors. This requires that each dummy gate must abut at least one source node after standard cell placement. If the drain nodes at two adjacent cell boundaries abut each other, additional source nodes must be inserted in between for dummy gate power tying, which costs more placement area. Usually there is some flexibility during detailed placement to horizontally flip the cells or switch the positions of adjacent cells, which has little impact on the global placement objectives, such as timing conditions and net congestion. This paper proposes a detailed placement optimization strategy for the standard cell based designs. By flipping a subset of cells in a standard cell row and switching pairs of adjacent cells, the number of drain to drain abutments between adjacent cell boundaries can be optimally minimized, which saves additional source node insertion and reduces the length of the standard cell row. In addition, the proposed graph model can be easily modified to consider more complicated design rules. The experimental results show that the optimization of 100k cells is completed within 0.1 second, verifying the efficiency of the proposed algorithm.

Triple patterning lithography (TPL) has been recognized as one of the most promising techniques for 14/10nm technology node. There are various concerns for TPL decompositions. For standard cell based designs, assigning the same pattern for the same type of cells is a desired property for TPL decomposition. It is more robust for process variations and gives the chip similar physical and electrical characteristics as well as more reliable and predictable performance. Assigning the same type of pattern for the same type of cell is called a constrained pattern assignment (CPA) problem. In this paper, we integrated the flow of detailed placement and TPL decompositions with CPA coloring constraints. We focused on refining a layout to make it CPA-friendly during the detailed placement stage while minimizing the area and HPWL (half perimeter wire length) overhead. A weighted partial MAX SAT approach is proposed which guarantees to obtain a CPA-friendly detailed placement result while minimizing the area overhead. An efficient graph model is also proposed to compute the locations of the cells with optimal HPWL. Our formulation is very efficient and achieves a 79.4% area overhead reduction compared with the approach of fixing cell colors beforehand. Better HPWL are also achieved consistently over all benchmarks.

Due to the absence of defect-free blanks in extreme ultraviolet (EUV) lithography, defect mitigation is necessary before mass production. One effective defect mitigation approach is to cover defects by device features, such that the defects will no longer be printable. Normally die size is much smaller than the exposure field on the blank, such that one blank can accommodate multiple copies of a die, each of which can be placed independently within the exposure field. For thorough utilization of blank area, the number of valid dies that are not impacted by any defects should be maximized. To do so, all relocation positions to place a single valid die on a defective blank must be determined first [1]. To the best of our knowledge, no existing work can find all relocation positions throughout the whole blank in a reasonable amount of time. In this paper, we develop an efficient algorithm to solve this problem. The time complexity of our algorithm is linear in the number of features in the die. Experimental results with full die layouts generated from a standard cell library validate the efficiency of our algorithm. Comparing to the algorithm in [2] which runs more than one week without termination, our algorithm only takes several hours to find all relocation positions for a die with millions of features.

Self-aligned double patterning (SADP) lithography is a leading technology for 10nm node Metal layer fabrication. In order to achieve successful decomposition, SADP-compliant design becomes a necessity. Spacer-Is-Dielectric (SID) is the most popular flavor of SADP with higher flexibility in design. This paper makes a careful study on the challenges for SID-compliant detailed routing and proposes a graph model to capture the decomposition violations and SID intrinsic residue issues. Then a negotiated congestion based scheme is adopted to solve the overall routing problem. The proposed SID-compliant detailed routing algorithm simultaneously assigns colors to the routed wires, which provides valuable information guiding SID decomposition. In addition, if one pin has multiple candidate locations, the optimal one will be automatically determined during detailed routing. The decomposability of the conflict-free routing layers produced by our detailed router is verified by a commercial SADP decomposition tool.

At the 10 nm technology node, the contact layers of integrated circuits (IC) designs are too dense to be printed by single exposure using 193 nm immersion (193i) lithography. Among all the emerging patterning approaches, block copolymer directed self-assembly (DSA) is a promising candidate with high throughput and low cost for sub-20 nm features. Traditionally, the study of DSA has focused on achieving periodic regular patterns over large area. Realizing that long range order is not needed for patterning irregularly distributed contact holes, we use topographical guiding templates to alter the natural symmetry of block copolymer and achieve controlled irregular DSA patterns. However, DSA patterning must satisfy the overlay accuracy requirements while the guiding templates also need to be printable by conventional lithography. This presents a unique opportunity of DSA patterning and layout design co-optimization for improving the manufacturability of DSA. This paper discusses the DSA-aware contact layer optimization problem for 10 nm 1D standard cell library. For the first time we propose a cost function for each DSA template based on its overlay accuracy performance. Then given a standard cell library, we simultaneously optimize the layouts of every cell, such that the contact layer of any cell in the library can be fully patterned by a set of guiding templates, and the total cost of the templates is minimal. This optimization problem is first proved to be NP-hard and formulated as a Weighted Partial Maximum Satisfiability (MAXSAT) problem, which can be optimally solved with a public SAT solver. Then we propose a bounded approximation algorithm that solves the problem much more efficiently. The experimental results demonstrate that our approach is remarkably promising in practice and validate the proposed optimization problem.

Triple patterning lithography (TPL) has been recognized as one of the most promising candidates for 14/10nm technology node. Apart from obtaining legal TPL decompositions, various concerns have been raised by the designers, among them consistently assigning the same pattern for the same type of standard cells and balancing the usage of the three masks are two most critical ones. In this paper, a hybrid approach (SAT followed by a sliding-window approach) is proposed targeting at these two problems. To assign the same pattern for the same type of standard cell, we pre-color the boundary polygons of each type of cell by solving a small SAT problem. Following that we propose a sliding-window based approach to compute a locally balanced decomposition. Our algorithm guarantees to find a feasible solution if one exists. Experimental results verify that the problem can be solved very efficiently with the proposed algorithm. Superior locally balanced decompositions are achieved compared with the previous approach in.

Self-aligned double patterning is one of the most promising double patterning techniques for sub-20nm nodes. As in any multiple patterning techniques, layout decomposition is the most important problem. In SADP decomposition, overlay is among the most primary concerns. Most of the existing works target at minimizing the overall overlay, while others totally forbid the overlay. On the other hand, most of the works either rely on exponential time methods, or apply heuristic that cannot guarantee to find a solution. In this paper, we consider the SADP decomposition problem in row-based standard cell layout, where the overlay violations are minimized. Although SADP decomposition has been shown to be NP-hard in general, we showed that it can be solved in polynomial time when the layout is row-based standard cells. We propose a polynomial time optimal algorithm that finds a decomposition with minimum overlay violations. The efficiency of our method is further demonstrated by the experimental results.

Double patterning lithography (DPL) technologies have become a must for today's sub-32 nm technology nodes. Currently, there are two leading DPL technologies: self-aligned double patterning (SADP) and litho-etch-litho-etch (LELE). Among them, SADP has the significant advantage over LELE in its ability to avoid overlay, making it the likely DPL candidate for the next technology node of 14 nm. In any DPL technology, layout decomposition is the key problem. While the layout decomposition problem for LELE has been well studied in the literature, only a few attempts have been made to address the SADP layout decomposition problem. In this paper, we present a polynomial time exact (optimal) algorithm to determine if a given layout has SADP decompositions that do not have any overlay at specified critical edges. The previous approaches tried to minimize the total overlay of a given layout, which may be a problematic objective. Furthermore, all previous exact algorithms were computationally expensive exponential time algorithms based on SAT or ILP. Other previous algorithms for the problem were heuristics without having any guarantee that an overlay-free solution can be found even if one exists.

Since some of major IC industry participants are moving to the highly regular 1D gridded designs to enable scaling to sub-20nm nodes, how to manufacture the randomly distributed cuts with reasonable throughput and process variation becomes a big challenge. With the help of hybrid lithography, people can apply different types of processes for one single layer manufacturing such that the advantages from different technologies can be combined together to further benefit manufacturing. In this paper, targeting cut printing difficulties and hybrid lithography with electron beam (E-Beam) and 193 nm immersion (193i) processes, we propose a novel algorithm to optimally assign cuts to 193i or E-Beam processes with proper modifications on cut distribution, in order to maximize the overall throughput. To validate our method, we construct our algorithm based on the forbidden patterns obtained from the optical simulation; then we formulate the redistribution problem into a well defined ILP problem and finally call a reliable solver to solve the whole problem. Experimental results show that the throughput is dramatically improved by the cut redistribution. Besides that, for sparser layers, the EBL process can be totaly saved, which largely reduces the fabrication cost.

Blank defect mitigation is a critical step for extreme ultraviolet (EUV) lithography. Targeting the defective blank, a layout relocation method, to shift and rotate the whole layout pattern to a proper position, has been proved to be an effective way to reduce defect impact. Yet, there is still no published work about how to find the best pattern location to minimize the impact from the buried defects with reasonable defect model and considerable process variation control. In this paper, we successfully present an algorithm that can optimally solve this pattern relocation problem. Experimental results validate our method, and the relocation results with full scale layouts generated from Nangate Open Cell Library has shown great advantages with competitive runtimes compared to the existing commercial tool.

Blank defect mitigation is crucial for extreme ultraviolet (EUV) lithography. One of the existing options is to relocate patterns to avoid defect impact. However, when the defect number increases, only pattern shift in X-Y directions becomes far from enough, requiring the reticle holder rotate a small angle to provide a third exploring dimension. This non-trivial extension from 2D to 3D exploration requests efficient runtime as well as enough accuracy to handle different defect sizes and locations on the different features. In this paper, we present the first work with a detailed algorithm to find the optimal shift and rotation for layout patterns on blanks. Compared to the straightforward method, which is to check every pair of defect and feature at every possible relocation position, our proposed algorithm can significantly reduce the runtime complexity to scale linearly with the size of the full solution space. The experimental results validate our method and show a largely increased success rate of defect mitigation by shift and rotation.

Double patterning lithography (DPL) technologies have become a must for today's sub-32nm technology nodes. There are two leading DPL technologies: self-aligned double patterning (SADP) and litho-etch-litho-etch (LELE). Among these two DPL technologies, SADP has the significant advantage over LELE in its ability to avoid overlay, making it the likely DPL candidate for the next technology node of 14nm. In any DPL technology, layout decomposition is the key problem. While the layout decomposition problem for LELE has been well-studied in the literature, only few attempts have been made to address the SADP layout decomposition problem. In this paper, we present the first polynomial time exact (optimal) algorithm to determine if a given layout has an overlay-free SADP decomposition. All previous exact algorithms were computationally expensive exponential time algorithms based on SAT or ILP. Other previous algorithms for the problem were heuristics without having any guarantee that an overlay-free solution can be found even if one exists.

Double patterning lithography (DPL) is the enabling technology for printing in sub-32nm nodes. In the EDA literature, researchers have been focusing on double-exposure double-patterning (DEDP) DPL for printing arbitrary 2D features where the layout decomposition problem for double exposure is an interesting graph coloring problem. But due to overlay errors, it is very difficult for DEDP to print even 1D features. A more promising DPL technology is self-aligned double patterning (SADP) for 1D design. SADP first prints dense lines and then trims away the portions not on the design by a cut mask. The complexity of cut mask is very high, adding to the skyrocketing manufacturing cost. In this paper we present a mask cost reduction method with circuit performance consideration for SADP. This is the first paper to focus on the mask cost reduction issue for SADP from a design perspective. We simplify the polygons on the cut mask, by formulating the problem as a constrained shortest path problem. Experimental results show that with a set of layouts in 28nm technology, we can largely reduce the complexity of cut polygons, with little impact on performance.

Self-aligned double patterning (SADP) lithography is a promising technology which can reduce the overlay and print 2D features for sub-32nm process. Yet, how to decompose a layout to minimize the overlay and perform hot spot detection is still an open problem. In this paper, we present an algorithm that can optimally solve the SADP decomposition problem. For a decomposable layout, our algorithm guarantees to find a decomposition solution that minimizes overlay. For a non-decomposable layout our algorithm guarantees to find all hot spots. Experimental results validate our method, and decomposition results for Nangate Open Cell Library and larger testcases are also provided with competitive runtimes.