WO2001020502A9

WO2001020502A9 - Optimal phase conflict removal for layout of alternating phase-shifting masks

Info

Publication number: WO2001020502A9
Application number: PCT/US2000/025572
Authority: WO
Inventors: Andrew B Kahng; Huijuan Wang; Alexander Z Zelikovsky
Original assignee: University of California Berkeley; University of California San Diego UCSD
Current assignee: University of California Berkeley; University of California San Diego UCSD
Priority date: 1999-09-16
Filing date: 2000-09-18
Publication date: 2001-10-11
Anticipated expiration: 2002-03-16
Also published as: WO2001020502A1; AU7829800A

Abstract

Method for resolving phase conflict for dark-field and bright-field alternating phase-shifting mask technologies is disclosed. For the dark-field masks, the method consists of a new 2-coloring and compaction approach that simultaneously optimizes layout and phase assignment which is based on planar embedding of an associated phase conflict graph; optimal and fast algorithms minimizing the number of phase conflicts that must be removed to ensure 2-colorability of the phase conflict graph; and fast gadget-based algorithms solving optimally the corresponding T-join problem. For the bright-field masks, the method consists of a new 2-coloring and compaction approach that simultaneously optimizes layout and phase assignment which is based on planar embedding of an associated feature graph, wherein the feature graph incorporates two types of layout modifications: increasing spacing and changing the width of critical thin features; optimal fast algorithms minimizing the number of phase conflicts that must be removed by increasing spacing; and approximate fast algorithms minimizing the number of phase conflicts that must be removed by both types of layout modifications.

Description

OPTIMAL PHASE CONFLICT REMOVAL FOR LAYOUT OF ALTERNATING PHASE-SHIFTING MASKS

CROSS-REFERENCE TO RELATED APPLICATIONS This application claims priority from U.S. Application No. 60/154,264, filed

September 16, 1999, the disclosure of which is incorporated herein by reference.

BACKGROUND OF THE INVENTION

1. Field of the Invention Modern manufacturing process of integrated circuits is based on alternating phase-shifting masks. The alternating phase-shifting masks require phase assignment to apertures. The present invention addresses the modifications that are necessary to apply to physical VLSI layout in order to obtain valid phase assignment. The present invention affords new optimal methods for finding and removing phase conflicts for the dark-field and for the bright-field alternating phase-shifting masks, simultaneously minimizing the area of the physical VLSI layout.

2. Review of Prior Art

For the dark-field alternating phase-shifting mask technology there were suggested two methods reviewed below, while for the bright-field masks no prior methods are known.

The heuristic or Moniwa et al. (see "Heuristic Method for Phase-Conflict Minimization in Automatic Phase-Shift Mask Design" , A. Moniwa., T. Terasawa, K. Nakajo, .J. Sakemi and S. Okazaki, Japan Journal of Applied Physics 34 (1995), pp. 6584-6589) first constructs the conflict graph G, then creates a list of all odd cycles in G using an enumerative approach. The heuristic then iteratively finds and deletes the edge that is in the greatest number of minimum-length odd cycles. Deletion is accomplished by increasing the lower bound on separation between the corresponding features, and then applying a compactor to perturb the shape or position of these features (see Figure 7). This approach may be feasible for the cell layout editing context but likely does not scale to large instances since the number of odd cycles can be exponential in the size of the layout. Moreover, the heuristic does not. necessarily delete the minimum number of edges, nor will it necessarily select edges whose deletion will have minimum impact on the layout. Ooi et al. (see "Method of Designing Phase-Shifting Masks Utilizing a Compactor", K Ooi, K. Koyama andM. Kiryu, Japan Journal of Applied Physics 33 (1994), pp. 6774-6778) also suggested a compaction-based method which (i) produces a symbolic layout from the mask layout; (ii) performs phase assignment in the symbolic layout; and (iii) compacts the symbolic layout using minimum spacing design rules consistent with the phase assignment. The advantage of compaction-based method is that it is fully automated and guarantees to remove all odd cycles from the conflict graph. On the other hand, the phase assignment step is relatively oblivious to details to the mask layout; the ensuing compaction step may not minimize distortion of the original layout.

SUMMARY OF THE INVENTION The present invention gives a new method for resolving phase conflicts for dark-field and bright-field alternating phase-shifting mask technologies. For the dark-field masks, this method consists of • A new 2-coloring and compaction approach that simultaneously optimizes layout and phase assignment which is based on planar embedding of an associated phase conflict graph.

• Optimal and fast algorithms minimizing the number of phase conflicts that must be removed to ensure 2-colorability of the phase conflict graph. These algorithms are based on reduction to the T-join problem which asks for a minimum weight edge set A such that a node u is incident to an odd number of edges of A if and only if u belongs to a given nude subset Tof a weighted graph.

• Fast gadget-based algorithms solving optimally the corresponding -join problem.

For the bright-field masks this method consists of

• a new 2-coloring and compaction approach that simultaneously optimizes layout and phase assignment which is based on planar embedding of an associated feature graph. Feature graph^' incorporates two types of layout modifications: increasing spacing and changing the width of critical features.

• Optimal fast algorithms minimizing the number of phase conflicts that must be removed by increasing spacing • Approximate fast algorithms minimizing the number of phase conflicts that must be removed by the both types of layout modifications.

