一种重建电路并联子结构的方法

摘要

一种重建电路并联子结构的方法，包括以下步骤：1)将电路转为二分图；2)初始化顶点标记，对节点顶点进行标记；3)根据标记进行节点顶点聚类；4)根据标记进行器件顶点聚类；5)检查是否已收敛到不动点，若是则执行步骤6)，否则返回步骤3)；6)统计各类中顶点数量，重建并联子结构。本发明的重建电路并联子结构的方法，能够有效应用于在大规模电路中重建所有具有任意器件数、任意连接的并联子结构，从而提高电路约减率，提升仿真性能。

权利要求

1.一种重建电路并联子结构的方法，其特征在于，包括以下步骤：

1)将电路转为二分图；

2)初始化顶点标记，对节点顶点进行标记；

所述步骤2)初始化顶点，对节点顶点进行标记的步骤，还包括，对于器件顶点，两个器件对应的图顶点标记相同，当且仅当这两个器件的类型相同且参数相同时，对于节点顶点，赋予相同的标记；

3)根据标记进行节点顶点聚类；

所述步骤3)根据标记进行节点顶点聚类的步骤，还包括，当且仅当同时满足：这两个顶点当前标记相同、它们和相邻器件顶点的连接完全相同、对应相邻器件顶点的当前标记相同的三个条件时，判定两个节点顶点属于同类；

4)根据标记进行器件顶点聚类；

所述步骤4)根据标记进行器件顶点聚类的步骤，还包括，当且仅当同时满足：这两个顶点当前标记相同、它们和相邻节点顶点的连接完全相同、对应相邻节点顶点的当前标记相同的三个条件时，判定两个器件顶点属于同类；

5)检查是否已收敛到不动点，若是则执行步骤6)，否则返回步骤3)；

6)统计各类中顶点数量，重建并联子结构。

2.根据权利要求1所述的重建电路并联子结构的方法，其特征在于，构造分类器，将所有顶点进行分类。

3.根据权利要求1所述的重建电路并联子结构的方法，其特征在于，所述步骤5)检查是否已收敛到不动点的步骤，还包括，检查收敛条件，若本次聚类的类数目和上次聚类相同，则表示已收敛到不动点。

4.根据权利要求1所述的重建电路并联子结构的方法，其特征在于，所述步骤6)统计各类中顶点数量，重建并联子结构的步骤，还包括，统计各类中顶点的个数，将顶点个数为1的类的顶点标记为不连通，将每个连通分量构建为一个并联子结构，标记相同的顶点是并联子结构的对应点。

5.一种电子设备，其特征在于，

包括存储器和处理器，所述存储器上储存有在所述处理器上运行的计算机程序，所述处理器运行所述计算机程序时执行权利要求1至4任一项所述的重建电路并联子结构的方法的步骤。

6.一种计算机可读存储介质，其上存储有计算机程序，其特征在于，所述计算机程序运行时执行权利要求1至4任一项所述的重建电路并联子结构的方法的步骤。

说明书

一种重建电路并联子结构的方法

技术领域

[0001] 本发明涉及EDA仿真工具技术领域，特别是涉及一种高效重建电路任意并联子结构的方法。

背景技术

[0002] 在集成电路仿真过程中，为了降低计算量，需要事先对电路进行约减，重建电路的并联子结构，再将这些子结构合并可以有效达到约减的目的，在上述过程中，重建并联子结构是核心步骤。传统的基于图搜索的并联子结构重建算法一般只用于识别器件级的并联，即如果一系列器件的类型相同，参数相同，且相同的端口连在一起，则把这些器件识别为并联，每个器件为一个并联单元，如图2所示。然而实际电路的并联单元并不是器件级的，有可能是若干器件构成的子电路，这样的并联子电路可由任意数目的器件以任意的方式连接构成，如图3所示。假设某个并联子结构由N个器件构成，若采用图搜索的策略找到所有并联子结构，其时间复杂度和空间复杂度都是关于N的指数函数，且算法逻辑很复杂，一般需要维护若干候选集合，集合的元素是当前找到的所有并联单元。在算法的每一步都要动态更新这些集合，如分离、合并。因此考虑到仿真效率，如果采用传统的基于图搜索的策略来寻找并联子结构一般最多只找到2‑3级，即并联单元的器件数不超过2或3，这样就限制了电路约减的程度。

