臺灣博碩士論文加值系統

隨著先進製程快速發展下，佈局圖案(Layout pattern)更容易受到製程變異(Process variation)的影響，其中有些佈局圖案雖然能通過設計法則驗證(Design rule checking)，但其可印刷性顯得相當不好，我們統稱其為微影熱點(Lithography hotspots)。為了提高可製造性及良率，這些熱點需要盡可能在設計流程前期就被偵測出來，大部分的熱點偵測(Hotspot detection)研究中，熱點圖案分類常被忽略，但熱點偵測的效率往往與熱點圖案分類息息相關，在熱點圖案分類中，相似的圖案需要被歸類為同一群，同一群內能允許些微誤差，而每一群會被選出一個熱點代表做為應用，如當作熱點偵測的圖案代表，為了使熱點偵測更有效率，群集數量(熱點代表)需要被最小化。在此篇文獻中，我們提出了佈局片段移動法以降低熱點圖案分類的群集數量，並制訂兩階段的圖案比對演算法，對一個集合覆蓋問題(Set cover problem)找出最佳解，實驗結果顯示，我們的演算法能夠降低2016 CAD Contest at ICCAD提供的範例群集數量30%。

With the rapid advance of semiconductor process technologies, layout features in integrated circuits (ICs) become highly prone to process variations. Lithography hotspots are a set of problematic layout patterns with poor printability even if they pass design rule checking (DRC). These hotspots need to be detected and fixed as early as possible in the design flow to improve manufacturability and yield. While most of existing studies focus on hotspot detection, hotspot pattern classification is rarely addressed but plays an important role in determining the efficiency of hotspot detection. In hotspot pattern classification, similar hotspots are classified into a cluster with tolerance constraints, and a representative hotspot is chosen for each cluster for future application. To minimize the problem size of subsequent hotspot detection, the number of clusters, and thus the number of representative hotspots, should be minimized. In this paper, a clip shifting method is adopted to further reduce the cluster number during hotspot classification. We propose a two-stage pattern matching algorithm flow and derive optimal solutions by solving a set cover problem. Experiment results show that our flow can reduce the cluster number by about 30% compared to reference results in 2016 CAD Contest at ICCAD.

Table of Contents
Abstract vii
List of Tables xi
List of Figures xii
Chapter 1. Introduction 1
1.1 Hotspot Detection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.2.1 Layout Encoding Techniques . . . . . . . . . . . . . . . . . . . . . 4
1.2.2 Pattern Matching Based Hotspot Detection . . . . . . . . . . . . . 7
1.2.3 Machine Learning Based Hotspot Detection . . . . . . . . . . . . . 9
1.2.4 Hybrid Pattern Matching and Machine Learning . . . . . . . . . . 11
1.3 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
1.4 Contributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
1.5 Thesis Organization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
Chapter 2. Preliminaries 16
2.1 Terminologies . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
2.2 Problem Formulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
Chapter 3. Hotspot Pattern Classication 20
3.1 Pattern Classication Flow . . . . . . . . . . . . . . . . . . . . . . . . . . 20
3.2 Clip Construction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
3.3 Exact Clip Matching . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
3.4 Area/Edge-Tolerant Clip Matching with Clip Shifting . . . . . . . . . . . 25
3.4.1 Clip Candidate Generation with Clip Shifting . . . . . . . . . . . . 26
3.4.2 Area/Edge-Tolerant Clip Matching . . . . . . . . . . . . . . . . . . 26
3.5 Cluster Number Minimization with Set Covering . . . . . . . . . . . . . . 27
Chapter 4. Experimental Results 32
4.1 Environment Setting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
4.2 Comparison with 2016 CAD Contest . . . . . . . . . . . . . . . . . . . . 33
4.3 Clip Shifting Eciency . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
4.4 Runtime Detail Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
Chapter 5. Conclusions and Future Work 40
Bibliography 41

