WISDOM: Wire spreading enhanced decomposition of masks in Double Patterning Lithography

In Double Patterning Lithography (DPL), conflict and stitch minimization are two main challenges. Post-routing mask decomposition algorithms may not be enough to achieve high quality solution for DPL-unfriendly designs, due to complex metal patterns. In this paper, we propose an efficient framework of WISDOM to perform wire spreading and mask assignment simultaneously for enhanced decomposability. A set of Wire Spreading Candidates (WSC) are identified to eliminate coloring constraints or create additional splitting locations. Based on these candidates, an Integer Linear Programming (ILP) formulation is proposed to simultaneously minimize the number of conflicts and stitches, while introducing as less layout perturbation as possible. To improve scalability, we further propose three acceleration techniques without loss of solution quality: odd-cycle union optimization, coloring-independent group computing, and suboptimal solution pruning. The experimental results show that, compared to a post-routing mask decomposition method, we are able to reduce the number of conflicts and stitches by 41% and 23% respectively, with only 0.43% wire length increase. Moreover, with proposed acceleration methods, we achieve 9× speed-up.