Multiple patterning lithography has been widely adopted for today's circuit manufacturing. However, increasing the number of masks will make the manufacturing process more expensive. More importantly, towards 7 nm technology node, the accumulated overlay in multiple patterning will cause unacceptable edge placement error (EPE). Recently, directed self-assembly (DSA) has been shown to be an effective lithography technology that can pattern contact/via/cuts with high throughput and low cost. DSA is currently aiming at 7 nm technology, where the guiding template generation needs either double patterning EUV or multiple patterning DUV process. By incorporating DSA into the multiple patterning process, it is possible to reduce the number of masks and achieve a cost effective solution. In this paper, we study the decomposition problem for contact layer in row-based standard cell layout with DSA-MP complementary lithography. We explore several heuristic-based approaches, and propose an algorithm that decomposes a standard cell row optimally in polynomial-time. Our experiments show that our algorithm guarantees to find a minimum cost solution if one exists, while the heuristic cannot or only finds a sub-optimal solution. Our results show that the DSA-MP complementary approach is very promising for the future advanced nodes.

Triple patterning lithography (TPL) has been recognized as one of the most promising techniques for 14/10nm technology node. In this paper, we applied triple patterning lithography on standard cell based designs, and proposed a novel algorithm to solve the problem. The algorithm guarantees to find a legal TPL decomposition with optimal number of stitches if one exists. A graph model is proposed to reduce the number of vertices in the solution graph, and a fast approach is developed to achieve simultaneous runtime and memory improvement. An efficient approach to limit the number of stitches is also proposed, which greatly reduces the total number of stitch candidates and enables an incremental implementation of the algorithm. Experimental results shows that the proposed algorithm is very efficient, which achieves 39.1% runtime improvement and 18.4% memory reduction compared with the state-of-the-art TPL algorithm on the same problem.

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.

Recently, block copolymer directed self-assembly (DSA) has demonstrated great advantages in patterning contacts/vias for the 7 nm technology node and beyond. The high throughput and low process cost of DSA makes it the most promising candidate in patterning tight pitched dense patterns for the next generation lithography. Since DSA is very sensitive to the shapes and distributions of the guiding templates, it is necessary to develop new EDA algorithms and tools to address the patterning rules and constraints of the process. This paper presents a set of DSA-aware optimization techniques targeting the most urgent problems for DSA technology, including layout optimization and template pattern verification.

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.

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.

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.

As minimum feature size keeps shrinking, and the next generation lithography (e.g, EUV) further delays, double patterning lithography (DPL) has been widely recognized as a feasible lithography solution in 20nm technology node. However, as technology continues to scale to 14/10nm, DPL begins to show its limitations and usually generates too many undesirable stitches. Triple patterning lithography (TPL) is a natural extension of DPL to conquer the difficulties and achieve a stitch-free layout decomposition. In this paper, we study the standard cell based row-structure layout decomposition problem in TPL. Although the general TPL layout decomposition problem is NP-hard, in this paper we will show that for standard cell based TPL layout decomposition problem, it is polynomial time solvable. We propose a polynomial time algorithm to solve the problem optimally and our approach has the capability to find all stitch-free decompositions. Color balancing is also considered to ensure a balanced triple patterning decomposition. To speed up the algorithm, we further propose a hierarchical algorithm for standard cell based layout, which can reduce the run time by 34.5% on average without sacrificing the optimality. We also extend our algorithm to allow stitches for complex circuit designs, and our algorithm guarantees to find optimal solutions with minimum number of stitches.

Due to the rapid advances of integrated circuit technology, the size of power distribution network (power grid) is becoming larger and larger. There are usually multi-million nodes on a power grid. Analyzing these huge power grids has become very expensive in terms of both time and memory. This paper presents an efficient parallel implementation of the Additive Schwarz Method (ASM) for IR-drop analysis of large-scale power grid. Based on distributed memory system, a new data storage method is proposed to overcome memory bottleneck of traditional methods. Techniques including overlapping in multiple layer and irregular power grid, via detection and grouping are utilized to accelerate the simulation. Moreover, a new communication strategy exhibiting minimum communication overhead is proposed. The proposed method is very accurate in the final solution, with the maximum error less than 0.1mv. Experimental results on industrial medium size benchmarks show that the proposed method achieves more than 110X speedup over a state-of-the-art direct LU solver. The proposed approach can easily solve very large-scale benchmarks, while LU solver fails to obtain the solution because of system memory limitation. It is the first time reported in literature that IR-drop analysis of power grid with over 190M nodes is successfully solved within 5 minutes.

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.

