A Matching Based Decomposer for Double Patterning Lithography

摘要

Double Patterning Lithography (DPL) is one of the few hopeful candidate solutions for the lithography for CMOS process beyond 45nm. DPL assigns the patterns less than a certain distance from each other on each layer onto two masks instead of one mask in traditional lithography. In this paper, we prove that the conflict graph used to model DPL conflicts in layout is a planar graph. Based on the planarity, we propose a new face merging based framework which formulates DPL decomposition as a problem of pairing odd faces to simultaneously minimize the number of stitches generated and conflicts to eliminate. We employ partitioning and simplification techniques to reduce the problem size and use an O(n~3) time maximum weighted matching algorithm to generate an optimal DPL decomposition.