基于边的倒序树扫描线算法优化层次版图验证技术

摘要

基于边的倒序树扫描线算法优化层次版图验证技术含有)ILT运算的复杂度降到线性的步骤，其特征在于含有以下操作步骤：利用了基于边的扫描线算法和VLSI版图验证的局部性原理，引入版图倒序树(Inverse Layout Tree)和投影边(halo element)的概念，在计算边的状态时发明了“存在状态”与“不存在状态”两种类型的ILT，通过投影法和倒序树扫描线的结合来对版图进行分解，计算操作。利用VLSI版图数据的局部性原理和基于边的扫描线算法的特点，把(版图倒序树)ILT运算的算法复杂度降到线性的程度。使得避免组合爆炸问题并且避免了不同边操作下的几何操作重复这一技术缺陷。