臺灣博碩士論文加值系統

在本篇論文中，我們探討兩個有清楚定義的佈局圖案分群問題，一個考慮面積比對限制，另一個考慮邊緣位移限制。給定一個電路佈局和一群標記，我們所探討的佈局圖案分群問題要求根據每個標記找出一個佈局片段，且在不違反面積比對或邊緣位移的限制下，將這些佈局片段分群，目標是分出來的群數越小越好且最大群中的佈局片段個數越多越好，其中面積比對限制或是邊緣位移限制是判斷佈局片段彼此間是否相似而能分在同一群的依據。我們將問題轉換成圖的問題(也就是一個限制型最小控制集問題)並且使用以整數線性規劃為基礎的方法來解決。同時也提供佈局片段合併技術以降低圖的大小，並加速我們的演算法。實驗數據顯示我們的演算法具有很好的效益。

In this thesis, we study two layout pattern classification problems respectively subject to an area match constraint and an edge displacement constraint. Given a circuit layout and a set of markers, each problem asks to identify a layout clip around each marker and divide the set of layout clips into disjoint clusters such that without violating a given area match constraint or edge displacement constraint, the
resultant number of clusters is as small as possible and the maximum cluster size is as large as possible. Either area match constraint or edge displacement constraint is used to well capture the similarity relations between clips and to group similar clips into a cluster. We model each problem as a graph problem (i.e., a constrained minimum dominating set problem) and solve it by an integer linear programming
based method. A clip merging technique for graph size reduction is also presented to accelerate our algorithms. The efficacy of our algorithms is well supported by encouraging experimental results.

1 Introduction 2
2 Preliminaries and Problem Formulations 5
2.1 Preliminaries 5
2.2 Problem Formulations 7
3 ACC Algorithm 9
3.1 Algorithm Overview 9
3.2 Clip Generation 9
3.3 Clip Merging 10
3.4 Similarity Graph Construction for ACC 13
3.5 Representative Clip Selection and Cluster Creation for ACC 14
4 ECC Algorithm 23
4.1 Algorithm Overview 23
4.2 Similarity Graph Construction for ECC 23
4.3 Representative Clip Selection and Cluster Creation for ECC 30
5 Experimental Results 33
6 Conclusion and Future Work 40

[1] Y.-C. Lai, F. E. Gennari, M. W. Moskewicz, J. Lei, and W. Lai, "Method and system for performing pattern classication of patterns in integrated circuit designs," US8,079,005, 2011.
[2] ICCAD 2016 Contest Website. http://cad-contest-2016.el.cycu.edu.tw/Problem_C/default.html.
[3] R. O. Topaloglu, "Cad contest in pattern classification for integrated circuit design space analysis and benchmark suite," in Proceedings of ICCAD, 2016.
[4] J.-Y.Wuu, F. Pikus, A. Torres, and M. Marek-Sadowska, "Rapid layout pattern classification," in Proceedings of ASP-DAC, pp. 781-786, 2011.
[5] Y.-T. Yu, G.-H. Lin, I. H.-R. Jiang, and C. Chiang, "Machine-learning-based hotspot detection using topological classification and critical feature extraction," in IEEE Transactions on Computer-Aided Design of Integrated Circuits
and Systems, vol. 34, no. 3, pp. 460-470, 2015.
[6] J. Guo, F. Yang, S. Sinha, C. Chiang, and X. Zeng, "Improved tangent space based distance metric for accurate lithographic hotspot classification," in Proceedings of DAC, pp. 1169-1174, 2012.
[7] N. Ma, J. Ghan, S. Mishra, C. Spanos, and K. Poolla, "Automatic hotspot classification using pattern-based clustering," in Proceedings of SPIE, vol. 6925, pp. 692505-1-692505-10, 2008.
[8] V. Dai, Y.-C. Lai, F. Gennari, E. Teoh, and L. Capodieci, "Systematic physical verification with topological patterns," in Proceedings of SPIE, vol. 9053, pp. 905304-1-905304-10, 2014.
[9] E. Teoh, V. Dai, L. Capodieci, Y.-C. Lai, and F. Gennari, "Systematic data mining using a pattern database to accelerate yield ramp," in Proceedings of SPIE, vol. 9053, pp. 905306-1-905306-13, 2014.
[10] J. P. Cain, Y.-C. Lai, F. Gennari, and J. Sweis, "Methodology for analyzing and quantifying design style changes and complexity using topological patterns," in
Proceedings of SPIE, vol. 9781, pp. 978108-1-978108-13, 2016.
[11] Y.-T. Yu, Y.-C. Chen, S. Sinha, I. H.-R. Jiang, and C. Chiang, "Accurate process-hotspot detection using critical design rule extraction," in Proceedings of DAC, pp. 1163-1168, 2012.
[12] Y.-T. Yu, I. H.-R. Jiang, Y. Zhang and C. Chiang, "DRC-based hotspot detection considering edge tolerance and incomplete specification," in Proceedings of ICCAD, pp. 101-107, 2014.
[13] A. B. Kahng, C.-H. Park, and X. Xu, "Fast dual-graph-based hotspot filtering," in Proceedings of SPIE, vol. 27, pp. 1635-1642, 2006.
[14] J. W. Park, R. Todd, and X. Song, "Geometric pattern match using edge driven dissected rectangles and vector space," in IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 35, no. 12, pp. 2046-2055, 2016.
[15] C. C. Chang, I. C. Shih, J. Lin, Y. Yen, C. Lai, W. Huang, R. Liu, and Y. Ku, "Layout patterning check for DFM," in Proceedings of SPIE, vol. 6925, pp. 69251R-1-6925R-7, 2008.
[16] J. Xu, K. Krishnamoorthy, E. Teoh, V. Dai, and L. Capodieci, "Design layout analysis and DFM optimization using topological patterns," in Proceedings of SPIE, vol. 9427, pp. 94270Q-1-94270Q-11, 2015.
[17] P.-H. Wu, C.-W. Chen, C.-R. Wu, and T.-Y. Ho, "Triangle-based process hotspot classication with dummication in EUVL," in Proceedings of VLSI-DAT, pp. 1-4, 2014.
[18] S. Wagner and D. Wagner, Comparing Clusterings - An Overview. http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.164.6189, 2007.
[19] Clipper - an Open source freeware library for clipping and offsetting lines and polygons. http://www.angusj.com/delphi/clipper.php.
[20] T. Kloks and Y.-L. Wang, Advances in Graph Algorithms, pp. 17-21. http://vixra.org/abs/1409.0165, 2013.