Patent ID: 7496883
Filing Date: 2009-02-24
Classification: G03F

Abstract:
1. A method for determining a set of phase conflicts in a PSM-layout, wherein correcting the set of phase conflicts makes the PSM-layout phase-assignable, the method comprising: constructing a phase-conflict graph from a PSM-layout such that the PSM-layout is phase-assignable if and only if the phase-conflict graph is bipartite, by: creating a node in the phase-conflict graph for a shifter in the PSM-layout, creating a conflict-edge between a first node and a second node, wherein the first node and the second node correspond to a pair of adjacent shifters that need to have different phase shifts, creating an edge between a third node and a fourth node, wherein the third node and the fourth node correspond to a pair of overlapping shifters that need to have the same phase shift, creating an overlap-node that subdivides the edge into two overlap-edges: a first overlap-edge between the third node and the overlap-node and a second overlap-edge between the overlap-node and the fourth node, and wherein an overlap-edge is assigned a weight a. W+b. (1/F), where W is the minimum amount of space that needs to be added between the pair of overlapping shifters associated with the overlap-edge so that they can have different phase shifts, F is the number of phase conflicts that are corrected when space is added between the pair of overlapping shifters, and a, b are weighting factors; removing a first set of edges from the phase-conflict graph to create a planar sub-graph; removing a second set of edges from the planar sub-graph to create a bipartite sub-graph, wherein each edge in the second set of edges is associated with the phase-conflict graph in the PSM-layout; adding zero or more edges of the first set of edges to the bipartite sub-graph, such that none of the added edges creates an odd cycle in the bipartite sub-graph; and determining a set of phase conflicts in the PSM-layout associated with the remaining edges in the first set of edges and the second set of edges; wherein first making the phase-conflict graph planar and then making it bipartite allows the method to determine a substantially minimal set of phase conflicts, which reduces the number of corrections required to make the PSM-layout phase-assignable.