标题: 使用Prüfer序列的布局编码技术的精准快速之制程热点侦测技术
A Novel Fast and Accurate Process Hotspot Detection Method with Prüfer-Code Layout Encoding
作者: 苏宏彦
Su, Hong-Yan
李毅郎
Li, Yih-Lang
资讯科学与工程研究所
关键字: 可制造性设计;制程热点;图形比对;Design for manufacturability;process hotspot;pattern matching;centerline;Prüfer Encoding
公开日期: 2012
摘要: 近年来,可制造性设计技术已被广泛应用在先进奈米制程上以改善良率,其中,制程热点侦测技术被用来侦测并评判布局图中容易降低良率的图形。此篇论文提出了两种图形模型:骨干图及空间图分别模拟出布局图中多边形的几何关系以及多边形间的空间关系。另一方面,我们也提出基于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.
URI: http://140.113.39.130/cdrfb3/record/nctu/#GT070056054
http://hdl.handle.net/11536/71842
显示于类别:Thesis