Double patterning technology (DPT) is regarded as the most practical solution for the sub-22nm lithography technology. DPT decomposes a single layout into two masks and applies double exposure to print the shapes in the layout. DPT requires accurate overlay control. Thus, the primary objective in DPT decomposition is to minimize the number of stitches (overlay) between the shapes in the two masks. The problem of minimizing the number of stitches in DPT decomposition is conjectured to be NP-hard. Existing approaches either apply Integer Linear Programming (ILP) or use heuristics. In this paper, we show that the problem is actually in P and present a method to decompose a layout for DPT and minimize the number of stitches optimally. The complexity of the method is O(n1.5log n). Experimental results show that the method is even faster than the fast heuristics.

Layout optimization is a powerful technique for design migration, circuit performance tuning and design for manufacturing. In this paper, we study the problem of layout optimization for the hierarchical circuits in modern VLSI designs which essentially can be formulated as the Integer Linear Programming(ILP) problem. Existing approaches are either unable to handle hierarchy, inefficient or failing to provide the feasible integer solutions for large scale hierarchical layouts. We present a practical method, IRLS algorithm (Iteratively Rounding and LP Solving) which consists of a proper rounding strategy based on the careful analysis of hierarchical layout constraints, to obtain a feasible integer solution in the constraint-based layout modification process, thus enabling efficient optimization for large scale hierarchical layouts, and specifically avoiding the need to use the general ILP solvers. Experimental results demonstrate the efficiency and effectiveness of the IRLS algorithm. Compared with the general ILP/MILP solver, the IRLS algorithm can obtain decent results with much less runtime (speed-up ranging from 4,000X to 360,000X). Compared with the two-step approach[2] on legalizing a set of large scale industry circuit layouts, the IRLS algorithm can provide much better solution (satisfying all abutment/alignment constraints that the two-step approach fails to meet).

Designs using simple geometric layout objects (such as points, sticks and rectangles) with Restrictive Design Rules (RDRs) on each layout object (i.e., it must be placed on a set of grids subject to a set of ground rules) have been introduced as an approach to better enable design for manufacturability (DFM) in ultra-deep submicron designs[9]. In this paper, we study the problem of migrating the conventional shape-based layouts to the simplified layouts with RDR constraints. We present a migration flow which consists of two process steps: (1) conversion where shapes (such as polygons) are converted to simple geometric objects (such as sticks) while the topology is maintained, and (2) grid legalization for RDRs where the simple geometric objects are placed on grid subject to the given set of ground rules by using a novel legalization algorithm, the Minimum Perturbation-driven Graph-based Grid Legalization(MP-GGL) algorithm. We demonstrate the effectiveness of the flow by successfully migrating a set of library cells in the conventional shape-based technology to the simplified layouts with RDR constraints. 1.

Existing floorplanning algorithms compact blocks to the left and bottom. Although the compaction obtains an optimal area, it may not be good for meeting other objectives such as minimizing the total wire length, which is the first-order objective. It is not known in the literature how to place blocks to obtain an optimal wire length. This paper first shows that the problem can be formulated by linear programming. Thereafter, instead of using the general, but slow, linear programming, this paper proposes an efficient minimum-cost flow-based approach to solve it. This approach guarantees to obtain the minimum total wire length in polynomial time and meanwhile keep the minimum area by distributing white space smarter for a given floorplan topology. This paper also shows that the approach can be easily extended to handle constraints such as fixed frame (fixed area), input-output (IO) pins, preplaced blocks, boundary blocks, range placement, alignment and abutment, rectilinear blocks, soft blocks, one-dimensional cluster placement, and bounded net delay, without loss of optimality. Practically, the algorithm is so efficient that it finishes in less than 0.4 s for all Microelectronics Center of North Carolina (MCNC) benchmarks of block placement. It is also very effective. Experimental results show that the wire length of very compact floorplans can even be improved by 4.2%. Thus, it provides an ideal way for postfloorplanning refinement

