Recent 3D IC designs need to realize high connectivity demand in one direction by utilizing limited routing resources. This paper proposes a fast greedy heuristic, practical criticality-based ceiling and packing (PC-CAP), for a gap channel to complete the allocation of trunks with a small number of gaps and to achieve small vertical wire congestion as much as possible while meeting the constraints on allocation. PC-CAP repeatedly assigns a trunk according to the priority defined in terms of criticality against an estimated vertical congestion, and obtains near optimal allocation in a short time.

Subresolution assist feature (SRAF) generation is a very important resolution enhancement technique to improve yield in modern semiconductor manufacturing process. Model-based and rule-based approaches are widely adopted in the semiconductor industry. The model-based SRAF generation can achieve a high accuracy but it is known to be time-consuming and it is hard to obtain consistent SRAFs on the same layout pattern configurations. The rule-based SRAF generation is highly technology dependent and it is becoming extremely difficult to render high-quality results in advanced technology nodes. This paper proposes supervised data learning techniques for fast yet consistent SRAF generation with high-quality results. We first propose the constrained concentric circle with area sampling scheme for feature extraction. Illumination source symmetry-based feature compaction technique is further invented to reduce the training data set size and achieve consistent SRAF predictions. Using accurate model-based SRAFs as training data, classification models based on logistic regression (LGR) and support vector machine are calibrated for SRAF predictions. Moreover, the probability maximum prediction is proposed to generate manufacturing-friendly SRAFs with a greedy simplification scheme. We compare support vector machine and LGR models by embedding into an entire mask optimization flow, where the support vector machine model obtains better lithographic performance. Experimental results demonstrate that, compared with the commercial Calibre tool, supervised data learning techniques for SRAF generation obtain significant speed up (>3X for a 100 um2layout clip) and comparable lithographic performance in terms of edge placement error and process variation band.

In advanced semiconductor-process technology, the ability to detect and repair lithography hotspots, which can affect printability, is essential. In this paper, we propose a two-stage cascade classifier for accurate hotspot detection. Our classifier uses a novel layout feature based on the propagation of light passing through a photomask. We performed experiments to evaluate our cascade classifier by applying it to the ICCAD-2012 CAD contest problem. The hotspot detection performance was evaluated according to two indices: (I1) the number of correctly detected hotspots over the number of actual hotspots and (I2) the number of correctly detected hotspots over the number of false hotspots. The results showed that the proposed method gained a 1.15% improvement in I1 and 24.4 times improvement in I2 on average compared to existing state-of-the-art methods, even the one with the best I1.

With the continuous shrinkage of advanced technology nodes into the sub-16-nm regime, optical proximity correction (OPC) is still the main stream to preserve acceptable wafer image quality under lithographic process variations in the foreseeable future. However, OPC is getting more aggressive to keep pace with advanced technology nodes. This results in complex mask solutions and long computation time. In this paper, we propose a novel-intensity-based OPC algorithm to find mask solutions with minimal edge placement error and process variability band area within a short computation time. This is achieved through exploiting a fast novel intensity estimation model with acceptable estimation accuracy to guide the OPC response including two-fragment shifting, corner hammering, and subresolution assist feature insertion for better convergence. Moreover, our algorithm is extended to satisfy the mask notch rule and reduce shot count for a lower mask manufacturing cost. The experimental results show that our algorithm outperforms recently published algorithms on the public benchmarks.

Sub-Resolution Assist Feature (SRAF) generation is a very important resolution enhancement technique to improve yield in modern semiconductor manufacturing process. Model- based SRAF generation has been widely used to achieve high accuracy but it is known to be time consuming and it is hard to obtain consistent SRAFs on the same layout pattern configurations. This paper proposes the first ma- chine learning based framework for fast yet consistent SRAF generation with high quality of results. Our technical con- tributions include robust feature extraction, novel feature compaction, model training for SRAF classification and pre- diction, and the final SRAF generation with consideration of practical mask manufacturing constraints. Experimental re- sults demonstrate that, compared with commercial Calibre tool, our machine learning based SRAF generation obtains 10X speed up and comparable performance in terms of edge placement error (EPE) and process variation (PV) band.

One of the most promising techniques in the 14 nm logic node and beyond is triple patterning lithography (TPL). Recently, LELECUT type TPL technology, where the third mask is used to cut the patterns, is discussed to alleviate native conflict and overlay problems in LELELE type TPL. In this paper, we formulate LELECUT mask assignment problem which maximizes the compliance to the lithography and apply a positive semidefinite relaxation. In our proposed method, the positive semidefinite relaxation is defined by extracting cut candidates from the layout, and a mask assignment is obtained from an optimum solution of the relaxation by randomized rounding technique.

In nano-scale systems, design for manufacturability is essentially required. For sub 20 nm technology node, Self-Aligned Double Patterning (SADP) is an important manufacturing technique, and complex two-dimensional patterns are requested to be fabricated by SADP. However all two-dimensional patterns cannot be fabricated by SADP. In this paper, two-dimensional patterns that satisfy connection requirements as well as manufacturability by SADP are effectively derived by our proposed approach in which partially pre-colored two-color base grid is used.

Although self-aligned double and quadruple patterning (SADP, SAQP) have promising processes for sub-20 nm node advanced technologies and beyond, not all layouts are compatible with them. In advanced technologies, feasible wafer image should be generated effectively by utilizing SADP and SAQP where a wafer image is determined by a selected mandrel pattern. However, predicting a mandrel pattern is not easy since it is different from the wafer image (or target pattern). In this paper, we propose new routing methods for spacer-is-dielectric (SID)-type SADP, SID-type SAQP, and spacer-is-metal (SIM)-type SADP to generate a feasible layout satisfying the connection requirements. Routing algorithms comprising simple connecting and cutting rules are performed on a new grid structure where two (SID-type SADP) or three colors (SID-type SAQP and SIM-type SADP) are assigned alternately to grid-nodes. Then a mandrel pattern is selected without complex coloring or decomposition methods. Also, we try to reduce hotspots (potentially defective regions) by the proposed dummy pattern flipping for SID-type SADP. In experiments, feasible layouts meeting the connection requirements are generated and the effectiveness of the proposed framework is confirmed.

