Fixing Double Patterning violations with look-ahead

Double Patterning Technology (DPT) conflicts express themselves as odd cycles of spacing between layout shapes. One way of resolving these is by imposing a large spacing constraint between a pair of shapes participant in an odd cycle. However, this may shrink spacing in other parts of the layout and introduce DRC violations or new DPT conflicts. In this work, we model DPT conflict resolution as a constrained linear optimization problem, look ahead to upfront estimate potential violations and preclude them with additional constraints. We borrow the approach of Satisfiability Modulo Theory (SMT) solvers to simultaneously check satisfiability of linear constraint set and resolution of DPT conflicts. These two are interleaved and feed information to each other to churn out a feasible set of constraints that fixes DPT and DRC violations. We demonstrate the efficacy of the method on layouts at advanced nodes.