Cut Redistribution with Directed-Self-Assembly Templates for Advanced 1-D Gridded Layouts
Journal
IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
Journal Volume
36
Journal Issue
12
Pages
2066-2079
Date Issued
2017
Author(s)
Lin, Z.-W.
Abstract
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.
Type
journal article