3. Technical Basis of the Invention Alternating phase-shifting mask (AltPSM) technology is enabling to subwavelength process technology. AltPSM uses destructive interference between opposite- phase light (e.g., 0 phase and 180 phase) to improve contrast on the wafer between exposed and unexposed regions (see Figure 1). AltPSM affects circuit layout because there is no longer any concept of a "complete" design rules set: layout is correct if and only if a given layout-derived graph can be 2-colored. Since 2-colorability of this derived graph is difficult to maintain during layout creation, all proposed solutions use post-processing of layout to identify required perturbations, followed by layout compaction to achieve a phase-assignable final layout. There are two essentially different ALtPSM technologies: (1) dark-field AltPSM where the clearpage region corresponds to a feature (the negative photoresist is used) and (2) bright-field AltPSM where the clearpage region corresponds to gaps between features (the positive photoresist is used). For the both technologies it is necessary to assign phases to clearpage regions corresponding to 0 or 180 phase of the assigned light.

3.1 Dark-Field Alternating Phase-shifting Mask Technology The positive constants b < B define a simplified relationship between printability and the distance between two clearpage regions in the dark-field AltPSM technology. The distance between any two features cannot be smaller than b without violating the minimum spacing design rule. If the distance between two features is at least b but smaller than B, the features are in phase conflict. Phase conflict can be resolved by assigning opposite phases to the conflicting features. In other words, B defines the mimmum spacing rule when two features have the same phase. If the distance between two features is greater than or equal to B, there is no phase conflict and the features can be assigned arbitrary phases. Note that the values of b and B are layer-dependent. We also let w > b denote the minimum allowed width of any feature on the layer of interest. Finally, we assume that all features are rectilinearly oriented (all edges axis-parallel) polygons.

The Phase Assignment Problem: Given a layout, assign phases to all features such that no two conflicting features are assigned the same phase. If the phase assignment problem has a feasible solution, i.e., the layout is PSM-feasible, then the dark-field AltPSM technology can be applied for manufacturing of this layout. The overall objective of PSM layout design is to achieve minimum-area layout while maintaining PSM-feasibility, but assuming that feature widths and spacings can be sealed down to values achievable using PSM, will lead to well-compacted but PSM- infeasible layouts. This induces the following problem.

Minimum Distortion Problem. Given a layout, find a solution to the Phase Assignment Problem which requires minimum layout modification.

3.2 Bright-Field Alternating Phase-shifting Mask Technology

We will describe the bright AltPSM technology due to Wang and Pati and involves double exposure (two masks) on positive photoresist. With positive photoresist, development removes photoresist material from all regions that have been exposed with sufficient energy. Hence, areas defining features should be protected from light and phases should be assigned to clearpage areas of the mask outside the features (i.e., "bright field" or "clearpage field"). The AltPSM technology of is illustrated in Figure 2. In the figure 2, a poly feature includes a critical(-width) gate which requires phase-shifting to be successfully printed. The feature is formed by exposing two masks: (i) a "locally bright-field" AltPSM mask, followed by (ii) a binary (non-phase-shifting, standard chrome on glass) mask that protects the critical portion of the feature from light while also defining the non-critical width portions of the feature.

When the majority of features are at critical width then the incidence of phase shifters becomes "dense": the layout must leave room for phase shifters around nearly every feature, and finding compatible assignments of phases to shifters must be ensured. The latter task is quite difficult, and maintaining design productivity for logic applications requires automated phase-mask layout tools.

Figure 3 shows that when two vertical critical features are closely spaced, their phase shifters overlap, and must be assigned the same phase. On the other hand, when the features are widely spaced, their phase shifters can be assigned phases independently. We see that the overlap between shifters introduces dependencies between the phase assignments to shifters of corresponding features. Figure 4 gives simple layout examples for which there is no assignment of 0 and 180 phases to the shifters, such that (i) there are opposite-phase shifters on either side of each feature, and (ii) any shifters that overlap are assigned the same phase. In general, to minimize layout area, the phase assignment to shifters should eliminate or reduce the number of cases when adjacent shifters get opposite phases.

Phase Assignment Problem. Given a layout, find a phase assignment such that the following Conditions (1) and (2) are satisfied: • Condition (1): Phase shifters on opposite sides of each critical feature are assigned opposite phases; and • Condition (2): Any pair of overlapping shifters is assigned the same phase. We know from Figure 4 that conditions (l)-(2) cannot always be satisfied. Such situations are caused by odd cycles of phase dependencies. In graph-theoretic terms, only graphs free of odd cycles can be properly colored into two colors¹ - meaning that shifters of the corresponding layout can be properly assigned 0 and 180 phases. In such cases, for the chip to be manufacturable the layout must be modified so that; it becomes phase-assignable. A violation of condition (1) can be corrected via layout modification that increases the width of the corresponding critical feature, i.e., the feature must become sufficiently wide that it can be manufactured without phase shifting. A violation of condition (2) is corrected by layout modification that increases the spacing between critical features. Note that the "odd cycle" problem illustrated in Figure 4 can in general be interpreted as a violation of either condition 1 or condition 2 (!) - and hence can be corrected by increasing either feature width or feature spacing. It is necessary to minimize the total cost of the layout modifications applied:

4. Detailed Description of the Preferred Embodiment for Dark-Field Alternating Phase-shifting Mask Technology