Computer-aided design problems of digital microfluidic biochips are receiving much attention, and most of the previous works focus on direct-addressing biochips. In this paper, we solve the placement and droplet routing problem in cross-referencing biochips. In these biochips, the electrodes are addressed in a row-column manner, which may cause electrode interference that prevents simultaneous movements of multiple droplets. We propose a routing algorithm that solves the droplet routing problem directly. A two-coloring graph-theoretic method is used in our router to detect and prevent the electrode interference. In addition, we propose an integer linear programming based method to solve the placement problem. Our method considers the characteristics of cross-referencing biochips and is aware of droplet routing. Real-life benchmarks are used to evaluate the proposed methods. Compared with previous works, our router improves on average 4% in routing time and 58% in runtime. It can route all the benchmarks within the time limits, while the latest work fails in some cases. Moreover, experimental results show that by running our router on the placement result generated by our method and those generated by the latest work, an average improvement of 11%, 29%, 54%, and 46% in the maximum routing time, average routing time, stalling steps, and cell usage can be achieved.

Digital Microfluidic Biochip (DMFB) has drawn lots of attention today. It offers a promising platform for various kinds of biochemical experiments. DMFB that uses cross-referencing technology to drive droplets movements scales down the control pin number on chip, which not only brings down manufacturing cost but also allows large-scale chip design. However, the cross-referencing scheme that imposes different voltage on rows and columns to activate the cells, might cause severe electrode interference, and hence greatly decreases the degree of parallelism of droplet routing. Most of the previous papers get a direct-addressing result first, and then convert to cross-referencing compatible result. This paper proposes a new method that solves the droplet routing problem on cross-referencing biochip directly. Experimental results on public benchmarks demonstrate the effectiveness and efficiency of our method in comparison with the latest work on this problem.

Clock network construction is one key problem in high performance VLSI design. Reducing the clock skew variation is one of the most important objectives during clock network synthesis. Local clock skew (LCS) is the clock skew between any two sinks with distance less than or equal to a given threshold. It is defined in the ISPD 2010 High Performance Clock Network Synthesis Contest, and it is a novel criterion that captures process variation effects on a clock network. In this paper, we propose a hybrid method that creates a mesh upon a tree topology. Total wire and buffer capacitance is minimized under the LCS and slew constraints. In our method, a clock mesh will be built first according to the positions and capacitance of the sinks. A top-level tree is then built to drive the mesh. A blockage-aware routing method is used during the tree construction. Experimental results show our efficiency and the solution generated by our approach can satisfy the LCS constraint of all the benchmarks in the contest, with a fair capacitance usage.

Redundancy Addition and Removal (RAR), one of the major combinational logic perturbation techniques, has been shown to be very useful for many EDA optimization tasks. However, all the currently known RAR techniques did not analyze and make use of unreachable states, which are abundant in sequential circuits. These unreachable states can be considered as input don't cares and can add an extra flexibility in locating alternative wires. In this paper, we study the fundamental theory and propose a reasoning scheme for locating alternative wires without performing wasteful redundancy tests. To explore the deeper effect of unreachable states, the concept is extended to illegal assignments and the fault independent redundancy identification is applied on illegal assignments to find flexibilities introduced by unreachable states. On the experiments carried for both MCNC and industry benchmarks, it is shown that using such an idea, a remarkable increase of more than 100% (averagely) in the number of alternative wires can be found, which should be quite useful as most of today's practical circuits are sequential.

Digital Microfluidic Biochip (DMFB) is a revolutionary technology for performing lab-on-a-chip experiments. Comparing to traditional direct-addressing design of DMFB, Cross-Referencing Biochip is a flexible design which not only helps to reduce pin number on chip but also brings down manufacturing cost. Following the generally accepted DMFB top-down design methodology, namely task scheduling, resource binding, module placement, droplet routing, previous works that focus on cross-referencing biochip routing are all based on the placement result generated for direct-addressing biochip. In this paper, we present an ILP-based placement method that first utilizes the property of cross-referencing for the purpose of optimizing routing. Furthermore, one previously ignored electrode interference problem on modules (blocks) is addressed in this paper. Real-life bioassay protocol based benchmarks are used to evaluate the proposed method. Experimental results show that the placement result generated by our placer yields better routing result comparing with those from placer for direct-addressing DMFB.