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.

Modern PCBs have to be routed manually since no EDA tools can successfully route these complex boards. An auto-router for PCBs would improve design productivity tremendously since each board takes about 2 months to route manually. This paper focuses on a major step in PCB routing called bus planning. In the bus planning problem, we need to simultaneously solve the bus decomposition, escape routing, layer assignment and global bus routing. This problem was partially addressed by Kong et al. in [3] where they only focused on the layer assignment and global bus routing, assuming bus decomposition and escape routing are given. In this paper, we present an ILP-based solution to the entire bus planning problem. We apply our bus planner to an industrial PCB (with over 7000 nets and 12 signal layers) which was previously successfully routed manually, and compare with a state-of-the-art industrial internal tool where the layer assignment and global bus routing are based on the algorithm in [3]. Our bus planner successfully routed 97.4% of all the nets. This is a huge improvement over the industrial tool which could only achieve 84.7% routing completion for this board.

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.

Conventional CMOS devices are facing an increasing number of challenges as their feature sizes scale down. Graphene nanoribbon (GNR) based devices are shown to be a promising replacement of traditional CMOS at future technology nodes. However, all previous works on GNRs focus at the device level. In order to integrate these devices into electronic systems, routing becomes a key issue. In this article, the GNR routing problem is studied for the first time. We formulate the GNR routing problem as a minimum hybrid-cost shortest path problem on triangular mesh (“hybrid” means that we need to consider both the length and the bending of the routing path). We show that by graph expansion, this minimum hybrid-cost shortest path problem can be solved by applying the conventional shortest path algorithm on the expanded graph. Experimental results show that our GNR routing algorithm effectively handles the hybrid cost.

As technology continues to scale to 14nm node, Double Patterning Lithography (DPL) is pushed to near its limit. Triple Patterning Lithography (TPL) is a considerable and natural extension along the paradigm of DPL. With an extra mask to accommodate the features, TPL can be used to eliminate the unresolvable conflicts and minimize the number of stitches, which are pervasive in DPL process, and thus smoothen the layout decomposition step. Considering TPL during routing stage explores a larger solution space and can further improve the layout decomposability. In this paper, we propose the first triple patterning aware detailed routing scheme, and compare its performance with the double patterning version in 14nm node. Experimental results show that, using TPL, the conflicts can be resolved much more easily and the stitches can be significantly reduced in contrast to DPL.

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.

In this paper, we introduce and study the rectangle escape problem (REP), which is motivated by printed circuit board (PCB) bus escape routing. Given a rectangular regionRand a setSof rectangles withinR, the REP is to choose a direction for each rectangle to escape to the boundary ofR, such that the resultant maximum density overRis minimized. We prove that the REP is NP-complete, and show that it can be formulated as an integer linear programming (ILP). A provably good approximation algorithm for the REP is developed by applying linear programming (LP) relaxation and a special rounding technique to the ILP. In addition, an iterative refinement procedure is proposed as a postprocessing step to further improve the results. Our approximation algorithm is also shown to work for more general versions of REP: weighted REP and simultaneous REP. Our approach is tested on a set of industrial PCB bus escape routing problems. Experimental results show that the optimal solution can be obtained within several seconds for each of the test cases.

In this paper, we introduce and study the Rectangle Escape Problem (REP), which is motivated by PCB bus escape routing. Given a rectangular region R and a set S of rectangles within R, the REP is to choose a direction for each rectangle to escape to the boundary of R, such that the resultant maximum density over R is minimized. We prove that the REP is NP-Complete, and show that it can be formulated as an Integer Linear Program (ILP). A provably good approximation algorithm for the REP is developed by applying Linear Programming (LP) relaxation and a special rounding technique to the ILP. This approximation algorithm is also shown to work for a more general version of REP with weights (weighted REP). In addition, an iterative refinement procedure is proposed as a postprocessing step to further improve the results. Our approach is tested on a set of industrial PCB bus escape routing problems. Experimental results show that the optimal solution can be obtained within 3 seconds for each of the test cases.

Conventional CMOS devices are facing an increasing number of challenges as their feature sizes scale down. Graphene nanoribbon (GNR) based devices are shown to be a promising replacement of traditional CMOS at future technology nodes. However, all previous works on GNRs focus at the device level. In order to integrate these devices into electronic systems, routing becomes a key issue. In this paper, the GNR routing problem is studied for the first time. We formulate the GNR routing problem as a minimum hybrid-cost shortest path problem on triangular mesh (“hybrid” means that we need to consider both the length and the bending of the routing path). In order to model this hybrid-cost problem, we apply graph expansion and introduce a shortest red-black path problem on the expanded graph. We then propose an algorithm that solves the shortest red-black path problem optimally. This algorithm is then used in a negotiated congestion based routing scheme. Experimental results show that our GNR routing algorithm effectively handles the hybrid cost.

