Optimally minimizing overlay violation in self-aligned double patterning decomposition for row-based standard cell layout in polynomial time

摘要: Self-aligned double patterning is one of the most promising techniques for sub-20nm nodes. As in any multiple techniques, layout decomposition important problem. In SADP decomposition, overlay among primary concerns. Most existing works target at minimizing overall overlay, while others totally forbid overlay. On other hand, either rely on exponential time methods, or apply heuristic that cannot guarantee to find a solution. this paper, we consider problem row-based standard cell layout, where violations are minimized. Although has been shown be NP-hard general, showed it can solved polynomial when cells. We propose optimal algorithm finds with minimum violations. The efficiency our method further demonstrated by experimental results.