LRSDP: Low-Rank SDP for Triple Patterning Lithography Layout Decomposition

Multiple patterning lithography (MPL) has been widely adopted in advanced technology nodes to enhance lithography resolution. As layout decomposition for triple patterning lithography (TPL) and beyond is NP-hard, existing approaches formulate mathematical programming problems and leverage general-purpose solvers such as integer linear programming (ILP) and semidefinite programming (SDP) to trade off quality against runtime. With the aggressive increase in design complexity, existing approaches can no longer scale to solve complicated designs with high solution quality. In this paper, we propose a dedicated low-rank SDP algorithm for MPL decomposition with augmented Lagrangian relaxation and Riemannian optimization. Experimental results demonstrate that our method is 186×, 25×, and 12× faster than the state-of-the-art decomposition approaches with highly competitive solution quality.