公开(公告)号：US08788990B2

公开(公告)日：2014-07-22

申请号：US12604368

申请日：2009-10-22

Applicant: Douglas C. Meserve

Inventor： Douglas C. Meserve

IPC: G06F17/50

CPC classification number: G06F17/505

Abstract: Method, apparatus and system for finding instances of a pattern in a main netlist include reading in the main netlist and the pattern that is used for finding pattern matches in the main netlist. The main netlist and the pattern include a plurality of vertices. Each of the vertices is a device or a net. Labels for the vertices are computed in both the pattern and the main netlist up to a depth appropriate for the pattern. A vertex of the pattern is identified and used in matching with one or more vertices in the main netlist at the depth appropriate for the pattern using the computed labels. The computed labels for each of the vertices of the main netlist are stored for possible reuse in subsequent pattern matches.

Abstract translation: 用于查找主网表中的模式实例的方法，装置和系统包括在主网表中读取和用于在主网表中查找模式匹配的模式。 主网表和图案包括多个顶点。 每个顶点是设备或网络。 顶点的标签在图案和主网表中计算，直到适合于图案的深度。 在使用计算标签的适合于图案的深度处，识别并使用与主网表中的一个或多个顶点匹配的图案的顶点。 存储主网表的每个顶点的计算标签，以便在随后的模式匹配中可能重新使用。

公开(公告)号：US20100042964A1

公开(公告)日：2010-02-18

申请号：US12604368

申请日：2009-10-22

Applicant: Douglas C. Meserve

Inventor： Douglas C. Meserve

IPC: G06F17/50

CPC classification number: G06F17/505

Abstract: Method, apparatus and system for finding instances of a pattern in a main netlist include reading in the main netlist and the pattern that is used for finding pattern matches in the main netlist. The main netlist and the pattern include a plurality of vertices. Each of the vertices is a device or a net. Labels for the vertices are computed in both the pattern and the main netlist up to a depth appropriate for the pattern. A vertex of the pattern is identified and used in matching with one or more vertices in the main netlist at the depth appropriate for the pattern using the computed labels. The computed labels for each of the vertices of the main netlist are stored for possible reuse in subsequent pattern matches.

Abstract translation: 用于查找主网表中的模式实例的方法，装置和系统包括在主网表中读取和用于在主网表中查找模式匹配的模式。 主网表和图案包括多个顶点。 每个顶点是设备或网络。 顶点的标签在图案和主网表中计算，直到适合于图案的深度。 在使用计算标签的适合于图案的深度处，识别并使用与主网表中的一个或多个顶点匹配的图案的顶点。 存储主网表的每个顶点的计算标签，以便在随后的模式匹配中可能重新使用。

公开(公告)号：US07958468B2

公开(公告)日：2011-06-07

申请号：US12035409

申请日：2008-02-21

Applicant: Douglas C. Meserve

Inventor： Douglas C. Meserve

IPC: G06F17/50

CPC classification number: G06F17/5045 ,  G06F2217/66

Abstract: A method for indentifying instances of a smaller circuit in a larger circuit is disclosed. Both the smaller circuit and the larger circuit have a plurality of vertices. A vertex is one of a device or a net. The device, such a transistor, includes a Gate, a Drain, and a Source. The net is a wired connection between devices. In this method, one initial unique label is assigned to each of the plurality of vertices, each of a plurality of connection-types, power connection, and ground connection. A zero label is assigned to each of an input/output ports and a same initial unique label is assigned to same types of circuit components. Then each net is relabeled using labels of neighboring vertices. The neighboring vertices of a vertex are vertices that are directly connected to the vertex. Then, each device in the plurality of vertices is relabeled using labels of neighboring vertices excluding a label of a vertex that is connected to the Gate of the each device. The new labels of each vertex are stored in a data store and these labels are used in the calculation of the new labels of the vertices in a next iteration of relabeling.

Abstract translation: 公开了一种用于在较大电路中识别较小电路的实例的方法。 较小的电路和较大的电路都具有多个顶点。 顶点是设备或网络之一。 这种晶体管的器件包括门，排水和源。 网络是设备之间的有线连接。 在该方法中，将一个初始唯一标签分配给多个顶点中的每一个，多个连接类型，电源连接和接地连接中的每一个。 零标签被分配给每个输入/输出端口，并且相同的初始唯一标签被分配给相同类型的电路组件。 然后使用相邻顶点的标签重新标记每个网。 顶点的相邻顶点是直接连接到顶点的顶点。 然后，使用除了连接到每个设备的门的顶点的标签的相邻顶点的标签来重新标记多个顶点中的每个设备。 每个顶点的新标签存储在数据存储中，并且这些标签用于在下一次重新标记迭代中计算顶点的新标签。

公开(公告)号：US07861193B2

公开(公告)日：2010-12-28

申请号：US12035405

申请日：2008-02-21

Applicant: Douglas C. Meserve

Inventor： Douglas C. Meserve

IPC: G06F17/50

CPC classification number: G06F17/5045 ,  G06F2217/66

