Graph- and ILP-Based Cut Redistribution for Two-Dimensional Directed Self-Assembly

Two-dimensional (2D) directed self-assembly (DSA) is a promising technology for sub-5nm process, which forms patterns through combinations of oriented double posts. In 2D DSA, line-end cuts are employed to fabricate 2D patterns to derive desired layouts, and cut redistribution is applied to eliminate cut spacing violations. In this paper, we present the first work to handle the 2D DSA cut redistribution problem. We first solve this problem by basic integer linear programming (ILP) with solution optimality guarantees. We then propose an efficient graph-based optimality-preserving framework to handle this problem, where the spacing violations between template candidates are evaluated in linear time. This framework simplifies the cut redistribution problem with a lower-complexity binary ILP, where the numbers of variables and constraints can be reduced from quadratic to only linear. Experimental results show that our algorithm can effectively and efficiently redistribute cuts with zero spacing violations and the minimum wire extensions.