发明内容

[0003] 为了解决现有技术存在的不足，本发明的目的在于提供一种重建电路并联子结构的方法，能够有效应用于在大规模电路中重建所有具有任意器件数、任意连接的并联子结构，从而提高电路约减率，提升仿真性能。

[0004] 为实现上述目的，本发明提供的一种重建电路并联子结构的方法，包括以下步骤：

[0005] 1)将电路转为二分图；

[0006] 2)初始化顶点，对节点顶点进行标记；

[0007] 3)根据标记进行节点顶点聚类；

[0008] 4)根据标记进行器件顶点聚类；

[0009] 5)检查是否已收敛到不动点，若是则执行步骤6)，否则返回步骤3)；

[0010] 6)统计各类中顶点数量，重建并联子结构。

[0011] 进一步地，所述步骤2)初始化顶点，对节点顶点进行标记的步骤，还包括，[0012] 对于器件顶点，两个器件对应的图顶点标记相同，当且仅当这两个器件的类型相同且参数相同时，对于节点顶点，赋予相同的标记。

[0013] 进一步地，所述步骤3)根据标记进行节点顶点聚类的步骤，还包括，[0014] 当且仅当同时满足：这两个顶点当前标记相同、它们和相邻器件顶点的连接完全相同、对应相邻器件顶点的当前标记相同的三个条件时，判定两个节点顶点属于同类。

[0015] 进一步地，所述步骤4)根据标记进行器件顶点聚类的步骤，还包括，[0016] 当且仅当同时满足：这两个顶点当前标记相同、它们和相邻节点顶点的连接完全相同、对应相邻节点顶点的当前标记相同的三个条件时，判定两个器件顶点属于同类。

[0017] 进一步地，构造分类器，将所有顶点进行分类。

[0018] 进一步地，所述步骤5)检查是否已收敛到不动点的步骤，还包括，检查收敛条件，若本次聚类的类数目和上次聚类相同，则表示已收敛到不动点。

[0019] 更进一步地，所述步骤6)统计各类中顶点数量，重建并联子结构的步骤，还包括，[0020] 统计各类中顶点的个数，将顶点个数为1的类的顶点标记为不连通，将每个连通分量构建为一个并联子结构，标记相同的顶点是并联子结构的对应点。

[0021] 为实现上述目的，本发明还提供一种电子设备，包括存储器和处理器，所述存储器上储存有在所述处理器上运行的计算机程序，所述处理器运行所述计算机程序时执行如上文所述的重建电路并联子结构的方法的步骤。

[0022] 为实现上述目的，本发明还提供一种计算机可读存储介质，其上存储有计算机程序，所述计算机程序运行时执行如上文所述的重建电路并联子结构的方法的步骤。

[0023] 本发明的重建电路并联子结构的方法、电子设备及计算机可读存储介质，具有以下有益效果：

[0024] 1)利用并联子图的特性，将并联单元的识别问题转化为寻找标记不动点的问题，在每个迭代步骤，只需检查顶点及其相邻顶点并更新标记，流程非常简单，利于实现；

[0025] 2)本算法的最坏时间复杂度和图的半径(最远两个顶点的距离)、顶点数、器件的平均端口数的乘积成正比，空间复杂度和顶点数成正比，而对于实际应用，每个迭代步需要处理的顶点数目会随迭代次数增加而逐步减少，且收敛需要的迭代步一般很少，因此很适合大规模电路任意并联子结构的重建。

[0026] 本发明的其它特征和优点将在随后的说明书中阐述，并且，部分地从说明书中变得显而易见，或者通过实施本发明而了解。

附图说明

[0027] 附图用来提供对本发明的进一步理解，并且构成说明书的一部分，并与本发明的实施例一起，用于解释本发明，并不构成对本发明的限制。在附图中：

[0028] 图1为根据本发明的重建电路并联子结构的方法流程图；

[0029] 图2为并联单元为单个器件的示意图；