With the continuous shrinking of minimum feature sizes beyond current 193nm wavelength for optical micro lithography, the electronic industry relies on Resolution Enhancement Techniques (RETs) to improve pattern transfer fidelity. However, the lithographic process is susceptible to dose and focus variations that will eventually cause lithographic yield degradation. In this paper, a new algorithm is proposed to minimize the Edge Placement Error (EPE) and the process variability of the printed image. The algorithm is also adapted to reduce the computational time using a novel approach through minimizing the number of convolutions during lithography simulation time. Experimental results show that the proposed algorithm results in less average cost than the top three teams of ICCAD 2013 contest on the public benchmarks.

Although Self-Aligned Double and Quadruple Patterning (SADP, SAQP) have become the most promising processes for sub-20 nm and sub-14 nm node advanced technologies, not all wafer images are realized by them. In advanced technologies, feasible wafer images should be generated effectively by utilizing SADP and SAQP where a wafer image is uniquely determined by a selected mandrel pattern. However, predicting the wafer image of a mandrel pattern is not easy. In this paper, we propose a routing method of generating a feasible wafer image satisfying the connection requirements. Routing algorithms comprising simple connecting and cutting rules are performed on a new grid structure where two (SADP) or three colors (SAQP) are assigned alternately to grid-nodes. Then a mandrel pattern is selected without complex coloring or decomposition methods. Also, hotspot reduction by dummy pattern flipping is proposed. In experiments, feasible wafer images meeting the connection requirements are generated and the effectiveness of the proposed framework is confirmed.

In recent high-performance analog integrated circuit design, it is often required to place some cells symmetrically to a horizontal or vertical axis. Balasa et al. proposed a method of obtaining the closest placement that satisfies the given symmetry constraints and the topology constraints imposed by a sequence-pair (seq-pair). However, this method has the following defects: 1) Balasa's necessary condition for existence of the cell placement that satisfies the given constraints is incorrect; 2) some cells overlap; 3) the closest placement of satisfying both the symmetry and topology constraints is not always obtained; and 4) there is no explanation of placing cells symmetrically to plural axes. In this paper, we clarify the necessary and sufficient conditions for the existence of the cell placement that satisfies the given symmetry constraints and the topology constraints imposed by a seq-pair, and we propose an efficient method of obtaining, by linear programming, the closest cell placement that satisfies the given constraints. Here, a simple constraint graph is obtained from a seq-pair in order to derive a set of linear constraint expressions. Then, to shorten the running time of linear programming, the number of linear expressions is reduced by substituting the expressions for dependent variables, and the solution is obtained. The effectiveness of the proposed method was shown by computational experiments

In our dynamically reconfigurable system model, computation resources are arranged in 2D-plane and each partial task is assigned to computation resources of rectangle-shape for a certain time period. The problem can be regarded as a rectangular box packing problem in 3D-space of 2D-plane and time axis. However, since partial tasks have order constraints, a packing should satisfy the given order constraints. We call this problem 3D-scheduling problem. Although there have been proposed various types of rectangular box packing representation, it is not examined until now which representation is fit to 3D-scheduling problem. In this paper, we investigate features of each 3D-packing representation, and show which representation is fit to 3D-scheduling problem theoretically and experimentally

Recently, it is often required in high performance analog IC design that some cells are placed symmetrically to horizontal or vertical axis. Balasa et al. proposed a method of obtaining the closest placement satisfying the given symmetry constraints and the topology constraints imposed by a sequence-pair, but this method has the following defects: (1) Some cells overlap each other. (2) The closest cell placement satisfying both the symmetry and topology constraints may not be obtained. (3) How to place cells symmetrically is mentioned only for one axis and there is no explanation for plural axes. In this paper, we propose an efficient method to obtain the closest cell placement satisfying the given symmetry constraints and the topology constraints imposed by a sequence-pair using linear programming. The proposed method obtains a simple constraint graph from a sequence-pair and derives a set of linear constraint expressions from the graph. The number of linear expressions decreases by substituting the expressions for dependent variables. Then the solutions are obtained by linear programming. The effectiveness of the proposed method was shown by computational experiments.

In this paper, we propose selected (SSP), a sequence-pair (seq-pair) with the limited number of subsequences called adjacent crosses. Its features are: (1) The smallest packing based on a given SSP can be obtained in O(n) time, where n is the number of rectangles. (2) An arbitrary packing can be represented by SSP. (3) The total representation number of SSP of size n is not more than that of rectangular dissection of the same size with n-/spl lfloor//spl radic/(4n-1)/spl rfloor/ empty rooms (the necessary number of empty rooms to represent an arbitrary packing). To realize these features of SSP, we propose an algorithm to enumerate all adjacent crosses on a seq-pair in linear time of n + k (k is the number of adjacent crosses). Also we apply a conventional method to convert a seq-pair without adjacent crosses to an equivalent Q-sequence, representation of rectangular dissection, in O(n + k) time. A move operation to obtain an adjacent solution efficiently is proposed to perturb SSP for Simulated Annealing (SA). From experimental results, we confirmed the proposed method was carried out in linear time and was more efficient than the conventional method when SSP size got bigger.