The embodiment presentation is organized as follows. In the next subsection, we construct a phase conflict in which the Phase Assignment Problem is reduced to node bicoloring. Section 4.2 describe new methods of design modification which ensure bicolorability of the associated phase conflict graph. In Section 4.3 we reduce the Phase Assignment Problem to the Minimum Perturbation Problem in the phase conflict graph and to the T-join problem on the dual graph of the phase conflict graph. In Section 4.4, we present

¹ One cannot color the nodes of an odd cycle into two colors, such that all pairs of adjacent nodes receive different colors. new fast and practical algorithms for solving the -join problem. These algorithms are based on reduction of the T-jom problem to the Minimum- Weight Perfect Matching problem via gadgets. Section is devoted to several previously known and new approximation methods for solving the T-join problem.

4.1 Construction and Planar Embedding of the Conflict Graph

We now show how to construct a phase conflict graph corresponding to a given layout, such that the assignment of phases to features corresponds to the coloring of nodes of the phase conflict graph. We also describe a planar embedding the phase conflict graph. For a given layout of polygonal features, the phase conflict graph G = (V, E) is constructed by defining a node for each feature, and introducing an edge between two nodes exactly when the corresponding features are in phase conflict. The phase conflict graph can be constructed in 0(n log ή) time, where n is the total number of segments in all polygon boundaries. We implement the following construction. • Slice each feature (polygon) into rectangles by vertical cuts through all polygon nodes, maintaining a pointer from each rectangle to its containing polygon

• Bloat each rectangle by distance BI2.

• Using sweepline and interval tree, detect conflicts between polygons by finding overlapping pairs of rectangles that belong to different polygons.

Alternatively, one may detect intersections of bounding boxes of polygons, then check whether the corresponding polygons actually intersect.

In alternating PSM, we can remove all phase conflicts by assigning opposite phases to each pair of adjacent nodes in the phase conflict graph G. This is equivalent to 2- coloring the rules of G with phase 0 and phase 180. For this to be possible, G must be bipartite, i.e., have no odd cycles. Hence, if the phase conflict graph G is not bipartite, our goal is to delete enough edges such that no odd cycles exist in the remaining modified phase conflict graph. Edge deletion in the phase conflict graph is achieved by changing the placement of layout features so that they no longer conflict. Thus, with alternating PSM technology we see that manufacturability creates highly non-obvious, non-local constraints on the layout. Efficient algorithms that we give below for removing odd cycles depend on

² Although the slicing is not strictly necessary, it greatly simplifies the construction as well as the planar embedding of the phase conflict graph. In fact, if slicing were not be performed in advance, the phase conflict planarity of G. In general, the phase conflict graph computed as described above may contain non-planar local configurations like the one in Fig. 2(a). Diagonal conflicts effectively do not exist because of interference effects. Therefore, the deletion of intersecting diagonals from the phase conflict graph will not compromise the effectiveness of the resulting PSM.

Assume that (i) 2b > B and (ii) four rectangles which are pairwise (with the possible exception of one pair) in conflict do not have diagonal conflicts (see Figure 5(a)). Then, the phase conflict graph G is planar.

To fully exploit the planarity of the phase conflict graph once diagonals have been removed, the phase conflict graph should be embedded into the plane. Embedding is fully determined by the cyclic order of edges incident to each node, i.e., by the cyclic order of nodes adjacent to a given node. Note that the order induced by segments connecting the centers of adjacent rectangles may be incompatible with a planar embedding, e.g., if rectangles have large aspect ratio (see Figure 6(a)). We use the following cyclic order of adjacent rectangles (see Figure 6(b)). All rectangles adjacent to a given rectangle R are partitioned into four groups consisting of: (i) rectangles positioned to the right of R (i.e., having left side to the right of the right side of R); (ii) rectangles positioned below R which do not belong to group (i); (iii) rectangles positioned to the left of R which do not belong to group (ii); and (iv) rectangles positioned above R which do not belong to groups (i) and (iii). In the ordering, rectangles from group (i) precede those from group (ii) which in turn precede those from group (iii), which in turn precede those from group (iv). Inside their respective groups, the rectangles are sorted (i) in decreasing order of their -coordinates, (ii) in decreasing order of their x-coordinates, (iii) in increasing order of their -coordinates, and (iv) in increasing order of their x-coordinates. After the correct planar embedding is established all instances of Kύ, and K in which cause edge intersections can be detected, and their edge intersections removed, in a straightforward way.

4.2 Approaches to Removing Odd Cycles From the Phase Conflict Graph

We focus on the following "one-shot" approach (Figure 8). Initially, we constrain the layout only by the minimum-spacing design rule, i.e., no two features can be less than distance b apart. We then: (i) find the phase conflict graph G; (ii) find the minimum set of edges whose deletion makes the phase conflict graph G 2-colorable; (iii)

