Electron beam lithography (EBL) has been used for high-resolution photomask fabrication; its successive heating process in a certain region, however, may cause critical dimension (CD) distortion. As a result, subfield scheduling, which reorders a sequence of subfields in the writing process, is desirable to avoid the heating problem and thus CD distortion. To consider longer range heat dissipation, this paper models a subfield scheduling problem with blocked region consideration as a constrained max–min$m$-neighbor traveling salesman problem (called constrained$m$-nTSP). To solve the constrained$m$-nTSP which is NP-complete in general, we decompose a constrained$m$-nTSP into subproblems conforming to a special case with points on two parallel lines, solve each of them with a provably good linear-time approximation algorithm, and merge them into a complete scheduling solution. In particular, our algorithm can also minimize the distances between successive subfields to alleviate the throughput degradation of EBL writing due to moving a writing head, while minimizing the heating problem. Average reductions of 10% in the maximum temperature and 14% in the distances between successive subfields over the state-of-the-art work can be achieved.

Two-dimensional directed self-assembly (2D-DSA), a promising nanotechnology, manipulates the orientation of double posts to guide block copolymers to fabricate 2D patterns in nanoscale. In this paper, we present the first detailed placement algorithm for 2D-DSA. We first propose an orientation-number model for nets to estimate post orientations. Then, a cost model based on the orientation numbers is defined to estimate the 2D-DSA routability efficiently during placement, and a novel detailed placement framework is proposed to consider the orientationsto optimize wirelength. In this framework, we develop a dynamic-programming-based algorithm for single-row detailed placement with a specialized pruning technique based on the defined orientation cost. Experimental results show that our algorithm can effectively generate a 2D-DSA friendly placement solution.

Directed-self-assembly (DSA) technology is a promising candidate for cut printing in sub-10nm 1-D gridded designs, where cuts might need to be redistributed such that they could be patterned by DSA guiding templates. In this paper, we first propose a linear-time optimal dynamic-programming-based algorithm for a special case of the template guided cut redistribution problem, where there is at most one dummy wire segment on a track. We then extend our algorithm to general cases by applying a bipartite matching algorithm to decompose a general problem to a set of subproblems conforming to the special case (thus each of them can be solved optimally). Our resulting algorithm can achieve a provably good performance bound, with the cost of a template distribution only linearly to the problem size. Experimental results show that our algorithm can resolve all spacing rule violations, with smaller running times, compared with the previous works on a set of common benchmarks. In addition, we also extend our algorithm to consider general design rules, simple templates, and dummy cuts.

Directed self-assembly (DSA) technology is a promising candidate for cut printing in sub-10nm 1-D gridded designs, where cuts might need to be redistributed such that they could be patterned by DSA guiding templates. In this paper, we first propose a linear-time optimal dynamic-programming-based algorithm for a special case of the template guided cut redistribution problem, where there is at most one dummy wire segment on a track. We then extend our algorithm to general cases by applying a bipartite matching algorithm to decompose a general problem to a set of subproblems conforming to the special case (thus each of them can be solved optimally). Our resulting algorithm can achieve a provably good performance bound, with the cost of a template distribution only linearly to the problem size. Experimental results show that our algorithm can resolve all spacing rule violations, with smaller running times, compared with the previous works on a set of common benchmarks.

Directed self-assembly (DSA) technology has emerged as a promising candidate for cut printing in advanced 1-D gridded layouts, where cuts might need to be redistributed such that they can be patterned by specific DSA guiding templates. The cut redistribution significantly affects the performance and manufacturability of a circuit. In this paper, we propose an algorithm incorporating DSA with double patterning for a template guided cut redistribution problem. We first develop a linear-time optimal algorithm for a special case of the template guided cut redistribution problem, with contiguous rows. For the general problem, a linear-time double-patterning aware partitioning method is developed to select a set of subproblem candidates to generate a template distribution to minimize the impact on circuit performance and manufacturing. Consequently, we decompose a general problem into a set of subproblems conforming to the aforementioned special case, solve each subproblem optimally, and merge the solutions to the subproblems to obtain an overall solution to the general one. Experimental results show that our algorithm can resolve all spacing rule violations, with even smaller extended wire costs and running times, compared with the state-of-the-art works on a set of common benchmarks.

Electron beam lithography (EBL) has been used for high-resolution photomask fabrication; its successive heating process in a certain region, however, may cause critical dimension (CD) distortion. As a result, subfield scheduling which reorders a sequence of subfields in the writing process is desirable to avoid the heating problem and thus CD distortion. To consider longer-range heat dissipation, this paper models a subfield scheduling problem with blocked region consideration as a constrained max-min m-neighbor travelling salesman problem (called constrained m-nTSP). To solve the constrained m-nTSP which is NP-complete in general, we decompose a constrained m-nTSP into subproblems conforming to a special case with points on two parallel lines, solve each of them with a provably good linear-time approximation algorithm, and merge them into a complete scheduling solution. In particular, our algorithm can also minimize the distances between successive subfields to alleviate the throughput degradation of EBL writing due to moving a writing head, while minimizing the heating problem. Average reductions of 10% in the maximum temperature and 14% in the distances between successive subfields over the state-of-the-art work can be achieved.