Triple patterning lithography-aware detailed routing ensuring via layer decomposability

摘要

For sub-10 nanometer technology nodes, multiple patterning technologies are still the major solutions for pushing the limit of lithography due to the delay of next generation lithography technologies. In this paper, we propose a triple patterning lithography (TPL)-aware router that guarantees the layout decomposability of via layers, which are the layers particularly requiring TPL for fabrication. In the research, the router does not perform simultaneous routing and coloring such that routing flexibility can be maximized. To guarantee layout decomposability, we show that considering K4 avoidance in the conflict graph alone is not sufficient. We therefore adopt the idea of graph isomorphism and construct a 3-uncolorable graph library in our routing flow. To tackle the high complexity of the graph isomorphism algorithm, we use several graph reduction techniques and propose a via plane division method to minimize runtime overhead. Finally, an optimal integer linear programming (ILP)-based layout decomposition algorithm is used to verify that layout decomposability is ensured by our router. Experimental results show the necessity and effectiveness of our router.