Non-stitch triple patterning-aware routing based on conflict graph pre-coloring

Considering decomposition constraints earlier during routing becomes critical for realizing triple patterning lithography. In addition, stitches typically cause significant yield loss because of the overlay errors among different masks. As a result, leading foundries even get rid of the use of stitches in their design methodology. In order to completely avoid stitch-induced yield loss, we address the non-stitch triple patterning-aware routing problem. We observe that directly extending a state-of-the-art triple patterning-aware routing work to non-stitch routing might generate improper self-crossing nets and degrade routing quality due to sequential coloring for mask selection. To resolve these problems, we propose a new graph model to prevent self-crossing nets during routing and use a weighted conflict graph to globally consider net coloring. We then propose the first non-stitch triple patterning-aware routing scheme, which consists of two main stages: (1) conflict graph pre-coloring followed by (2) pre-coloring-based non-stitch routing. Experimental results show the effectiveness and efficiency of our routing scheme.