使用Prüfer序列的佈局編碼技術的精準快速之製程熱點偵測技術

Abstract

近年來，可製造性設計技術已被廣泛應用在先進奈米製程上以改善良率，其中，製程熱點偵測技術被用來偵測並評判佈局圖中容易降低良率的圖形。此篇論文提出了兩種圖形模型：骨幹圖及空間圖分別模擬出佈局圖中多邊形的幾何關係以及多邊形間的空間關係。另一方面，我們也提出基於Prüfer編碼的演算法進一步的將骨幹圖編碼成一串序列。因此，被轉化成圖形同構問題的單一多邊形比對問題，我們可藉由比對兩個骨幹圖經此編碼後的序列解決。我們也提出一個基於分支定界的圖形定位演算法可以快速有效的解決一般性圖形同構問題中的頂點排序問題，並用以比對兩個空間圖是否同構。實驗結果顯示相較於採用設計法則類的方法，我們擁有與之相同的精準度且平均速度快上5.7倍。

As design-for-manufacturability techniques have become widely used to improve the yield of nano-scale semiconductor technology in recent years, hot-spot detection methods have been investigated with a view to calibrating layout patterns that tend to reduce yield. In this work, we propose two graph models, i.e., skeleton graph and space graph, to formulate polygon topology and spatial relationship among polygons. In addition, a Prüfer Encoding based method is presented to encode each skeleton graph. Single polygon matching problem is then equivalent to the verification of graph isomorphism, which is realized by checking the identity of two enhanced Prüfer codes associated with two skeleton graphs. A branch-and-bound based pattern anchoring algorithm is presented to resolve the vertex ordering problem for isomorphism checking. Finally, the general exact pattern matching problem can be accomplished by adopting the space graph to identify the similarity of spatial relationship among polygons. Experimental results show that we can achieve 5.7x runtime speedup than design-rule-based methodology in average.