[0030] 图3为并联单元为多个器件组成的子结构的示意图；

[0031] 图4为根据本发明的一个实施例电路转为二分图示意图；

[0032] 图5为根据本发明的一个实施例节点顶点聚类并更新节点顶点标记示意图；

[0033] 图6为根据本发明的一个实施例器件顶点聚类并更新器件顶点标记示意图；

[0034] 图7为根据本发明的一个实施例节点顶点聚类并更新节点顶点标记示意图。

具体实施方式

[0035] 以下结合附图对本发明的优选实施例进行说明，应当理解，此处所描述的优选实施例仅用于说明和解释本发明，并不用于限定本发明。

[0036] 图1为根据本发明的重建电路并联子结构的方法流程图，下面将参考图1，对本发明的重建电路并联子结构的方法进行详细描述。

[0037] 首先，在步骤101，将电路转为二分图。

[0038] 在步骤102，初始化顶点标记。

[0039] 优选地，对于器件顶点，两个器件对应的图顶点标记相同，当且仅当这两个器件的类型相同(如同属于线性电阻，或同属于相同model的mosfet)且参数相同。对于节点顶点，赋予相同的标记。

[0040] 在步骤103，节点顶点聚类。

[0041] 优选地，构造分类器(可由哈希map实现)，将所有节点顶点进行分类。

[0042] 优选地，当且仅当同时满足：(a)这两个顶点当前标记相同、(b)它们和相邻器件顶点的连接完全相同、(c)对应相邻器件顶点的当前标记相同的三个条件时，两个节点顶点属于同类。

[0043] 在步骤104，器件顶点聚类。

[0044] 优选地，构造分类器(可由哈希map实现)，将所有器件顶点进行分类。

[0045] 优选地，当且仅当同时满足：(a)这两个顶点当前标记相同；(b)它们和相邻节点顶点的连接完全相同；(c)对应相邻节点顶点的当前标记相同的三个条件时，判定两个顶点属于同类。

[0046] 在步骤105，检查收敛条件，如果本次聚类的类数目和上次聚类相同，则表示已收敛到不动点，执行步骤106，否则返回步骤103。

[0047] 在步骤106，重建并联子结构。

[0048] 优选地，统计各类中顶点的个数，将顶点个数为1的类的顶点标记为不连通，以此构建图的连通分量。

[0049] 优选地，将每个连通分量构建为一个并联子结构，且标记相同的顶点是并联子结构的对应点。

[0050] 本申请的一个实施例中，将电路中的器件(device)和节点(node)作为图的顶点，器件和节点的连接作为图的边，一个电路结构可用一个二分图G(V,E)描述：其中V是顶点集合，E是边集合，且V是两个不相交子集Vd和Vn的并集，Vd是器件顶点的集合，Vd是节点顶点的集合，并满足仅Vd和Vn之间有边，Vd和Vn内无边。M是一个标记的集合，可把标记看做正整数，则M＝{1,2,3,..}，F是从V到M的映射，即给顶点v∈V赋予一个标记F(v)＝m∈M。则任意两个子图G1、G2的并联关系可这样描述：存在G1与G2顶点的某个一一对应，在这种对应下任意两个对应顶点的标记相同，当且仅当它们和相邻顶点的连接方式相同，且相邻顶点的标记也对应相同。对于某种操作，对给定的标记方法F，如果不满足上述性质，则需对F做某种调整，可知满足上述性质的F是这种操作的唯一不动点，因此可采用迭代法找到这个不动点，从而找出并联子结构。

[0051] 下面结合一具体实施例对本发明的重建电路并联子结构的方法做进一步的说明。

[0052] 图2为并联单元为单个器件的示意图，如图2所示，并联单元只有一种类型的器件A，器件端口分别为p1、p2、p3。

[0053] 图3为多个器件组成的子结构的示意图，如图3所示，并联单元包括两种类型的器件A、B，器件端口分别为p1、p2、p3为器件端口。

[0054] 图4为根据本发明的一个实施例电路转为二分图示意图，如图4所示，黑色为节点顶点，白色为器件顶点，圈内数字为标记值；对于两类器件A、B，假设同类型器件参数相同，对应顶点标记分别为1和2，所有节点对应顶点标记为3。