Existing floorplanning algorithms compact blocks to the left and bottom. Although the compaction obtains an optimal area, it may not be good to meet other objectives such as minimizing total wire length which is the first-order objective. It is not known in the literature how to place blocks to obtain an optimal wire length. In this paper, we first show that the problem can be formulated as linear programming. Thereafter, instead of using the general but slow linear programming, we propose an efficient min-cost flow based approach to solve it. Our approach guarantees to obtain the minimum of total wire length in polynomial time and meanwhile keep the minimum area by distributing white space smarter for a given floorplan topology. We also show that the approach can be easily extended to handle constraints such as fixed-frame (fixed area), IO pins, pre-placed blocks, boundary blocks, range placement, alignment and abutment, rectilinear blocks, soft blocks, one-dimensional cluster placement, and bounded net delay, without loss of optimality. Practically, the algorithm is so efficient in that it finishes in less than 0.4 seconds for all MCNC benchmarks of block placement. It is also very effective. Experimental results show we can improve 4.2% of wire length even on very compact floorplans. Thus it provides an ideal way of post-floorplanning (refine floorplanning).

The buffer block methodology has become increasingly popular as more and more buffers are needed in deep-submicron design, and it leads to many challenging problems in physical design. In this article, we present a polynomial-time exact algorithm for integrated pin assignment and buffer planning for all two-pin nets from one macro block (source block) to all other blocks of a given buffer block plan, while minimizing the total cost α ˙ W + β ˙ R for any positive α and β where W is the total wirelength, and R is the number of buffers. By applying this algorithm iteratively (each time, pick one block as the source block), it provides a polynomial-time algorithm for pin assignment and buffer planning for nets among multiple macro blocks. Experimental results demonstrate its efficiency and effectiveness.

The antenna problem is a phenomenon of plasma-induced gate-oxide degradation. It directly affects manufacturability of very large scale integration (VLSI) circuits, especially in deep submicron technology using high-density plasma. Diode insertion is a very effective way to solve this problem. Ideally, diodes are inserted directly under the wires that violate antenna rules. But in today's high-density VLSI layouts, there is simply not enough room for "under-the-wire" diode insertion for all wires. Thus, it is necessary to insert many diodes at legal "off-wire" locations and extend the antenna-rule violating wires to connect to their respective diodes. Previously, only simple heuristic algorithms were available for this diode insertion and routing problem. In this paper, we show that the diode insertion and routing problem for an arbitrary given number of routing layers can be optimally solved in polynomial time. Our algorithm guarantees finding a feasible diode insertion and routing solution whenever one exists. Moreover, we can guarantee to find a feasible solution to minimize a cost function of the form /spl alpha//spl times/L+/spl beta//spl times/N, where L is the total length of extension wires and N is the total number of vias on the extension wires. Experimental results show that our algorithm is very efficient.

In this paper, we present an integrated approach for floorplanning and bus planning, i.e., bus-driven floorplanning (BDF). We are given a set of circuit blocks and the bus specifications (i.e., the net list of blocks for the buses). A feasible BDF solution is a placement of all circuit blocks such that each bus can be realized as a rectangular strip (horizontal or vertical) going through all the blocks connected by the bus. The objective is to determine a feasible BDF solution that minimizes the floorplan area and the total bus area. Our approach is based upon the sequence-pair floorplan representation. After a careful analysis of the relationship between bus ordering and block ordering in the floorplan represented by a sequence pair, we derive feasibility conditions on sequence pairs that give feasible BDF solutions. Experimental results demonstrate the efficiency and effectiveness of our algorithm.