[1] D. Ding, A. J. Torres, F. G. Pikus and D. Z. Pan. "High performance lithographic hotspot detection using hierarchically rened machine learning." In Asia and South Pacic Design Automation Conference (ASP-DAC), pp. 775-780, 2011.
[2] D. G. Drmanac, F. Liu and L. C. Wang. "Predicting variability in nanoscale lithography processes." In ACM/IEEE Design Automation Conference (DAC), pp. 545-550, 2009.
[3] J. Ghan, N. Maa, S. Mishraa, C. Spanosa, K. Poollaa, N. Rodriguezb, L. Capodiecib. Clustering and pattern matching for an automatic hotspot classication and detection system," In Proc. SPIE Design for Manufacturability through Design-Process Integration III, pp. 727 516727 51611, 2009.
[4] J. Guo, F. Yang, S. Sinha, C. Chiang and X. Zeng. "Improved tangent space based distance metric for accurate lithographic hotspot classication." In ACM/IEEE Design Automation Conference (DAC), pp. 1169-1174, 2012.
[5] W. Hoppe, T. Roessler, and J. A. Torres. Beyond rule-based physical verication. In Proc. SPIE, vol. 6349, pp. 63494X, 2006.
[6] A. B. Kahng, C.-H. Parka, and X. Xu. Fast Dual Graph Based Hotspot Detection. In Proc. SPIE, vol. 6349, pp. 628635, 2006.
[7] J.-M. Lin and Y.-W. Chang. TCG: A Transitive closure graph based representation for non-slicing floorplans. In ACM/IEEE Design Automation Conference (DAC), pp. 764769, 2001.
[8] J. Kim and M. Fan. Hotspot detection on Post-OPC layout using full chip simulation based verication tool: A case study with aerial image simulation.
In Proc. SPIE, vol. 5256, pp. 919{925, 2003.
[9] Sheng-Yuan Lin, Jing-Yi Chen, Jin-Cheng Li, Wan-yu Wen and Shih-Chieh Chang. "A novel fuzzy matching model for lithography hotspot detection." In ACM/IEEE Design Automation Conference (DAC), pp. 1-6, 2013.
[10] Ning Ma. "Automatic IC Hotspot Classication and Detection using Pattern Based Clustering." In PhD thesis, Engineering lC Mechanical Engineering, University of California, Berkeley, 2008.
[11] K. Madkour, S. Mohamed, D. Tantawy and M. Anis. "Hotspot detection using machine learning." In International Symposium on Quality Electronic Design (ISQED), pp. 405-409, 2016.
[12] Hong-Yan Su, Chieh-Chu Chen, Yih-Lang Li, An-Chun Tu, Chuh-Jen Wu, and Chen-Ming Huang "A Novel Fast Layout Encoding Method for Exact Multilayer Pattern Matching With Prfer Encoding." In IEEE Trans. Computer Aided Design of Integrated Circuits and Systems (TCAD), vol. 34, no. 10, pp. 95-108, November 2014.
[13] J.-Y. Wuu, F. G. Pikus, A. Torres, and M. Marek-Sadowska. "Rapid layout pattern classication." In Asia and South Pacic Design Automation Conference (ASP-DAC), pp. 781-786, 2011.
[14] Jingyu Xu, Subarna Sinha and C. C. Chiang. "Accurate detection for process hotspots with vias and incomplete specication." In IEEE/ACM International Conference on Computer-Aided Design (ICCAD), pp. 839-846, 2007.
[15] Wing Chiu Tam and Ronald D.Blanton. "LASIC: Layout Analysis for Systematic IC-Defect Identication Using Clustering." In IEEE Trans. Computer Aided Design of Integrated Circuits and Systems (TCAD), vol. 34, no. 8, pp.1278-1290, August 2015.
[16] H. Yao, S. Sinha, C. Chiang, X. Hong and Y. Cai. "Effcient Process-Hotspot Detection Using Range Pattern Matching." In IEEE/ACM International Conference on Computer Aided Design (ICCAD), pp. 625-632, 2006.
[17] J.-Y. Wuu, F. G. Pikus, A. Torres, and M. Marek-Sadowska. Detecting context sensitive hotspots in standard cell libraries. In Proc. SPIE, vol. 7275, Mar. 2009, Art. ID 727515.
[18] Y. T. Yu, Y. C. Chan, S. Sinha, I. H. R. Jiang and C. Chiang. "Accurate process-hotspot detection using critical design rule extraction." In 2012 49th ACM/IEEE Design Automation Conference (DAC), pp. 1163-1168, 2012.
[19] Bei Yu, David Z. Pan, Tetsuaki Matsunawa, and Xuan Zeng. "Machine Learning and Pattern Matching in Physical Design." In Asia and South Pacic Design Automation Conference (ASP-DAC), pp. 286-293, 2015.
[20] Y. T. Yu, G. H. Lin, I. H. R. Jiang and C. Chiang. "Machine-Learning-Based Hotspot Detection Using Topological Classication and Critical Feature Extraction." In IEEE Trans. Computer-Aided Design of Integrated Circuits and Systems (TCAD), vol. 34, no. 3, pp. 460-470, March 2015.
[21] IBM ILOG CPLEX Optimizer. http://www-01.ibm.com/software/
integration/optimization/cplex-optimizer/
[22] Rasit O. Topaloglu, "CAD Contest in Pattern Classication for Integrated Circuit Design Space Analysis and Benchmark Suite," Proc. IEEE/ACM ICCAD, 2016.