Bus escape routing is a critical problem in modern PCB design. Due to the huge pin count and high density of the pin array, it usually requires multiple layers to route the buses without any conflict. How to assign the escape routing of buses to different layers becomes an important issue. In addition, some buses are required to be assigned on consecutive layers, which adds more difficulties to the layer assignment problem. In this paper, we propose a branch-and-bound based algorithm that optimally solves the layer assignment problem of bus escape routing. Our algorithm guarantees to produce a feasible layer assignment of the buses with a minimum number of layers. We applied our algorithm on industrial data and the experimental results validate our approach.

Simultaneous escape routing on dense circuit boards is a very challenging task and a great amount of manual effort is still needed in order to achieve high routability. In this paper, we present a new simultaneous escape routing algorithm which is based upon a novel boundary routing approach. Our algorithm can solve complicated escape problems in a very short time. For a set of industrial escape problems, our algorithm successfully solved all of them while Cadence Allegro PCB router was only able to complete the routing of half of the problems. In addition, we propose a clustering strategy targeting at large escape routing problems. Experimental results show that this clustering strategy can significantly cut down the runtime of our router when solving large problems.

Power consumption has become a crucial problem in modern circuit design. Multiple supply voltage (MSV) design is introduced to provide higher flexibility in controlling the power and performance tradeoff. One important requirement of MSV design is that timing constraints of the circuit must be satisfied after voltage assignment of the cells. In this article, we develop two algorithms to solve the voltage assignment problem under timing constraints, namely, min-cost flow (MCF) and value-oriented branch-and-bound (VOBB). In the MCF algorithm, the voltage assignment problem is formulated as a convex cost dual network flow problem, and can be solved optimally in polynomial time under certain conditions by calling a MCF solver. The VOBB algorithm, which is a VOBB-based searching method, solves the voltage assignment problem optimally in general cases by employing the MCF algorithm and a linear programming solver as subroutines. At last, we propose a MSV-driven floorplanning framework that optimizes power consumption and physical layout of a circuit simultaneously during the floorplanning stage, by embedding the MCF algorithm into a simulated annealing-based floorplanner and applying the VOBB algorithm as a postprocessing step. We compared our approach with the latest works on this problem, and the experimental results show that, using our approach, significant improvement on power saving can be achieved in much less running time, which confirms the effectiveness and efficiency of our method.

In today's system-on-chip designs, both digital and analog parts of a circuit will be implemented on the same chip. Parasitic mismatch induced by layout will affect circuit performance significantly for analog designs. Consideration of symmetry and common centroid constraints during placement can help to reduce these errors. Besides these two specific types of placement constraints, other constraints, such as alignment, abutment, preplace, and maximum separation, are also essential in circuit placement. In this paper, we will present a placement methodology that can handle all these constraints at the same time. To the best of our knowledge, this is the first piece of work that can handle symmetry constraint, common centroid constraint, and other general placement constraints, simultaneously. Experimental results do confirm the effectiveness and scalability of our approach in solving this mixed constraint-driven placement problem.

Before VLSI design starts, it is strategically important to do product planning for targeted market segments that need specific applications, and to optimally reuse at different levels to save design and silicon costs with shorter time-to-market schedule. Conventional ASIC or SoC design floorplan usually targets for one single product; and, high efforts in re-floorplan and re-convergence for different products are still required if there is no pre-design stage multi-product planning. Therefore, the problem of designing floorplans at product or market planning stage that simultaneously optimizes multiple products, or Multi-product Floorplanning, is introduced. To the best of our knowledge, this is the first work in literature that addresses this newly emerged and financially important problem. We start with the necessary number of basic functional blocks to accommodate all the products, and pack them using a simulated annealing (SA) based floorplanner that can easily incorporate other costs (e.g., product finance weights). Given a candidate floorplan, we provide both an O(n3) exact algorithm and a O(n) greedy heuristic to identify the Minimum Feasible Region for each product, where n is the number of basic blocks in this floorplan. These identification procedures are integrated into the SA framework to generate a floorplan that favors the configurable multi-product design. The effectiveness of our approach is validated by promising results on several data sets derived from industrial test cases.

The maximum disjoint subset (MDS) of rectangles is a subset of non-overlapping rectangles with the maximum total weight. The problem of finding the MDS of general rectangles has been proven to be NP-complete in [6]. In this paper, we focus on the problem of finding the MDS of boundary rectangles, which is an open problem and is closely related to some difficult problems in PCB routing. We propose a polynomial time algorithm to optimally solve the MDS problem of boundary rectangles. Then we show that this algorithm can be applied to find the optimal solution of the bus escape routing problem.

As an important step in PCB design, the escape routing problem has been extensively studied in literature. However, few studies have been done on the escape routing of differential pairs. In this paper, we study the differential pair escape routing problem and propose two algorithms. The first one computes the optimal routing for a single differential pair while the second one is able to simultaneously route multiple differential pairs considering both routability and wire length. We then propose a two-stage routing scheme based on the two algorithms. Experimental results show that our routing scheme efficiently and effectively solves the differential pair escape routing test cases we obtained from industry.