Macroblock pin assignment and routing are important tasks in physical design. Existing algorithms for these problems can be classified into two categories: 1) a two-step approach where pin assignment is followed by routing and 2) a net-by-net approach where pin assignment and routing for a single net are performed simultaneously. However, none of the existing algorithms is "exact" in the sense that they may fail to route all of the nets even though a feasible solution exists. This remains to be true even if only two-pin nets with fixed pins between two blocks are concerned. In this paper, we consider the problem of two-pin net connections from one macroblock to all of the other blocks, and present the first polynomial-time exact algorithm for simultaneous pin assignment and routing for all of the two-pin nets between one block (source block) and all of the other blocks. In addition to finding a feasible solution whenever one exists, it guarantees to find a pin-assignment/routing solution with minimum cost /spl alpha//spl middot/W+/spl beta//spl middot/V, where W is the total wire length and V is the total number of vias. Our algorithm has various applications. 1) It is suitable in engineering change order (ECO) situations where the existing solution is modified incrementally. 2) Given any pin assignment and routing solution obtained by any existing method, our algorithm can be used to increase the number of routed nets and reduce the routing cost. Furthermore, it provides an efficient algorithm for the pin assignment and routing problem of all of the blocks. The method is applicable to both global and detailed routing with arbitrary routing obstacles on multiple layers. Experimental results demonstrate its efficiency and effectiveness.

In this paper, we present a floorplanning algorithm based on sequence pair representation. Our floorplanner has the following important features: 1) It is explicitly designed for fixed-frame floorplanning, which is different from traditional well-researched min-area floorplanning. Moreover, we also show that it can be adapted to minimize total area. 2) It addresses the problem of handling alignment constraint which arises in bus structure. 3) It deals with performance constraint such as bounded net delay, while many existing floorplanners just minimize total wire length. 4) More importantly, even with all these constraints the algorithm is very fast in that it evaluates the feasibility of a sequence pair and translates to a floorplan in O(n log log n) time typically where n is the number of blocks and the number of constrained blocks is O(n), which is significantly faster than the O(n3) method operating on constraint graph. Our algorithm is based on computing the longest common subsequence of a pair of weighted sequences. Experimental results on MCNC benchmark for block placement show the promise of the method.

The buffer block methodology has become increasingly popular as more and more buffers are needed in deep-submicron design, and it leads to many challenging problems in physical design. In this paper, we present a polynomial-time exact algorithm for integrated pin assignment and buffer planning for all two-pin nets from one macro block (source block) to all other blocks of a given buffer block plan as well as minimizing the total cost α ċ W + Β ċ R for any positive α and Β where W is the total wire length and R is the number of buffers. By applying this algorithm iteratively (each time pick one block as the source block), it provides a polynomial-time algorithm for pin assignment and buffer planning for nets among multiple macro blocks. Experimental results demonstrate its efficiency and effectiveness.

Antenna problem is a phenomenon of plasma induced gate oxide degradation. It directly affects manufacturability of VLSI circuits, especially in deep-submicron technology using high density plasma. Diode insertion is a very effective way to solve this problem Ideally diodes are inserted directly under the wires that violate antenna rules. But in today's high-density VLSI layouts, there is simply not enough room for "under-the-wire" diode insertion for all wires. Thus it is necessary to insert many diodes at legal "off-wire" locations and extend the antenna-rule violating wires to connect to their respective diodes. Previously only simple heuristic algorithms were available for this diode insertion and routing problem. In this paper we show that the diode insertion and routing problem for an arbitrary given number of routing layers can be optimally solved in polynomial time. Our algorithm guarantees to find a feasible diode insertion and routing solution whenever one exists. Moreover we can guarantee to find a feasible solution to minimize a cost function of the form /spl alpha/ /spl middot/ L + /spl beta/ /spl middot/ N where L is the total length of extension wires and N is the total number of Was on the extension wires. Experimental results show that our algorithm is very efficient.

Electron projection lithography (EPL) is a leading candidate for next generation lithography (NGL) in VLSI production. The membrane mask used in EPL is divided into sub-fields by struts for structural support. A layout must be partitioned into these sub-fields on mask and then stitched back together by the EPL tool on wafer. To minimize possible stitching errors, partitioning of a mask layout should minimize cuts of layout features in the overlapping area between two adjacent sub-fields. This paper presents the first formulation of the mask layout partitioning problem for EPL as a graph problem. The graph formulation is optimally solved with a shortest path approach. Two other techniques are also presented to speed up computation. Experimental runs on data from a real industry design show excellent results.

