在現代的科技蓬勃發展下，半導體製造進入了次10 奈米的技術節點，關鍵尺寸的微小化使得下一世代微影技術被迫切地需要，其中，團鏈共聚物定向自組裝微影技術已經證明其用於製作導通孔的可能性。除此之外，後佈局冗餘導通孔插入已經變成為保證足夠良率以及電路可靠性的一個必要步。然而，目前現有的冗餘導通孔插入演算法並不適用於定向自組裝微影，因為任意地插入冗餘導通孔可能會導致導通孔的可製造性大幅下降；但是相反的，一個經過精密設計並考慮定向自組裝微影技術的冗餘導通孔插入演算法不僅可以增加電路的可靠性，更可能可以改善導通孔在定向自組裝微影中的可製造性。在此論文中，我們提出了第一個針對定向自組裝微影技術的演算法，此演算法以一個整數線性規劃公式來同時考慮引導樣板最佳化和冗餘導通孔插入。為了促進整數線性規劃公式的開發，我們提出一個系統性的方法來決定一個導通孔是否可以用定向自組裝微影製造出來；除此之外，我們亦提出整數線性規劃簡化的技術以大量減少計算複雜。實驗的結果表示，此演算法可以在合理的時間內有效的使不可製造的導通孔數目最小化並使冗餘導通孔的插入比例最大化。

Next generation lithography technologies are urgently required in sub-10 nm technology nodes, and the diblock copolymer directed self-assembly (DSA) technology has shown its strong potential for contact/via layer fabrication. In addition, post-layout redundant via insertion has become a necessary step to guarantee sufficient yield and circuit reliability. However, existing redundant via insertion algorithms are not suitable for DSA since they could seriously decrease via manufacturability. On the contrary, a sophisticated DSA-aware redundant via insertion algorithm may not only enhance circuit reliability but also turn the original unmanufacturable via pattern into manufacturable one. In this work, we propose an optimal integer linear programming (ILP)-based algorithm to simultaneously consider guiding template optimization and redundant via insertion for DSA. To facilitate the development of the ILP formulation, a systematic approach is proposed to determine whether a via is manufacturable with DSA. In addition, reduction techniques are presented to greatly reduce the computational complexity of ILP and runtimes. Experimental results show that our algorithm can effectively minimize the number of unmanufacturable vias and maximize the redundant via insertion rate within reasonable computation time.

