Methods For Layout Decomposition For Double Patterning Lithography

Technology Description

The subject invention employs two methods for layout decomposition for double patterning lithography (DPL) based on integer linear programming (ILP) formulations. In an exemplary embodiment of the invention, a pre-processing step fractures polygonal layout features into rectangles according to vertex coordinates of neighboring features. The fractured rectangular features are further split by a node-splitting process that resolves coloring conflicts and enlarges the solution space for DPL coloring. Then the coloring of the rectangles is optimized with a process-aware cost function that avoids small jogging line-ends and maximizes overlap at dividing points of polygons. The cost function may also be revised to make preferential splits at landing pads, junctions, and long runs. A layout partitioning heuristic helps achieve scalability for large layouts. There are two different layout decomposition approaches possible in the invention.

The first approach (referred to as Conflict Cycle Detection, or CCD) performs conflict cycle detection to find and report coloring conflicts (i.e., design changes such as layout modifications are needed) then finds the coloring solution on the remaining features using an ILP formulation.

The second approach (referred to as Pure ILP or PILP) directly computes the coloring solution on the rectangles after polygon splitting, along with the minimum number of necessary layout modifications, using a more sophisticated ILP formulation.

An exemplary objective for the DPL layout decomposition methods is to optimize a weighted combination including number of design changes, number of line-ends, number of design rule violations, and the overlap lengths between touching features with different colors.

State Of Development

Working software prototype is available.

Related Materials

Additional information can be found at IEEE paper.

Patent Status