graph construction and sorting of neighbors would implicitly include some procedure equivalent (at least in assign phases such that only the conflict edges in the minimum set connect features of the same phase; and (iv) compact the layout with "PSM design rules", i.e., minimum separation B between features that are assigned the same phase, and mimmum separation b between features that are assigned different phases. Iterative coloring and compaction approach iteratively applies the following three steps until the phase conflict graph G becomes bipartite:

(i) compact the layout and find the phase conflict graph G;

(ii) find the minimum set of edges whose deletion makes the phase conflict graph G 2-colorable; and (iii) add a new constraint for each edge in this minimum set, such that the pair of features connected by this edge must be separated by distance at least B;

4.3 The Minimum Perturbation and J-Join Problems

The overall objective of PSM layout design is to achieve minimum-area layout while maintaining PSM-feasibility. Our "one-shot" flow assumes that an automated-custom or migration flow will essentially start out by being "optimistic", i.e., by assuming that feature widths and spacings can be scaled down to values achievable using PSM. The optimistic assumption will typically result in a design that: cannot be phase-assigned, due to the presence of odd cycles. This induces a "minimum perturbation" problem: we seek a "minimum perturbation" of the layout, in terms of odd cycle breaking and resultant B spacing constraints between pairs of features that previously had b spacings.

Recall that when a phase assignment is found, each conflict edge that separates two same-phase features induces a minimum spacing requirement of B between the features. Such a requirement is passed to compaction in the form of a spacing constraint. To fully exploit compaction technology and achieve optimal algorithms for phase assignment with minimum layout perturbation, we must take into account that different changes may have different impact on the resulting layout area.

The methods for optimal odd cycle removal that we develop below will find the minimum-weight set of conflict edges whose deletion makes the phase conflict graph bipartite, even if the conflict edges have different weights. Thus, as we minimize the number of layout changes (i.e., new spacing requirements in compaction), we believe that it will be helpful to assign larger weights to those conflict edges whose resolution will cause larger

runtime) to slicing. increase in the layout area. A specific recipe would detect spacing constraints (between feature pairs) that are on critical paths in the compaction, i.e., constraints that when increased will directly increase the size of the layout. It would be reasonable to assign larger weight to conflict edges corresponding to such constraints; lesser weight should be assigned to conflict edges that do not lie on critical paths (see Figure 9). Finally, if several methods to delete edges and eliminate odd cycles are combined, the cost of a given conflict edge should reflect the minimum possible cost of breaking that edge using any of the available methods. Finally, we assign costs to the phase conflict graph edges based on one or more of the following layout analysis results: values of slacks in the layout compaction graph, values of slacks and sensitivities in static timing and noise analysis, and values of critical area and yield sensitivities in manufacturability analyses.

Optimal phase assignment can be found by solving the following problem. The Minimum Perturbation Problem: Given a planar graph G - (V, E) with weighted (multiple) edges, find the minimum-weight edge set M such that the graph (V, E - M) contains no odd cycles.

After the Minimum Perturbation Problem is solved, i.e., the set of edges M is determined and deleted, the valid assignment of phases can be found using breadth-first search. For each connected component of the phase conflict graph (the weight of each edge is set to 1), starting from arbitrary node v breadth-first search determines the distance from v to each other node u. If the distance from v to u is even, then u is assigned the same phase as v; otherwise, u is assigned the opposite phase. Such breadth-first search can be performed in linear time.

The Minimum Perturbation Problem is closely related to the well-known T- join problem. The -join Problem: Given a graph G with weighted edges, and a subset of nodes T, \I\ is even, find a minimum weight edge set A such that a node u is incident to an odd number of edges of A iff u e T.

The Minimum Perturbation Problem can he reduced to the -join problem in the following way. We use the following definitions. A geometric dual of an embedded planar graph G = < V, E> is a multigraph D = <F, E> in which nodes are the faces of G. Iff g are two faces of G, i.e., two nodes of D, than an edge of G connects /with g if it belongs to both of them. A reduced dual of G is a graph D = < F, E > obtained from D by deleting all but one of the edges that connect a given pair of nodes. The undeleted edge must be the one of minimal weight. The Mimmum Perturbation Problem for a planar graph G is equivalent to the T-join problem in the reduced dual graph of G.

The T-join problem for a graph with n nodes was reduced by Hadlock and Orlova & Dorfrnan to the Minimum- Weight Perfect Matching Problem in a complete graph with |T| nodes.

The reduction defined above has two drawbacks. First the reduction itself can be slow, because finding all pairwise distances between nodes of Tis too time- and memory- consuming. Additionally the resulting instance of Minimum- Weight Perfect Matching Problem may have many more edges than necessary, and thus itself is too difficult to be used in practice.

4.4 Fast Optimal Algorithms for the T-join Problem

In this section we present new reductions of the T-join problem to the minimum weight perfect matching problem, which yield a fast optimal algorithm for the T- join Problem in phase conflict graphs (i.e., sparse graphs).

We start from simple reductions that allow to reduce the problem size in many practical instances, moreover they eliminate special cases that would complicate the description of gadgets that are used by the subsequent reduction. Next, we will show a gadget-based reduction that uses very simple gadgets and has simple correctness proof. This reduction yields an algorithm that solves an instance of T-join problem with m edges by applying a perfect matching algorithm to a graph with 0(m) edges. In this manner, we obtain an algorithm for the T-join problem that runs in time roughly 0(n^V2). Finally, we refine this idea to improve the size of the resulting instance of perfect matching (and consequently, the overall running time) by a constant factor. First we describe simplifying, opportunistic reductions that eliminate the nodes of degree 0, 1 and nodes of degree 2 that do not belong to T

