Simultaneous layout migration and decomposition for double patterning technology

Double patterning technology (DPT) and layout migration are two closely related problems on design for manufacturability in the nanometer era. DPT decomposes a layout into two masks and applies double exposure patterning to increase the pitch size and thus printability. In this paper, we present the first algorithm in the literature for the simultaneous layout migration and decomposition (SMD) problem. Our algorithm first constructs a conflict graph and DPT-aware constraint graphs, and then applies integer linear programming (ILP) corresponding to the graphs to obtain a decomposed and migrated layout. We further present an effective graph-based reduction technique to prune the ILP solution space, which maintains the same DPT conflicts. We also present a new DPT-aware objective for the SMD problem to minimize the difference between the original and migrated layouts while considering the DPT effects. In addition, we present an approach to generate DPT-aware standard cells by considering the DPT effects on the cell boundaries; this technique improves the layout printability and facilitates EDA tools to consider DPT. Experimental results show that our algorithms can effectively generate conflict-free migrated layouts with 14% smaller layout areas and 28% smaller layout changes, compared with the traditional method of layout decomposition followed by layout migration. In particular, our reduction technique can reduce the runtimes for the test cases from more than one day for the basic ILP formulation to only seconds. can reduce the runtimes for the test cases from more than one day to only seconds.