[1] Y. Ban, K. Lucas, and D. Pan, "Flexible 2D layout decomposition framework for spacer-type double pattering lithography," in Proceedings of ACM/IEEE Design Automation Conference (DAC), pp. 789-794, 2011.
[2] H.-Y. Chen, M.-F. Chiang, and Y.-W. Chang, "Novel full-chip gridless routing considering double-via insertion," in Proceedings of ACM/IEEE Design Automation Conference (DAC), pp. 755-760, 2006.
[3] H.-Y. Chen, M.-F. Chiang, Y.-W. Chang, L. Chen, and B. Han, "Full-chip routing considering double-via insertion," in IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems (TCAD), vol. 27, no. 5, pp. 844-857, 2008.
[4] M. Cho, Y. Ban, and D. Z. Pan, "Double patterning technology friendly
detailed routing," in Proceedings of IEEE/ACM International Conference on
Computer-Aided Design (ICCAD), pp. 506-511, 2008.
[5] Y. Du, Q. Ma, H. Song, J. Shiely, G. Luk-Pat, A. Miloslavsky, and
M. D. F. Wong, "Spacer-is-dielectric-compliant detailed routing for self-aligned double patterning lithography," in Proceedings of ACM/IEEE Design Automation Conference (DAC), pp. 1-6, 2013.
[6] Y. Du, D. Guo, M. D. F. Wong, H. Yi, H.-S. P. Wong, H. Zhang, and Q. Ma,
"Block copolymer directed self-assembly (DSA) awrae contact layer optimiza-
tion for 10 nm 1D standard cell library," in Proceedings of IEEE/ACM Inter-
national Conference on Computer-Aided Design (ICCAD), pp. 186-193, 2013.
[7] Y. Du, Z. Xiao, M. D. F.Wong, H. Yi, and H.-S. P.Wong, "DSA-aware detailed routing for via layer optimization," in Proc. SPIE, vol. 9049, pp. 904920, 2014.
[8] S.-Y. Fang, Y.-W. Chang, and W.-Y. Chen, "A novel layout decomposition
algorithm for triple patterning lithography," in Proceedings of ACM/IEEE De-
sign Automation Conference (DAC), pp. 1181-1186, 2012.
[9] J.-R. Gao and D. Z. Pan, "Flexible self-aligned double patterning aware detailed routing with prescribed layout planning," in Proceedings of ACM International Symposium on Physical Design (ISPD), pp. 25-32, 2012.
[10] D. Herr, "The extensibility of optical patterning via directed self-assembly of nano-engineered imaging materials," Future Fab International (www.futurefab.com), vol. 18, 2005.
[11] A. B. Kahng, C.-H. Park, X. Xu, and H. Yao, "Layout decomposition
approaches for double patterning lithography," in IEEE Transactions on
Computer-Aided Design of Integrated Circuits and Systems (TCAD), vol. 29,
no. 6, pp. 939-952, 2010.
[12] J. Kuang and E. F. Y. Young, "An e cient layout decomposition approach for triple patterning lithography," in Proceedings of ACM/IEEE Design Automation Conference (DAC), pp. 1-6, 2013.
[13] K.-Y. Lee, C.-K. Koh, T.-C. Wang, and K.-Y. Chao, "Optimal post-routing
redundant via insertion," in Proceedings of ACM International Symposium on
Physical Design (ISPD), pp. 111-117, 2008.
[14] K.-Y. Lee, C.-K. Koh, T.-C. Wang, and K.-Y. Chao, "Fast and optimal re-
dundant via insertion," in IEEE Transactions on Computer-Aided Design of
Integrated Circuits and Systems (TCAD), vol. 27, no. 12, pp. 2197-2208, 2008.
[15] K.-Y. Lee, S.-T. Lin, and T.-C. Wang, "Redundant via insertion with wire bending," in Proceedings of ACM International Symposium on Physical Design (ISPD), pp. 123-130, 2008.
[16] K.-Y. Lee, T.-C. Wang, C.-K. Koh, and K.-Y. Chao, "Optimal double via
insertion with on-track preference," in IEEE Transactions on Computer-Aided
Design of Integrated Circuits and Systems (TCAD), vol. 29, no. 2, pp. 318-323, 2010.
[17] S.-T. Lin, K.-Y. Lee, T.-C. Wang, C.-K. Koh, and K.-Y. Chao, "Simultaneous redundant via insertion and line end extension for yield optimization," in Proc. ASPDAC, pp. 633{638, 2011.
[18] I.-J. Liu, S.-Y. Fang, and Y.-W. Chang, "Overlay-aware detailed routing for self-aligned double patterning lithography using the cut process," in Proceedings of ACM/IEEE Design Automation Conference (DAC), pp. 1-6, 2014.
[19] Q. Ma, H. Zhang and M. D. F. Wong, "Triple patterning aware routing and
its comparison with double patterning aware routing in 14nm technology," in
Proceedings of ACM/IEEE Design Automation Conference (DAC), pp. 591-596, 2012.
[20] Z. Xiao, Y. Du, H. Tian, M. D. F. Wong, H. Yi, and H.-S. P. Wong, "DSA
template optimization for contact layer in 1D standard cell design," in Proc. SPIE, vol. 9049, pp. 90492J, 2014.
[21] Z. Xiao, Y. Du, H. Tian, M. D. F. Wong, H. Yi, H.-S. P. Wong, and H. Zhang, "Directed self-assembly (DSA) template pattern veri cation," in Proceedings of ACM/IEEE Design Automation Conference (DAC), pp. 1-6, 2014.
[22] H. Yi, X.-Y. Bao, J. Zhang, R. Tiberio, J. Conway, L.-E. Chang, S. Mitra, and H.-S. P. Wong, "Contact hole patterning for random logic circuits using block copolymer directed self-assembly," in Proc. SPIE, vol. 8323, pp. 83230W, 2012.
[23] H. Yi, X.-Y. Bao, R. Tiberio, and H.-S. P. Wong, "Design strategy of small topographical guiding templates for sub-15 nm integrated circuits contact hole patterns using block copolymer directed self-assembly," in Proc. SPIE, vol. 8680, pp. 868010, 2013.
[24] IBM ILOG CPLEX Optimizer. http://www-01.ibm.com/software/
integration/optimization/cplex-optimizer/
[25] International Technology Roadmap for Semiconductors (ITRS). http://www.itrs.net/