The first opportunistic reduction reduces the T-join problem to instances with biconnected graphs. Consider an instance of the T-join problem described by the graph <V, E>, edge weight function w and fc . Assume that <V, E> has biconnected components < Vj, Ej>, ...,< V_k, Eu>. Then in linear time we can find sets T, c V_t such that A c E is an optimal T-join if and only if for i = 1,..., k, A n Ei is an optimal T-join for <Fi-, E₍-> w| The second opportunistic reduction eliminates nodes of degree 2 that do not belong to T. Assume that node v g Thas exactly two neighbors, vι and v₂. Consider the graph transformation where edges {v, vι} and {v, v₂} are replaced with edge {v_ls v₂} with weight w(v, v\) + w(v, v₂). Then this edge replacement defines a 1-1 correspondence between T-joins of the old graph and the new graph.

Reduction via simple gadgets.

We give the allowing algorithm for the T-join problem in sparse graphs.

1. Read T-join instance (V, E, w, T). 2. For each vertex v e create gadget graph Y_v that depends only on the degree of v and the membership of v in T. For every neighbor u of v, F_v contains a contact node (v, u), all edges of T_v have weight 0.

3. For each edge {u, v} e E connect T_Uι and T_u with a replacement of {u, v}, p{u, v}, - {(u, v), (v, u)}, that has the same weight. 4. In the resulting graph (V, E ' w ^*) find a minimum cost perfect matching M.

5. Return ,4 = p^l(M).

Fig. 11 shows an example of a transformation that uses our gadgets; the left part shows an instance of the T-join problem, and the middle part the instance of Perfect Matching that is obtained with the gadgets from Fig. 12.

Reducing T-join to Perfect Matching with Optimized Gadgets

Now we give optimized gadgets which improve the rumiing time by a factor of 4 on average. The construction of these gadgets is less uniform and the connection between the gadget is less regular. We define two versions of gadgets: full gadgets, shown in Fig. 13, and trimmed. The idea is that the full gadget of node u, denoted Y_u, contains replacements of all edges that are incident to w; when we connect gadgets of adjacent nodes u and v, we need to decide which replacements of the edge {u, v} we remove: those from T_u, or those from T_v? This removal creates the trimmed gadgets which are connected by identifying by respective contact nodes.

More formally, for every node v that is adjacent to u, the gadget T_u contains contact node (u, v). This contact node is incident to all replacements of the edge {u, v} that belong to T_u. The remaining nodes of T_u are the core nodes. We distinguish two kinds of contact nodes: obligatory and optional. All these kinds of nodes are illustrated in Fig. 13. The property of an optional contact is that it is incident to one edge only, and this edge connects this contact with a core node. We can trim r„ by removing some ofits optional contacts. For each contact

(u, v) thus removed we transfer the name (u, v) to its sole neighbor. Now we see that we cannot connect the gadgets arbitrarily (as we did in the previous algorithm). In particular, we can connect T_u and Y_v only if one of the respective contacts, (u, v) or (v, u), is optional. Suppose that (u, v) is optional. Then we can connect Y_tl and T_v by trimming (u, v), and identifying the new (u, v) with (v, u). As a result, all replacements of edge {u, v} are adjacent to a single core node of T_u; we say that edge {u, v} fans out from it toward v. Now we can describe the new algorithm.

1. Read instance (V, E, w, T) of T-join problem.

2. For each edge {u, v} e E, decide whether it fans out toward u or toward v. Make sure that if a node w has degree d, then at least [d/2] edges are fanned toward w.

3. For each node u e V create gadget T_u that depends on the degree of u and the membership of u in T For each v adjacent to u T_u contains contact node (u, v). Make sure that if {u, v} fans toward u then (u, v) is optional. 4. For each edge {u, v} e E connect T_u, and T_v. In particular, if {u, v} e

E fans out toward v, then remove the optional contact (u, v) (and the replacement of {u, v} in Γ_M) and identify the new (u, v) with (v, u).

5. In the resulting graph (V, E', > ') find a minimum cost perfect matching M. 6. Return A, the set of edges of E that have a replacement in M.

We should note that its step (2) can be implemented in linear time. We apply a graph traversal, where each edge is traversed exactly once, and when we traverse an edge, say from u to v, then we decide to fan it out toward v. If there exists a node adjacent to an odd number of un-traversed edges, we start the next stage of the traversal there, and we continue until we encounter another node with this property. When every node is adjacent to an even number of untraversed edges, we can start at any node adjacent to an untraversed edge and continue until we return to this node. It is easy to see that each time we traverse through a node, or when we start and end a traversal in the same node, we fan out one edge toward this node, and one edge away. At most once an edge can he used as a terminal of a non-cyclic traversal, thus we fan at least [d/2] edges toward a node of degree d.

To construct other gadgets, we will introduce some terminology. We use Ti to denote a gadget for a T-node of degree i, and Sz to denote a gadget for a (V- 2)-node of degree i. The reduced forms of our gadgets, namely, of S3, 23, S4 and Q (a version of S4), are cliques, so these gadgets are proven correct. Larger gadgets are defined inductively.

Given two gadgets H and H', we can meld them as follows. Let x be* an optional contact of H and x ' be an optional contact of H'. Let v and v ' be the core nodes adjacent to x and x '. Then meld (H, H') is created by discarding x and x ' and by identifying y with v'. Fig. 13 shows many examples of melding. For i > 1 we define St as meld(S(i - 2), Q) and Ti as meld(T(i - 2), Q). The following lemma validates building larger gadgets by melding the smaller ones.

