MAED: Mask assignment encoder decoder solver for multiple patterning layout decomposition

Multiple patterning layout decomposition (MPLD) plays a vital role in multiple patterning lithography (MPL) which assigns features in a layout into multiple physical masks. Existing methods, such as integer linear programming (ILP), manually design sophisticated formulations which can find the optimal solutions but exhibit decreased runtime performance for dense layouts. Besides, the need for problem specific designs cannot guarantee the trivial extension to other conditions. Regarding the issues above, in this paper, we revisit the objective of MPLD and design a general-purpose formulation for learning methods that is broadly applicable to layout decomposition problems. Moreover, a graph learning framework — MAED is introduced to solve the proposed formulation. Through minimizing the carefully designed differentiable objective, MAED can be trained unsupervised purely on small scale layouts and applied quickly to arbitrarily large ones via message passing mechanism. Combined with the greedy based color refinement hammer, we further improve the local quality of solutions. Experimental results reveal that our method can achieve more than 100x speedup compared to ILP and displays better quality-speed trade-offs compared with other approximation solvers.