一种集成电路版图验证中短路路径的识别方法

摘要

本发明是一种使用于集成电路版图验证中短路路径的识别方法，所属的技术领域是集成电路计算机辅助设计领域，尤其是涉及集成电路版图的设计规则检查(DRC)和版图与原理图的一致性检查(LVS)领域。本发明的目的在于：提出了一种快速查找版图数据库中短路路径的方法。通过抽象表示，将查找版图数据库中的短路路径问题转化为无向图中指定顶点之间的最短路径的问题，根据无向图的连通特性，将解空间划分为多个相互独立子空间，从而降低问题求解的算法复杂度；同时，本方法根据集成电路设计中数据量大、连接关系复杂的特点，采用了多点出发的广度优先最短路径搜索算法，相对与普通搜索算法，所需的存储空间更小，运行效率更高。

主权项

集成电路版图验证中短路路径的识别方法，其特征在于，包括以下几个步骤：①用无向图抽象表示版图数据库中的图形连接关系；②基于连通子图的解空间划分；③多点出发的广度优先最短路径搜索算法。