We will say that a graph is a gadget if it has a distinguished set of core nodes, and every superset of the core nodes of even size has a perfect matching. An S gadget has an even number of core nodes, and a T gadget has an odd number. An i gadget has i non-core nodes.

We build new gadgets in the following three ways:

(i) If Η is an St gadget, and H' is an Sj, then meld(H, W) is a T(i +j - 2).

(ii) If Η is a Ti gadget, and Η' is a Tj, then meld(H, W) is a T(i +j - 2). (iii) If Η is an St gadget, and Η' is a Tj, then meld (H, H j is a S(i +j - 2).

Consider an instance of Minimum Cost T-join problem with n nodes, m edges, no T nodes of odd degree and m nodes of T that have degree 3. Our algorithm solves this instance by generating an equivalent instance of the Minimum Cost Perfect Matching that has at most 2m - n + no nodes and at most 6m — 5.5« + 0.5n_\ edges. Finally we can apply the best known so far algorithm by Gabow and Tarjan to solve the perfect matching problem.

4.5 Approximation Algorithms for the T-join Problem

The exact algorithm from the previous section may still be too slow for processing very large layouts.

We give a fast heuristic based on the Noronoi graph paradigm. Iterated Voronoi Algorithm:

1. Partition all nodes in G into the Voronoi regions of the nodes in T such that:

(i) each Voronoi region contains exactly one node from T, which is the center of the Voronoi region, and

(ii) each even-degree node belongs to the Voronoi region that contains the closest node in T (break ties arbitrarily).

2. Construct the Voronoi graph V or (G) in which each node represents a Voronoi region, and two nodes R_\ and R₂ are adjacent if and only if a shortest weighted path in G between the corresponding region centers is completely contained in the two regions (see Fig. 14).

3. Find a minimum-weight maximum matching M in V or (G).

4. Find the edge set VMin G that is the union of paths in G corresponding to edges of M, which in turn correspond to the edges of the minimum weighted matching in V or (G).

5. Delete edges VM from the phase conflict graph G,

6. Repeat previous steps while T≠J.

BRIEF DESCRIPTION OF THE DRAWINGS Figure 1 is a diagram comparing the diffraction optics of conventional and phase-shifting masks where E denotes electric field and I denotes intensity: Fig. 1(a) depicts the conventional mask light diffracted by two adjacent apertures constructively interferes, increasing the light intensity in the dark area of the wafer between the apertures. Fig. 1(b) depicts the phase-shifting mask, the phase shifter reverses the sign of the electric field, and destructive interference minimizes light intensity at the wafer in the dark area between apertures.

Figure 2 is a block diagram depicting AltPSM style of Wang and Pati (Numerical Technologies, Inc.) The critical portion of the feature is created with an AltPSM mask; the second binary mask protects the critical portion and defines the non-critical portions of the feature.

Figure 3 is a schematic diagram illustrating in Fig. 3(a) that when two vertical critical features (black rectangles) are closely spaced, their phase shifters overlap and must be assigned the same phase and in Fig. 3(b) that when the features are widely spaced, their phase shifters can be assigned phases independently. Figure 4 is a diagram depicting two small layouts with 4 features each that illustrate the "odd cycle" problem of phase mask layout. There is no assignment of 0 and 180 phases to the shifters, such that in Fig. 4(a) there are opposite-phase shifters on either side of each feature, and in Fig. 4(b) any shifters that overlap are assigned the same phase.

Figure 5 (a) is a diagram illustrating the assumption that there are no conflicts between diagonal pairs (dashed edges) in a set of four features if at least three other conflicts exist. Figure 5 (b) is a diagram showing how to draw edges of the conflict graph without edge intersection. Figure 5 (c) is a diagram showing that that there is no conflict between the left T-feature and the right T-feature because B<=2b.

Figure 6(a) is a block diagram showing that the order induced by the segments connecting the centers of adjacent rectangles is not planar. Figure 6(b) is a diagram showing how to obtain a correct cyclic order on edges incident to a given node.

Figure 7 is a plan view showing that changing the shape of interconnections can reduce the number of conflicts between features without changing positions of vias.

Figure 8 is a flow chart showing the flow for the "one-shot" method. Note that the one-shot approach applies compaction separately in the x- and v-directions to enforce the given phase assignment.

Figure 9 is a diagram showing rectangular features and spacing constraints between them represented as arcs. The critical (longest) path between leftmost and rightmost features consists of thick edges. Any conflict on the critical path cannot be relaxed without widening the layout. Thin edges are on non-critical paths and they may be broken for free.

Figure 10 is a diagram that schematically shows how to find minimum number of conflicts to be deleted (black conflicts on Fig. 10(f)) from the set of all conflicts (dark conflicts on Fig. 10(a)). From the conflicts between features Fig. 10(a), the conflict graph is derived as depicted in Fig. 10(b). The dual graph depicted in Fig. 10(c) is constructed. The nodes of odd degree are matched using T-join in the dual graph is depicted in Fig. 10(d), and the corresponding conflict edges are determined as depicted in Fig. 10(e). Finally, the minimum set of conflicts to be deleted is determined as depicted in Fig. 10(f). Fig. 11 is a diagram showing an example of a transformation that uses gadgets; the left part shows an instance of the T-join problem, and the middle part the instance of Perfect Matching that is obtained with the gadgets from Fig. 12.

Fig. 12 is a diagram depicting T-join instances and gadgets used for transformations. Fig. 13 is a diagram depicting an improved set of gadgets. For the basic gadget the non-zero edge weights are shown explicitly. Empty dots depict the core nodes and full dots indicate the contacts. Larger full dots indicate obligatory contacts, smaller dots indicate optional contacts. Fig. 14 is a diagram depicting the geometric dual graph G and Voronoi graph for T. The weight of an edge in Vor( G) is the total cost of edges in the shortest path (dashed edges) between the centers of the Voronoi regions (black vertices).

Figure 15 is the feature graph for a layout with four critical features. The four feature nodes are lage and filled, the four contact nodes are small and filled, and the five shifter nodes are large and empty.

Fig. 16 is a diagram depicting two cases of self-intersection of the feature graph. In both cases the shifter width is more than half of the feature length.

DESCRIPTION OF THE SPECIFIC EMBODIMENTS The embodiment presentation is organized as follows. We first give construction and planar embedding of the feature graph which is the bright-field analogue of the phase conflict graph. Next the exact and approximation algorithms for bipartizing the feature graph are given.

5.1 The Feature Graph

In this section, we propose a new feature graph to represent relationships between adjacent layout features and their corresponding shifters. The feature graph allows us to reduce the Phase Assignment Problem to graph bicoloring. Furthermore, the structure of the feature graph allows both types of layout modifications (feature width increase, and feature spacing increase) to be applied, along with recent advanced discrete algorithmic methods.

The Minimum Distortion Problem asks to minimize the cost of correcting all violations of conditions (l)-(2), since each violation results in increasing area or slowing down the chip. We will model the layout modification used to correct violations of condition (1) as deletion of a node corresponding to the critical feature. Layout modification used to correct violations of condition (2) will correspond to either edge or node deletion. Both edge and node deletion help to eliminate odd cycles. Following is the formal description for now to construct the feature graph. Given a layout, the feature graph G = (F C J S, E) consists of the three types of nodes F, C and S and edges E:

(F) For each critical feature/* we put into correspondence a feature node/ e E; (C) For each overlap of two shifters we put into correspondence a conflict node c e F; (Ε) Any feature node/is connected to all conflict nodes representing overlaps of the shifters which are on the sides of the corresponding feature/*; (S) Edges between feature node/and conflict nodes of one of its shifters

(arbitrarily chosen) are subdivided into paths of length 2 by shifter nodes s e S. Note that all conflict and shifter nodes have degree 2, and only feature nodes may have arbitrary degree. Figure 15 shows the feature graph for a layout with four critical features.

The useful properties of the feature graph are justified as follows. Let G be the feature graph of the layout L. Then

(i) the Phase Assignment Problem has a feasible solution for L if and only if G is 2-colorable (i.e., G is bipartite); (ii) increasing the width of a feature/* in L is equivalent to deleting the corresponding feature node/from G; (iii) increasing the spacing between two features in L that have overlapping shifters is equivalent to deleting the corresponding conflict node c from G or deleting any of the edges (f, c), if, s) or (c, s), where/corresponds to either of the two features and s is the shifter node that possibly subdivides the/to-c connection. We also may supply nodes and edges of the feature graph G with costs reflecting the relative costs of the spacing enforcement and the critical feature widening layout perturbations. Formally, we assign costs to the feature graph edges based on one or more of the following layout analysis results: values of slacks in the layout compaction graph, values of slacks and sensitivities in static timing and noise analysis, and values of critical area and yield sensitivities in manufacturability analyses. Therefore, the Minimum Distortion Problem is equivalent to the following: Graph Bipartization Problem. Given an edge and node weighted graph G, find the minimum weight edge or node set D, such that the graph G — D is bipartite. Planar embedding of feature graph.

The feature graph is planar if the maximum width of a shifter is less than half the minimum length of a feature (see Fig. 16).

The embedding of the feature graph G = (F GoS, E) into the plane consists of the following steps:

1. For any feature/*, the corresponding feature node/ e F is placed at the geometric center of the corresponding feature rectangle. 2. For every pair of overlapping shifters, the corresponding conflict node c e C is placed at the geometric center of the overlapping area of the shifters.

3. We connect with straight lines each feature node/ e F to the conflict nodes representing overlaps of the shifters which are on the sides of the corresponding feature f* according to step (E) of the definition of the feature graph; is necessary, we subdivide this line with the shifter node s e S according to step (S).

5.2 Algorithms for Bipartization of Planar Graphs

We give two alternatives for bipartizing planar graphs. The first algorithm has been described in the dark-field embodiment and is the fast optimal algorithm for edge- deletion bipartization.

If the both modifications (edge- and node- deletion) are allowed then the problem is computationally very difficult. Below we describe the best know approximation algorithm due to Goemans and Williamson (see "Primal— Dual Approximation Algorithms for Feedback Problems in Planar Graphs", M.X. Goemans and D.P. Williamson, Combinatorica 18 (1998), pp. 37-59; pages 37-59 are hereby incorporated by reference for all purposes). It is provably good, i.e., it guarantees 9/4 approximation. Primal-Dual Algorithm (Goemans- Williamson) Given: Planar graph G Output: The bipartite subgraph H For each odd face/of G, initialize age(f) = 0

While there are odd faces in the graph G do

For each odd face/of G, increment age(f) = age(f) + 1. For each node v in the graph G set weight (v) to the sum of ages of all odd faces with the node v on the boundary.

Delete the node v with the largest weight. If a new face/is odd, then initialize age(f) = 0. In the reverse order of deletions do

Add node v with all adjacent edges to the graph If an odd face appears, then delete v from the graph G The best choice is to run the both algorithms and pick the best result.

Claims

WHAT IS CLAIMED IS: 1. A method of removing phase conflict in an arbitrary starting layout of a dark-field alternating phase-shifting mask, to obtain a properly phase-assignable final layout, such method comprising the steps of: 1. computing a planar phase conflict graph for a starting layout (i) representing phase-assignability of a dark-field alternating phase-shifting mask; (ii) distinguishing between relative costs of different modifications to mask apertures; 2. computing, using a fast, gadget-based algorithm, the minimum- cost set of phase conflicts in the phase conflict graph whose removal will enable the final layout to have a proper phase assignment; 3. assigning, based on the result of step (2), proper phases to each aperture of the dark-field alternating phase-shifting mask; 4. generating connectivity and spacing constraints for layout compaction according to the phase assignment of step (3); 5. compacting the starting layout into a properly phase-assignable layout according to the generated constraints.

2. The method of claim 1 , where such step of computing the planar phase conflict graph further comprises the steps of: 1. slicing each layout polygon into rectangles by horizontal or vertical cuts through polygon vertices, and maintaining a pointer from each rectangle to its containing polygon; 2. bloating each rectangle by a distance that is dependent upon the optical lithography equipment used with the phase-shifting mask, and equal to half the minimum allowed spacing between two same-phase apertures; 3. detecting conflicts between polygons by finding overlapping pairs of rectangles that belong to different polygons; 4. assigning costs to the phase conflict graph edges.

3. A method of removing phase conflict in an arbitrary starting layout of a bright-field alternating phase-shifting mask, to obtain a properly phase-assignable final layout, such method comprising the steps of:

1. computing a planar feature graph a layout (i) representing phase-assignability of a bright-field alternating phase-shifting mask: (ii) distinguishing between two types of resolving phase conflicts (i.e., modifications to mask apertures), namely, increasing spacing between two critical features and increasing the width of a critical feature; (iii) distinguishing between relative costs of different modifications to mask apertures; 2. computing, using a fast, gadget-based algorithm, the minimum- cost set of edges in the feature graph whose removal makes the graph bipartite and hence will enable the final layout to have a proper phase assignment; 3. assigning, based on the result of step (2), proper phases to each aperture of the bright-field alternating phase-shifting mask; 4. generating connectivity and spacing constraints for layout compaction according to the phase assignment of step (3); 5. compacting the starting layout into a properly phase-assignable layout according to the generated constraints.

4. The method of claim 3 , where such step of computing the planar feature graph further comprises the steps of: 1. placing, for any feature f*, the corresponding feature node f at the geometric center of the corresponding feature rectangle; 2. placing, for every pair of overlapping phase shifters, the corresponding conflict node c at the geometric center of the overlapping area of the shifters; 3. connecting with straight lines each feature node f to the conflict nodes representing overlaps between the shifters on the sides of the corresponding feature f* and other shifters; 4. subdividing each edge between a feature node f and the conflict nodes of one of its shifters into two edges by introduction of a shifter node s; 5. assigning costs to the feature graph vertices and edges.

5. A method of removing phase conflict in an arbitrary starting layout of a bright-field alternating phase-shifting mask, to obtain a properly phase-assignable final layout, such method comprising the steps of:

1. computing a planar feature graph for a layout (i) representing phase-assignability of a bright-field alternating phase-shifting mask; (ii) distinguishing between two types of resolving phase conflicts (i.e., modifications to mask apertures), namely, increasing spacing between two critical features and increasing the width of a critical feature; (iii) distinguishing between relative costs of different modifications to mask apertures; 2. computing, using heuristics that include but are not limited to the node-deletion bipartization heuristic of Goemans and Williamson, a set of nodes in the feature graph whose removal makes the graph bipartite and hence will enable the final layout to have a proper phase assignment; 3. assigning, based on the result of step (2), proper phases to each aperture of the bright-field alternating phase-shifting mask; 4. generating connectivity and spacing constraints for layout compaction according to the phase assignment of step (3); 5. compacting the starting layout into a properly phase-assignable layout according to the generated constraints.

6. The method of claim 5, where such step of computing the planar feature graph further comprises the steps of: 1. placing, for any feature f*, the corresponding feature node f at the geometric center of the corresponding feature rectangle; 2. placing, for every pair of overlapping phase shifters, the corresponding conflict node c at the geometric center of the overlapping area of the shifters; 3. connecting with straight lines each feature node fto the conflict nodes representing overlaps between the shifters on the sides of the corresponding feature f* and other shifters; 4. subdividing each edge between a feature node f and the conflict nodes of one of its shifters into two edges by introduction of a shifter node s; 5. assigning costs to the feature graph vertices and edges.