Simultaneous escape routing on dense circuit boards is a very challenging task and great amount of manual effort is still needed in order to achieve high routability. In this paper, we present a new simultaneous escape routing algorithm which is based upon a novel boundary routing approach. Our algorithm can solve complicated escape problems in very short time. For a set of industrial escape problems, our algorithm successfully solved all of them while Cadence Allegro PCB router was only able to complete the routing of half of the problems.

Energy efficiency has become a very important issue to be addressed in today's system-on-a-chip (SoC) designs. One way to lower power consumption is to reduce the supply voltage. Multisupply voltage (MSV) is thus introduced to provide flexibility in controlling the power and performance tradeoff. In region-based MSV, circuits are partitioned into ¿voltage islands¿ where each island occupies a contiguous physical space and operates at one voltage level. These tasks of island partitioning and voltage level assignment should be done simultaneously in the floorplanning process in order to take those important physical information into consideration. In this paper, we consider this core-based voltage island driven floorplanning problem including islands with power down mode, and propose a method to solve it. Given a candidate floorplan solution represented by a normalized Polish expression, we are able to obtain optimal voltage assignment and island partitioning (including islands with power down mode) simultaneously to minimize the total power consumption. Simulated annealing is used as the basic searching engine. By using this approach, we can achieve significant power saving (up to 50%) for all datasets, without any significant increase in area and wire length. We compared our approach with the most updated previous work on the same problem, and results show that our approach is much more efficient and is able to save more power in most cases. We have also studied two other approaches to solve the same problem, a simple dynamic programming approach and a lowest possible power consumption approach. Experimental results show that ours can perform the best among these three approaches. Our floorplanner can also be extended to minimize the number of level shifters, to address a minVdd version of the problem and to simplify the power routing step by placing islands close to their corresponding power pins.

Power consumption has become a crucial problem in modern circuit design. Multiple Supply Voltage (MSV) design is introduced to provide higher flexibility in controlling the power and performance trade-off. One important requirement of MSV design is that timing constraints of the circuit must be satisfied after voltage assignment of the cells. In this paper, we will show that the voltage assignment task on a given netlist can be formulated as a convex cost dual network flow problem and can be solved optimally in polynomial time using a cost-scaling algorithm when the delay choices of each module are continuous in the real or integer domain. We can make use of this approach to obtain a feasible voltage assignment solution in the general cases with power consumption approximating the minimum one. Furthermore, we will propose a framework to optimize power consumption and physical layout of a circuit simultaneously during the floorplanning stage, by embedding this cost-scaling solver into a simulated annealing based floorplanner. This is effective in practice due to the short running time of the solver. We compared our approach with the latest work [9] on the same problem, and the experimental results show that, using our framework, significant improvement on power saving (18% less power cost on average) can be achieved in much less running time (7X faster on average) for all the test cases, which confirms the effectiveness of our approach.

Energy efficiency has become one of the most important issues to be addressed in today’s System-on-a-Chip (SoC) designs. One way to lower the power consumption is to reduce the supply voltage. Multi-supply voltage (MSV) is thus introduced to provide higher flexibility in controlling the power and performance trade-off. In regionbased MSV, circuits are partitioned into “voltage islands” where each island occupies a contiguous physical space and operates at one supply voltage. These tasks of island partitioning and voltage level assignments should be done simultaneously in the floorplanning process in order to take those important physical information into consideration. In this paper, we consider this core-based voltage island driven floorplanning problem including islands with power down mode, and propose a method to solve it. Given a candidate floorplan solution represented by a normalized Polish expression, we are able to obtain optimal voltage assignment and island partitioning (including islands with power down mode) simultaneously to minimize the total power consumption. Simulated annealing is used as the basic searching engine. By using this approach, we can achieve significant power savings (up to 50%) for all data sets, without any significant increase in area and wire length. Our floorplanner can also be extended to minimize the number of level shifters between different voltage islands and to simplify the power routing step by placing the islands in proximity to the corresponding power pins.

In order to reduce parasitic mismatch in analog circuits, some groups of devices are required to share a common centroid while being placed. Devices are split into smaller ones and placed with a common center point. We will address this problem of handling common centroid constraint in placement. A new representation called Center- based Corner Block List (C-CBL) is proposed which is a natural extension of Corner Block List (CBL) [1] to represent a common centroid placement of a set of device pairs. C-CBL is complete and non-redundant in representing any common centroid mosaic packings with pairs of blocks to be matched. To address the same problem with an additional constraint that devices are required to be placed uniformly to average out the parasitic errors, a grid-based approach is proposed. Experimental results show that both approaches are fast and promising, and have high scalability that even large data sets can be handled effectively.