Fixed-Parameter Tractable Algorithms for Optimal Layout Decomposition and Beyond

被引：0

作者：

Kuang, Jian ^{[1
]}

Young, Evangeline F. Y. ^{[1
]}

机构：

[1] Chinese Univ Hong Kong, Dept Comp Sci & Engn, Hong Kong, Peoples R China

来源：

IEEE TRANSACTIONS ON COMPUTER-AIDED DESIGN OF INTEGRATED CIRCUITS AND SYSTEMS | 2019年 / 38卷 / 09期

关键词：

Design for manufacturability; double patterning; fixed-parameter tractable (FPT); layout decomposition; lithography; MASK ASSIGNMENT; OPTIMIZATION; LITHOGRAPHY;

D O I：

10.1109/TCAD.2018.2859255

中图分类号：

TP3 [计算技术、计算机技术];

学科分类号：

0812 ;

摘要：

This paper studies the application of fixed-parameter tractable (FPT) algorithms to solve computer-aided design (CAD) problems. Specifically, we focus on layout decomposition problems for four lithography technologies: 1) double patterning lithography (DPL); 2) DPL with e-beam lithography; 3) DPL with directed self-assembly; and 4) DPL with directed self-assembly and e-beam lithography. Layout decomposition for the first three technologies are long-standing open problems without efficient optimal solutions, and the fourth technology is very promising in the future. The proposed approaches use ideas drastically different from all the previous works and can normally get optimal solutions in a short time. We show the great potential of applying FPT algorithms to solve more NP-hard problems efficiently in CAD.

引用

页码：1731 / 1743

页数：13

共 29 条

[1] Mask Assignment and DSA Grouping for DSA-MP Hybrid Lithography for Sub-7 nm Contact/Via Holes [J].

Badr, Yasmine ;

Torres, Andres ;

Gupta, Puneet .

IEEE TRANSACTIONS ON COMPUTER-AIDED DESIGN OF INTEGRATED CIRCUITS AND SYSTEMS, 2017, 36 (06) :913-926

[2] Fourier Meets Mobius: Fast Subset Convolution [J].

Bjorklund, Andreas ;

Husfeldt, Thore ;

Kaski, Petteri ;

Koivisto, Mikko .

STOC 07: PROCEEDINGS OF THE 39TH ANNUAL ACM SYMPOSIUM ON THEORY OF COMPUTING, 2007, :67-74

[3] An experimental comparison of min-cut/max-flow algorithms for energy minimization in vision [J].

Boykov, Y ;

Kolmogorov, V .

IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE, 2004, 26 (09) :1124-1137

[4] Improved upper bounds for vertex cover [J].

Chen, Jianer ;

Kanj, Iyad A. ;

Xia, Ge .

THEORETICAL COMPUTER SCIENCE, 2010, 411 (40-42) :3736-3756

[5]

Choi Hyeong-Ah., 1989, SIAM Journal on Discrete Mathematics, V2, P38, DOI DOI 10.1137/0402004

[6]

Cormen T. H., 2009, Introduction to algorithms, VThird

[7] MAX-CUT and MAX-BISECTION are NP-hard on unit disk graphs [J].

Diaz, Josep ;

Kaminski, Marcin .

THEORETICAL COMPUTER SCIENCE, 2007, 377 (1-3) :271-276

[8]

Downey Rodney G., 2013, TCS, DOI DOI 10.1007/978-1-4471-5559-1

[9] A Novel Layout Decomposition Algorithm for Triple Patterning Lithography [J].

Fang, Shao-Yun ;

Chang, Yao-Wen ;

Chen, Wei-Yu .

IEEE TRANSACTIONS ON COMPUTER-AIDED DESIGN OF INTEGRATED CIRCUITS AND SYSTEMS, 2014, 33 (03) :397-408

[10] Iterative compression and exact algorithms [J].

Fomin, Fedor V. ;

Gaspers, Serge ;

Kratsch, Dieter ;

Liedloff, Mathieu ;

Saurabh, Saket .

THEORETICAL COMPUTER SCIENCE, 2010, 411 (7-9) :1045-1053

← 1 2 3 →