Manufacturability of a design that is processed with shallow-trench isolation (STI) depends on the uniformity of the chemical-mechanical polishing (CMP) step in STI. The CMP step in STI is a dual-material polish for which all previous studies on dummy-feature placement for single-material polish by Kahng et al. (1999), Tian et al. (2000), and Chen et al. (2000) are not applicable. Based on recent semiphysical models of polish-pad bending by Ouma et al (1998), local polish-pad compression by Grillaert (1999) and Smith (1999), and different polish rates for materials present in a dual-material polish by Grillaert (1999) and Tugbawa et al. (1999), this paper derives a time-dependent relation between post-CMP topography and layout pattern density for CMP in STI. Using the dependencies derived, the first formulation of dummy-feature placement for CMP in STI is given as a nonlinear-programming problem. An iterative approach is proposed to solve the dummy-feature placement problem. Computational experience on four layouts from Motorola is given.

In this paper we present FAST-SP which is a fast block placement algorithm based on the sequence-pair placement representation. FAST-SP has two significant improvements over previous sequence-pair based placement algorithms: 1) FAST-SP translates each sequence pair to its corresponding block placement in O(n log log n) time based on a fast longest common subsequence computation. This is much faster than the traditional O(n2) method by first constructing horizontal and vertical constraint graphs and then performing longest path computations. As a result, FAST-SP can examine more sequence pairs and obtain a better placement solution in less runtime. 2) FAST-SP can handle placement constraints such as pre-placed constraint, range constraint, and boundary constraint. No previous sequence-pair based algorithms can handle range constraint and boundary constraint. Fast evaluation in O(n log log n) time is still valid in the presence of placement constraints and a novel cost function which unifies the evaluation of feasible and infeasible sequence pairs is used. We have implemented FAST-SP and obtained excellent experimental results. For all MCNC benchmark block placement problems, we have obtained the best results ever reported in the literature (including those reported by algorithms based on O-tree and B*-tree) with significantly less runtime. For example, the best known result for ami49 (36.8 mm2) was obtained by a B*-tree based algorithm using 4752 seconds, and FAST-SP obtained a better result (36.5 mm2) in 31 seconds.

Buffer insertion and wire sizing are critical in deep submicron VLSI design. This paper studies the problem of constructing routing trees with simultaneous buffer insertion and wire sizing in the presence of routing and buffer obstacles. No previous algorithms consider all these factors simultaneously. Previous dynamic programming based algorithm is first extended to solve the problem. However, with the size of routing graph increasing and with wire sizing taken into account, the time and space requirement increases enormously. Then a new approach is proposed to formulate the problem as a series of graph problems. The routing tree solution is obtained by finding shortest paths in a series of graphs. In the new approach, wire sizing can be handled almost without any additional time and space requirement, Moreover, the time and space requirement is only polynomial in terms of the size of routing graph. Our algorithm differs from traditional dynamic programming, and is capable of addressing the problem of inverter insertion and sink polarity. Both theoretical and experimental results show that the graph-based algorithm outperforms the DP-based algorithm by a large margin. We also propose a hierarchical approach to construct routing tree for a large number of sinks.

Macro-block pin assignment and routing are important tasks in physical design planning. Existing algorithms for these problems can be classified into two categories: 1) a two-step approach where pin assignment is followed by routing, and 2) a net-by-net approach where pin assignment and routing for a single net are performed simultaneously. None of the existing algorithms is "exact" in the sense that the algorithm may fail to route all nets even though a feasible solution exists. This remains to be true even if only 2-pin nets between two blocks are concerned. In this paper, we present the first polynomial-time exact algorithm for simultaneous pin assignment and routing for 2-pin nets from one block (source block) to all other blocks. In addition to finding a feasible solution whenever one exists, it guarantees to find a pin-assignment/routing solution with minimum cost /spl alpha//spl middot/W + /spl beta//spl middot/V, where W is the total wirelength and V is the total number of vias. Our algorithm has various applications and is applicable to both global and detailed routing with arbitrary routing obstacles on multiple layers. Experimental results demonstrate its efficiency and effectiveness.

