Post-routing layer assignment for double patterning with timing critical paths consideration

Double patterning lithography is promising for 32 nm technology and beyond. In this technique, one-layer layout is decomposed into two masks. Much work has been proposed to solve feature decomposition problem. However, post-routing layer assignment, which determines the layout features on each layer, thus having great impact on double patterning related parameters, has not been explored in the merit of double patterning. In this paper, we formulate post-routing layer assignment for double patterning problem for the first time. Both this problem and traditional single layer double patterning problem are proved to be NP-complete. An effective algorithm is further proposed to solve it. The algorithm consists of three major phases: multi-layer assignment to minimize double patterning risks, single layer double patterning, and via reduction. Since blind post-routing layer assignment may jeopardize timing critical paths obtained in the routing stage, our algorithm also considers total wire length and coupling capacitance on critical paths as timing metrics. Experimental results on Collaborative Benchmarking Laboratory benchmarks demonstrate the effectiveness of our algorithm. In comparison with single layer double patterning, our method achieves 62% and 11% average reduction on unresolvable conflicts and stitches, respectively, with only 0.30% increase of via number in layouts. Furthermore, the via height and parallel wire length on critical paths are decreased by 8% and 14% on average.