Abstract: A method for identifying instances of a smaller circuit in a larger circuit is provided. Both the smaller circuit and the larger circuit have a plurality of vertices. A vertex is one of a device or a net. The device, such a transistor, includes a Gate, a Drain, and a Source. The net is a wired connection between devices. The method includes recursively relabeling of each of the plurality of vertices until labels of all neighboring vertices of a selected vertex are zero. The neighboring vertices of a vertex are vertices that are directly connected to the vertex. Each successive iteration of the relabeling uses labels of each of the plurality of vertices after a previous iteration of the relabeling. Then, a recursive circuit tracing operation is performed.

Abstract translation: 提供了一种用于识别较大电路中较小电路的实例的方法。 较小的电路和较大的电路都具有多个顶点。 顶点是设备或网络之一。 这种晶体管的器件包括门，排水和源。 网络是设备之间的有线连接。 该方法包括递归地重新标记多个顶点中的每一个，直到所选顶点的所有相邻顶点的标号为零为止。 顶点的相邻顶点是直接连接到顶点的顶点。 重新标记的每个连续的迭代在重新标记的先前迭代之后使用多个顶点中的每一个的标签。 然后，执行递归电路跟踪操作。

公开(公告)号：US20090217214A1

公开(公告)日：2009-08-27

申请号：US12035409

申请日：2008-02-21

Applicant: Douglas C. Meserve

Inventor： Douglas C. Meserve

IPC: G06F17/50

CPC classification number: G06F17/5045 ,  G06F2217/66

Abstract: A method for indentifying instances of a smaller circuit in a larger circuit is disclosed. Both the smaller circuit and the larger circuit have a plurality of vertices. A vertex is one of a device or a net. The device, such a transistor, includes a Gate, a Drain, and a Source. The net is a wired connection between devices. In this method, one initial unique label is assigned to each of the plurality of vertices, each of a plurality of connection-types, power connection, and ground connection. A zero label is assigned to each of an input/output ports and a same initial unique label is assigned to same types of circuit components. Then each net is relabeled using labels of neighboring vertices. The neighboring vertices of a vertex are vertices that are directly connected to the vertex. Then, each device in the plurality of vertices is relabeled using labels of neighboring vertices excluding a label of a vertex that is connected to the Gate of the each device. The new labels of each vertex are stored in a data store and these labels are used in the calculation of the new labels of the vertices in a next iteration of relabeling.

Abstract translation: 公开了一种用于在较大电路中识别较小电路的实例的方法。 较小的电路和较大的电路都具有多个顶点。 顶点是设备或网络之一。 这种晶体管的器件包括门，排水和源。 网络是设备之间的有线连接。 在该方法中，将一个初始唯一标签分配给多个顶点中的每一个，多个连接类型，电源连接和接地连接中的每一个。 零标签被分配给每个输入/输出端口，并且相同的初始唯一标签被分配给相同类型的电路组件。 然后使用相邻顶点的标签重新标记每个网。 顶点的相邻顶点是直接连接到顶点的顶点。 然后，使用除了连接到每个设备的门的顶点的标签的相邻顶点的标签来重新标记多个顶点中的每个设备。 每个顶点的新标签存储在数据存储中，并且这些标签用于在下一次重新标记迭代中计算顶点的新标签。

公开(公告)号：US20090217213A1

公开(公告)日：2009-08-27

申请号：US12035405

申请日：2008-02-21

Applicant: Douglas C. Meserve

Inventor： Douglas C. Meserve

IPC: G06F17/50

CPC classification number: G06F17/5045 ,  G06F2217/66

Abstract: A method for indentifying instances of a smaller circuit in a larger circuit is disclosed. Both the smaller circuit and the larger circuit have a plurality of vertices. A vertex is one of a device or a net. The device, such a transistor, includes a Gate, a Drain, and a Source. The net is a wired connection between devices. The method includes recursively relabeling of each of the plurality of vertices until labels of all neighboring vertices of a selected vertex are zero. The neighboring vertices of a vertex are vertices that are directly connected to the vertex. Each successive iteration of the relabeling uses labels of each of the plurality of vertices after a previous iteration of the relabeling. Then, a recursive circuit tracing operation is performed starting from the selected vertex until each of the plurality of vertices in the smaller circuit is matched with one of the plurality of vertices in the larger circuit. The circuit tracing operation includes matching a label of each of the plurality of vertices neighboring the selected vertex in the smaller circuit with a label of each of the plurality of vertices in the larger circuit neighboring a vertex corresponding to the selected vertex, wherein labels at a same depth of relabeling iteration is matched.

Abstract translation: 公开了一种用于在较大电路中识别更小电路的实例的方法。 较小的电路和较大的电路都具有多个顶点。 顶点是设备或网络之一。 这种晶体管的器件包括门，排水和源。 网络是设备之间的有线连接。 该方法包括递归地重新标记多个顶点中的每一个，直到所选顶点的所有相邻顶点的标号为零为止。 顶点的相邻顶点是直接连接到顶点的顶点。 重新标记的每个连续的迭代在重新标记的先前迭代之后使用多个顶点中的每一个的标签。 然后，从所选择的顶点开始执行递归电路跟踪操作，直到较小电路中的多个顶点中的每个顶点与较大电路中的多个顶点中的一个顶点相匹配。 电路跟踪操作包括将较小电路中与所选择的顶点相邻的多个顶点中的每个顶点的标签与较大电路中的每个顶点的标签相邻，所述顶点与所选顶点相对应的顶点相邻，其中标记在 相同深度的重新标签迭代匹配。