在面積或邊緣限制下佈局圖案分群的優化

On Optimizing Layout Pattern Classification under Area or Edge Constraint

宋裕民(Sung, Yu Min)

指導教授 ： 王廷基

國立清華大學/電機資訊學院/資訊工程學系所/碩士(2016年)

摘要

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

關鍵字

佈局圖案分群 ； 超大型積體電路設計 ； 電子設計自動化

並列摘要

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.

並列關鍵字

layout pattern classification ； VLSI design ； electronic design automation (EDA)

參考文獻

[3] R. O. Topaloglu, "Cad contest in pattern classification for integrated circuit design space analysis and benchmark suite," in Proceedings of ICCAD, 2016.

[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

[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.

[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.