[0055] 本实施例中，以图3电路结构为例，重建任意并联电路子结构的一般步骤，可具体执行为：

[0056] 步骤(1)：将电路转为二分图。

[0057] 步骤(2)：初始化顶点标记。

[0058] 本实施例中，对于器件顶点，两个器件对应的图顶点标记相同，当且仅当这两个器件的类型相同且参数相同。对于节点顶点，赋予相同的标记。如图4所示，有两类器件A、B，假设同类型器件参数相同，对应顶点标记分别为1和2，所有节点对应顶点标记为3。

[0059] 步骤(3)：循环执行步骤(4)至步骤(6)，直到满足收敛条件。

[0060] 步骤(4)：(迭代第一步)节点顶点聚类并更新标记。构造分类器(可由哈希map实现)，将所有节点顶点进行分类，分类标准是：两个节点顶点属于同类，当且仅当同时满足(a).这两个顶点当前标记相同；(b).它们和相邻器件顶点的连接完全相同；(c).对应相邻器件顶点的当前标记相同。更新顶点标记，两个顶点赋予的新标记相同，当且仅当它们分在同一类。图5为根据本发明的一个实施例节点顶点聚类并更新节点顶点标记示意图，如图5所示，左下角原标记为3的顶点更新成4，中间原标记为3的顶点标记更新成5，右上角原标记为3的顶点更新成6。

[0061] 步骤(5)：(迭代第一步)器件顶点聚类并更新标记。构造分类器(可由哈希map实现)，将所有器件顶点进行分类，分类标准是：两个顶点属于同类，当且仅当同时满足(a).这两个顶点当前标记相同；(b).它们和相邻节点顶点的连接完全相同；(c).对应相邻节点顶点的当前标记相同。更新顶点标记，两个顶点赋予的新标记相同，当且仅的它们分在同一类。图6为根据本发明的一个实施例器件顶点聚类并更新器件顶点标记示意图，如图6所示，右边原标记为1的顶点更新成7。

[0062] 步骤(6)：检查收敛条件。此时收敛条件不满足，因为标记总数发生变化。转Setp3。

[0063] 步骤(7)：(迭代第二步)节点顶点聚类并更新标记。图7为根据本发明的一个实施例节点顶点聚类并更新节点顶点标记示意图，如图7所示，右下角原标记为3的顶点更新成8。

[0064] 步骤(8)：(迭代第二步)器件顶点聚类并更新标记。此时没有标记需要更新。

[0065] 步骤(9)：检查收敛条件。此时收敛条件已满足，转到步骤(10)。

[0066] 步骤(10)：重建并联子结构。统计各类中顶点的个数，将顶点个数为1的类的顶点标记为不连通，以此构建图的连通分量。将每个连通分量构建为一个并联子结构，且标记相同的顶点是并联子结构的对应点。如图7所示，每个相连的1‑5‑2‑7顶点集合构成一个并联子结构。

[0067] 本申请提供的重建电路并联子结构的方法，基于状态标记的方法，流程简单，能有效应用于在大规模电路中重建所有具有任意器件数、任意连接的并联子结构，从而提高电路约减率，提升仿真性能。

[0068] 本发明的一个实施例中，还提供一种电子设备，包括存储器和处理器，所述存储器上储存有在所述处理器上运行的计算机程序，所述处理器运行所述计算机程序时执行如上文所述的重建电路并联子结构的方法的步骤。

[0069] 本发明的一个实施例中，还提供一种计算机可读存储介质，其上存储有计算机程序，所述计算机程序运行时执行如上文所述的重建电路并联子结构的方法的步骤。

[0070] 本领域普通技术人员可以理解：以上所述仅为本发明的优选实施例而已，并不用于限制本发明，尽管参照前述实施例对本发明进行了详细的说明，对于本领域的技术人员来说，其依然可以对前述各实施例记载的技术方案进行修改，或者对其中部分技术特征进行等同替换。凡在本发明的精神和原则之内，所作的任何修改、等同替换、改进等，均应包含在本发明的保护范围之内。