TY - GEN
T1 - Post-routing layer assignment for double patterning
AU - Sun, Jian
AU - Lu, Yinghai
AU - Zhou, Hai
AU - Zeng, Xuan
PY - 2011/3/28
Y1 - 2011/3/28
N2 - Double patterning lithography, where one-layer layout is decomposed into two masks, is believed to be inevitable for 32nm technology node of the ITRS roadmap. However, post-routing layer assignment, which decides the layout pattern on each layer, thus having great impact on double patterning related parameters, has not been explored in the merit of double patterning. In this paper, we propose a post-routing layer assignment algorithm for double patterning optimization. Our solution consists of three major phases: multi-layer assignment, single-layer double patterning, and via reduction. For phase one and three, multi-layer graph is constructed and dynamic programming is employed to solve optimization problem on this graph. In the second phase, single-layer double patterning is proved NP-hard and existing algorithm is implemented to optimize single layer double patterning problem. The proposed method is tested on CBL (Collaborative Benchmarking Laboratory) benchmarks and shows great performance. In comparison with single-layer double patterning, our method achieves 73% and 27% average reduction for unresolvable conflicts and stitches respectively, with only 9% increase of via number. When double patterning is constrained on only the bottom two metal layers as in current technology, these numbers become 62%, 8% and 0.42%.
AB - Double patterning lithography, where one-layer layout is decomposed into two masks, is believed to be inevitable for 32nm technology node of the ITRS roadmap. However, post-routing layer assignment, which decides the layout pattern on each layer, thus having great impact on double patterning related parameters, has not been explored in the merit of double patterning. In this paper, we propose a post-routing layer assignment algorithm for double patterning optimization. Our solution consists of three major phases: multi-layer assignment, single-layer double patterning, and via reduction. For phase one and three, multi-layer graph is constructed and dynamic programming is employed to solve optimization problem on this graph. In the second phase, single-layer double patterning is proved NP-hard and existing algorithm is implemented to optimize single layer double patterning problem. The proposed method is tested on CBL (Collaborative Benchmarking Laboratory) benchmarks and shows great performance. In comparison with single-layer double patterning, our method achieves 73% and 27% average reduction for unresolvable conflicts and stitches respectively, with only 9% increase of via number. When double patterning is constrained on only the bottom two metal layers as in current technology, these numbers become 62%, 8% and 0.42%.
UR - http://www.scopus.com/inward/record.url?scp=79952944196&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=79952944196&partnerID=8YFLogxK
U2 - 10.1109/ASPDAC.2011.5722298
DO - 10.1109/ASPDAC.2011.5722298
M3 - Conference contribution
AN - SCOPUS:79952944196
SN - 9781424475155
T3 - Proceedings of the Asia and South Pacific Design Automation Conference, ASP-DAC
SP - 793
EP - 798
BT - 2011 16th Asia and South Pacific Design Automation Conference, ASP-DAC 2011
T2 - 2011 16th Asia and South Pacific Design Automation Conference, ASP-DAC 2011
Y2 - 25 January 2011 through 28 January 2011
ER -