Manufacturability of a design that is processed with shallow trench isolation (STI) depends on the uniformity of the chemical-mechanical polishing (CMP) step in STI. The CMP step in STI is a dual-material polish, for which all previous studies on dummy feature placement for single-material polish [3, 11, 1] are not applicable. Based on recent semi-physical models of polish pad bending [5], local polish pad compression [2, 10], and different polish rates for materials present in a dual-material polish [2, 13], this paper derives a time-dependent relation between post-CMP topography and layout pattern density for CMP in STI. Using the dependencies derived, the first formulation of dummy feature placement for CMP in STI is given as a nonlinear programming problem. An iterative approach is proposed to solve the dummy feature placement problem. Computational experience on four layouts from Motorola is given.

Murata et al. (1996) introduced an elegant representation of block placement called sequence pair. All block-placement algorithms that are based on sequence pairs use simulated annealing where the generation and evaluation of a large number of sequence pairs is required. Therefore, a fast algorithm is needed to evaluate each generated sequence pair, i.e., to translate the sequence pair to its corresponding block placement. This paper presents a new approach to evaluate a sequence pair based on computing longest common subsequence in a pair of weighted sequences. We present a very simple and efficient O(n/sup 2/) algorithm to solve the sequence pair evaluation problem. We also show that using a more sophisticated data structure, the algorithm can be implemented to run in O (n log log n) time. Both implementations of our algorithm are significantly faster than the previous O(n/sup 2/) graph-based algorithm. For example, we achieve 60 /spl times/ speedup over the previous algorithm when input size n = 128. As a result, we can examine a million sequence pairs within one minute for typical input size of placement problems. For all MCNC benchmark block-placement problems, we have obtained the best results ever reported in the literature (including those reported by algorithms based on O tree and B* tree) with significantly less runtime. For example, the best known result for ami49 (36.8 mm/sup 2/) was obtained by a B*-tree-based algorithm using 4752 s and we obtained a better result (36.5 mm/sup 2/) in 31 s.

Murata et al. (1996) introduced an elegant representation of block placement called sequence pair. All block placement algorithms which are based on sequence pairs use simulated annealing where the generation and evaluation of a large number of sequence pairs is required. Therefore, a fast algorithm is needed to evaluate each generated sequence pair, i.e. to translate the sequence pair to its corresponding block placement. This paper presents a new approach to evaluate a sequence pair based on comparing longest common subsequence in a pair of weighted sequences. We present a very simple and efficient O(n/sup 2/) algorithm to solve the sequence pair evaluation problem. We also show that using a more sophisticated data structure, the algorithm can be implemented to run in O(n log n) time. Both implementations of our algorithm are significantly faster than the previous O(n/sup 2/) graph-based algorithm. For example, we achieve 60/spl times/ speedup over the previous algorithm when input size n=128.

The problem of planning the locations of large number of buffers is of utmost importance in deep submicron VLSI design.Recently, Cong et al in [1] proposed an algorithm to directly address this problem.Given a placement of circuit blocks, a key step in [1] is to use the free space between the circuit blocks for inserting as many buffers as possible.This step is very important because if all buffers can be inserted into existing spaces, no expansion of chip area would be needed.An effective greedy heuristic was used in [1] for this step.In this paper, we give a polynomial-time optimal algorithm for solving the problem of inserting maximum number of buffers into the free space between the circuit blocks.In the case where the "costs" of placing a buffer at different locations are different, we can guarantee to insert maximum number of buffers with minimum total cost.Our algorithm is based on efficient min-cost network-flow computations.