JP7756590B2 - Function estimation method and function estimation program - Google Patents

Description

This disclosure relates to a function estimation method and program that uses a GNN (Graph Neural Network), a network with a graph structure, to perform function estimation based on a netlist used in the logic design of an LSI.

As a design technology for semiconductor integrated circuits (hereafter referred to as LSIs), hardware description languages (HDLs) are sometimes used, as they are highly efficient in development and are not tied to semiconductor vendors.

In this case, logic synthesis is used to automatically convert a circuit design created using HDL into a netlist that describes the connections between components to be implemented in the circuit. The HDL description level at which logic synthesis is possible is called the register transfer level (RTL).

In response to this, there is a demand for extracting functions implemented in netlists or converting netlists to RTL, with the aim of utilizing past design assets for which RTL does not exist. However, there is no established technology to automatically abstract and convert the descriptions of netlists, which differ from one semiconductor vendor to another, rather than simply converting the language, and so netlists have mainly been interpreted manually, referring to documentation.

To address this issue, there is a method for estimating functions implemented in RTL (see, for example, Patent Document 1). Patent Document 1 introduces a method that uses a neural network (hereafter referred to as NN) to learn a judgment function, then estimates the function and replaces the circuit data for matching functions.

However, Patent Document 1 focuses on the estimation of functions learned as conversion rules and circuit replacement. Therefore, there is no mechanism for estimating functions that combine learned functions. As a result, it is necessary to manually train each function that needs to be judged.

To solve these problems, the present applicant has proposed a function estimation method and program that can efficiently perform function estimation on LSI netlists (see, for example, Patent Document 2).

Japanese Unexamined Patent Publication No. 4-199369 Japanese Patent Application Laid-Open No. 2021-89722

Patent document 2 proposes a circuit function estimation method that graphs gate-level netlists and inputs them into an R-GCN, achieving function estimation for combinational circuits composed of simple arithmetic operation functions such as adders, subtractors, multipliers, and multiplexers.

Here, R-GCN (Relational Graph Convolutional Network) is a type of GNN, a type of convolutional neural network model that targets graph structures made up of nodes and edges, and is characterized by its ability to accept directed graphs as input.

However, with regard to the technique described in Patent Document 2, it is desirable to improve the estimation performance so that function estimation can be performed on more complex circuits.

The present disclosure has been made to solve these problems, and aims to provide a function estimation method and function estimation program that can improve the generalizability of function estimation for LSI netlists compared to conventional techniques.

A function estimation method according to the present disclosure is a function estimation method executed by a computer to estimate a function based on a netlist used in the logic design of an LSI using a GNN, which is a network having a graph structure, and includes a first estimation step of performing a first function estimation by using a first GNN based on the netlist, and a second estimation step of performing a second function estimation by using a second GNN based on the estimation result of the first estimation step, wherein the second estimation step performs clustering on each node of an output graph that is the estimation result of the first estimation step, generates a matrix representing the type of each node after clustering as input data for the second GNN, and performs the second function estimation, and the first estimation step includes a first step of generating a graphed netlist by converting the netlist into a graph representation consisting of nodes and edges, a feature matrix representing the type of each node in the graphed netlist, and a feature matrix representing the type of each node in the netlist. the second step of generating an adjacency matrix that expresses the connection relationships at each node; a third step of inputting the feature matrix and the adjacency matrix into a first GNN and executing a calculation using the connection relationships between the nodes and edges to perform a first function estimation, and generating, as an estimation result, an output graph that reflects the node classification according to the result of the first function estimation for each node in the graphed netlist; the second estimation process includes a fourth step of clustering each node in the output graph that is the estimation result, and generating, as input data to be input to the second GNN, a new feature matrix that expresses the type of each node after clustering and a new adjacency matrix that expresses the connection relationships at each node after clustering; and a fifth step of inputting the new feature matrix and new adjacency matrix into the second GNN and executing a calculation using the connection relationships between the nodes and edges after clustering to perform a second function estimation .
Further, a function estimation method according to the present disclosure is a function estimation method executed by a computer to estimate a function based on a netlist used in the logic design of an LSI using a GNN, which is a network having a graph structure, and includes a first estimation step of performing a first function estimation by using a first GNN based on the netlist, and a second estimation step of performing a second function estimation by using a second GNN based on the estimation result of the first estimation step, in which the second estimation step performs clustering for each node of an output graph, which is the estimation result of the first estimation step, generates a matrix representing the type of each node after clustering as input data for the second GNN, performs the second function estimation, and estimates the function by using an R-GC, which is a network in which the graph structure is folded as the GNN. When N is used, the first estimation step of performing the first function estimation by using the first R-GCN as the first GNN based on the netlist includes a first step of generating a graphed netlist by converting the netlist into a graph representation consisting of nodes and edges, a second step of generating a feature matrix representing the type of each node in the graphed netlist and three types of adjacency matrices representing the connection relationships and input/output relationships at each node in the netlist, and a second step of inputting the feature matrix and the three types of adjacency matrices to the first R-GCN and performing a graph convolution operation using the connection relationships of the nodes and edges to perform the first function estimation, and a second step of generating a graph representation of each node in the graphed netlist by reflecting the node classification according to the result of the first function estimation. The second estimation step performs a second function estimation by using a second R-GCN as a second GNN based on the estimation result of the first estimation step, and includes a fourth step of clustering each node of the output graph, which is the estimation result, and generating, as input data to be input to the second R-GCN, a new feature matrix representing the type of each node after clustering and three new types of adjacency matrices representing the connection relationships and input/output relationships of each node after clustering; and a fifth step of inputting the new feature matrix and the new three types of adjacency matrices to the second R-GCN and performing a graph convolution operation using the connection relationships of the nodes and edges after clustering, thereby performing the second function estimation. The three types of adjacency matrices generated in the second step are composed of a first adjacency matrix indicating the connection relationships regarding inputs between nodes at each node in the graphed netlist, a second adjacency matrix indicating a unit matrix with each node in the graphed netlist as an element, and a third adjacency matrix indicating the connection relationships regarding outputs between nodes at each node in the graphed netlist, and the three new types of adjacency matrices generated in the fifth step are composed of a new first adjacency matrix indicating the connection relationships regarding inputs between nodes at each node after clustering, a new second adjacency matrix indicating a unit matrix with each node after clustering as an element, and a new third adjacency matrix indicating the connection relationships regarding outputs between nodes at each node after clustering.
Furthermore, a function estimation method according to the present disclosure is a function estimation method executed by a computer to estimate a function based on a netlist used in the logic design of an LSI using a GNN, which is a network having a graph structure, and includes a first estimation step of performing a first function estimation by using a first GNN based on the netlist, and a second estimation step of performing a second function estimation by using a second GNN based on the estimation result of the first estimation step, in which the second estimation step performs clustering on each node of an output graph that is the estimation result of the first estimation step, generates a matrix representing the type of each node after clustering as input data for the second GNN, and performs the second function estimation, in which the computer estimates an arithmetic operation function included in the netlist as the first function estimation, and in the second estimation step estimates a circuit function of a higher hierarchy as the second function estimation based on the estimation result of the arithmetic operation function.

The function estimation program according to the present disclosure is a function estimation program executed by a computer to estimate functions based on a netlist used in the logic design of an LSI using a GNN, which is a network having a graph structure, and causes the computer to function as a first estimation means that performs a first function estimation by using a first GNN based on the netlist, and a second estimation means that performs a second function estimation by using a second GNN based on the estimation result of the first estimation means. The first estimation means performs a first step of generating a graphed netlist by converting the netlist into a graph representation consisting of nodes and edges, a second step of generating a feature matrix that represents the type of each node in the graphed netlist and an adjacency matrix that represents the connection relationships at each node in the netlist, and a second step of generating a feature matrix and an adjacency matrix that represents the connection relationships at each node in the netlist. The second estimation means has a fourth step of clustering each node in the output graph, which is the estimation result, and generating, as input data to be input to the second GNN, a new feature matrix that expresses the type of each node after clustering and a new adjacency matrix that expresses the connectivity of each node after clustering; and a fifth step of inputting the new feature matrix and new adjacency matrix to the second GNN and executing a calculation using the connectivity of the nodes and edges after clustering, thereby performing a second function estimation.

This disclosure provides a function estimation method and program that can improve the generalizability of function estimation for LSI netlists compared to conventional techniques.

FIG. 2 is an explanatory diagram showing a processing flow of a function estimation method according to the first embodiment of the present disclosure. 1A to 1C are diagrams illustrating overall flows of two processing steps according to a function estimation method according to a first embodiment of the present disclosure. FIG. 10 is an explanatory diagram showing input, processing, and output related to R-GCN2 when two R-GCNs are connected in series in the first embodiment of the present disclosure. FIG. 10 is an explanatory diagram showing the merits of estimation accuracy when two R-GCNs are connected in series in the first embodiment of the present disclosure. FIG. 10 is an explanatory diagram showing a method for generating an input graph that serves as the basis for a matrix used in R-GCN2 when an instance is present in the first embodiment of the present disclosure. FIG. 10 is an explanatory diagram showing an image of taking a majority vote within each instance for the estimation results obtained by node classification using R-GCN1 in the first embodiment of the present disclosure. FIG. 10 is an explanatory diagram showing a method for generating an instance matrix S prior to calculating a new adjacency matrix A′ in the first embodiment of the present disclosure. FIG. 10 is an explanatory diagram showing a method for generating a new adjacency matrix A′ using an instance matrix S in the first embodiment of the present disclosure. FIG. 10 is an explanatory diagram showing a method for generating a new feature matrix X′ from a clustered graph in the first embodiment of the present disclosure. FIG. 10 is an explanatory diagram showing a method for generating a new correct matrix Y′ from the application of a circuit shown in a graph after clustering in the first embodiment of the present disclosure. FIG. 10 is an explanatory diagram showing a method for generating an input graph for R-GCN2 when there is no instance in the first embodiment of the present disclosure. FIG. 10 is an explanatory diagram relating to a merge process according to the first embodiment of the present disclosure. FIG. 1 is a diagram illustrating a first specific example of a connection configuration according to the first embodiment of the present disclosure. FIG. 10 is a diagram illustrating a second specific example of a connection configuration according to the first embodiment of the present disclosure.

Preferred embodiments of the function estimation method and function estimation program of the present disclosure are described below with reference to the accompanying drawings. This disclosure relates to deep learning technology that handles graphs in general, and is characterized by performing classification at the node level in a GNN.

In the following first embodiment, a function estimation method executed by a computer is described, using an R-GCN as a GCN, a network with a folded graph structure, as a specific example of a GNN, to estimate functions based on a netlist used in LSI logic design. This disclosure, in particular, provides a method for using the results of function estimation in a previous stage to perform further function estimation in a later stage, thereby improving the generalizability of function estimation for LSI netlists.

Embodiment 1.
1 is an explanatory diagram showing a processing flow of a function estimation method according to a first embodiment of the present disclosure. A function estimation method for an application netlist using an R-GCN according to the first embodiment will be described with reference to FIG. 1. FIG. 1 shows a series of steps from an application netlist to finally estimating the function of the application.

As shown in FIG. 1, the function estimation method according to the first embodiment can be broadly divided into a first estimation process 10 and a second estimation process 20 that uses the estimation results from the first estimation process 10. The first estimation process 10 performs a first function estimation by using a first R-GCN based on a netlist. More specifically, the first estimation process 10 includes the following steps:

First step: generating a graphed netlist by converting the netlist into a graph representation consisting of nodes and edges.
Second step: A step of generating a feature matrix that represents the type of each node in the graphed netlist, and three types of adjacency matrices that represent the connection relationships and input/output relationships at each node in the netlist.

Third step: Input the feature matrix and three types of adjacency matrices into the first R-GCN, and perform a graph convolution operation using the node and edge connectivity relationships to perform a first function estimation, generating an output graph as an estimation result that reflects the node classification based on the results of the first function estimation for each node in the graphed netlist.

The detailed processing content of this first estimation step 10 is disclosed in Patent Document 2, and a detailed explanation will be omitted here.

The second estimation process 20 performs a second function estimation using a second R-GCN based on the estimation results of the first estimation process 10. This second estimation process 20 is a new process added in this disclosure to improve the generalizability of function estimation, and includes the following steps:

Fourth step: A step of performing clustering for each node of the output graph, which is the estimation result, and generating a new feature matrix and three new adjacency matrices as input data to be input to the second R-GCN.
Fifth step: A step of performing second function estimation by inputting the new feature matrix and the new three types of adjacency matrices into a second R-GCN and performing a graph convolution operation using the node and edge connectivity relationships after clustering.

The new feature matrix is a matrix that represents the type of each node after clustering, and the three new adjacency matrices are matrices that represent the connection relationships and input/output relationships of each node after clustering; details will be given later.

Figure 1 illustrates an example in which, in the first estimation process 10, arithmetic operation functions included in the netlist are estimated as the first function estimation, and in the second estimation process 20, application functions as higher-level circuit functions are estimated as the second function estimation based on the results of arithmetic operation function estimation. Note that the functions estimated in the first estimation process 10 and the functions estimated in the second estimation process 20 are not limited to this example.

Figure 2 is a diagram showing the overall flow of two different processing flows using the function estimation method according to embodiment 1 of the present disclosure. Note that in Figures 1 and 2, the notation R-GCN1 refers to the first R-GCN used in the first estimation process 10, and the notation R-GCN2 refers to the second R-GCN used in the second estimation process 20.

According to the function estimation method of the first embodiment shown in Figures 1 and 2, by connecting multiple R-GCNs in series, it is possible to perform function estimation for more complex and large-scale LSI netlists, which was not possible with conventional technology.

Note that Figure 2 shows two processing flows for connecting R-GCN1 and R-GCN2 in series: with and without instances. Here, "with instances" means that functions have already been separated into modules. In other words, the clustering process simply determines boundaries according to the instance names written in the gate-level netlist.

On the other hand, no instances means that functions are not separated into modules. Therefore, it is not possible to determine the boundaries of functions just by looking at the netlist.

The function estimation method according to the first embodiment is characterized by automatically determining the boundaries of functions (clustering) when the estimation results of the preceding R-GCN1 are input to the succeeding R-GCN2. Therefore, we will first explain the advantages of connecting two R-GCNs in series, and then explain a series of processes including clustering when instances are present, and a series of processes including clustering when instances are not present.

<Advantages of connecting two R-GCNs in series>
3A and 3B are explanatory diagrams showing the input, processing, and output of the R-GCN2 when two R-GCNs are connected in series in the first embodiment of the present disclosure. Fig. 3A shows the state after conversion processing into an input graph to the R-GCN2 by applying clustering to the results of the estimation of the arithmetic operation function by the R-GCN1 in the first stage. Details of this conversion processing will be described later.

Figure 3(A) shows the input graph obtained by clustering the three arithmetic operation functions ADD, MUL, and FF estimated by the first-stage R-GCN1. Specifically, the clustering results are summarized into 13 nodes and their connections.

Figure 3(B) shows the state in which the input graph shown in Figure 3(A) is input to the second-stage R-GCN2, application functions are estimated as circuit functions in the upper layer based on the results of the arithmetic operation function estimation, and Result2 is obtained as the output. Specifically, it shows the state in which FIR, IIR, and FFT are estimated as three application functions for 13 nodes.

Figure 3(C) shows the state in which a majority vote is taken for the 13 nodes in Result 2 shown in Figure 3(B), resulting in FIR being the estimated circuit function for the upper layer.

As shown in Figure 3, connecting two R-GCNs in series has the advantage of enabling hierarchical function estimation. Furthermore, connecting R-GCNs in series also has the advantage of improving estimation accuracy, as will be explained using Figure 4.

Figure 4 is an explanatory diagram showing the advantages in terms of estimation accuracy when two R-GCNs are connected in series in embodiment 1 of the present disclosure. Figure 4(A) shows Result 1, which is the estimation result by R-GCN1 in the first stage. Figure 4(B) also shows the results of clustering Result 1 shown in Figure 4(A).

Figure 4(B) shows an example where, of the 13 nodes, node n1 is originally MUL but is clustered as ADD, and node n2 is originally ADD but is clustered as MUL, resulting in two incorrectly determined input graphs.

Figure 4(C) shows Result2, which is the estimation result obtained by the second-stage R-GCN2 using the input graph of 13 nodes in Result1 after clustering shown in Figure 4(B) as input. Specifically, it shows the state in which Result2 is obtained as the estimation result by performing learning by the second-stage R-GCN2 for each misclassified result included in the input graph.

As shown in Figure 4, the estimation result (Result 1) in the first stage contained some misjudgments in the estimation of arithmetic operation functions such as MUL and ADD. However, by learning these misjudgments in the R-GCN2 in the second stage, it is expected that the accuracy of the final estimation of application functions will improve.

In other words, by linking the output of each layer with the label in the higher layer, it is possible to take into account the quirks of the function estimation method used in the first stage and train it in the second stage. As a result, by connecting R-GCNs in multiple stages in series, even if the estimation result in the previous stage is incorrect, the incorrect result can be used as training data in the subsequent stage, making it possible to improve accuracy end-to-end.

<Regarding the series of processes in the second estimation step when there are instances>
Next, a detailed description will be given of the second estimation step 20, which performs a second function estimation using the R-GCN 2 based on the estimation result of the first estimation step 10 using the R-GCN 1 when an instance is present.

Figure 5 is an explanatory diagram showing a method for generating an input graph that serves as the basis for the matrix used in R-GCN2 when instances are present, in embodiment 1 of the present disclosure. Figure 5(A) shows a gate-level netlist in which the range of each arithmetic operation circuit is written as an instance name.

Figure 5(B) shows the state in which logic gates are classified into seven instances as nodes based on the instance names in the netlist. Specifically, Figure 5(B) shows that the seven circuits FF1, FF2, MUL1, MUL2, MUL3, ADD1, and ADD2 are estimated as instances as the estimation results of R-GCN1, and each instance contains multiple nodes as logic gates.

Figure 5(C) shows the state in which an input graph with arithmetic operation circuits as nodes is obtained by performing clustering on the estimation results by R-GCN1 shown in Figure 5(B). Specifically, Figure 5(C) shows an input graph clustered into seven nodes consisting of two FFs, three MULs, and two ADDs.

Note that the nodes contained within each instance in Figure 5(B) are not necessarily unified into a single type. Therefore, by taking a majority vote regarding the nodes classified within each instance and assigning the same classification to all nodes within each instance, the input graph shown in Figure 5(C) can be obtained.

The concept of taking a majority vote will now be explained using Figure 6. Figure 6 is an explanatory diagram showing the concept of taking a majority vote within each instance for the estimation results obtained by node classification using R-GCN1 in embodiment 1 of the present disclosure.

Figure 6(A) shows that the nodes are classified into five circuits, ADD1, ADD2, MUL1, SUB1, and FF1, based on the instance names listed in the netlist. Of the three nodes classified as MUL1, nodes 3 to 5, nodes 3 and 4 are estimated as MUL, and node 5 is estimated as ADD.

Figure 6(B) shows that node 5 has changed from ADD to MUL by taking a majority vote among the three nodes classified as instance MUL1. By performing this majority vote process, the nodes within each instance in the estimation results classified by R-GCN1 are unified as a single arithmetic operation with the same function.

Next, we will explain how to generate the three matrices used in R-GCN2: the new adjacency matrix A', the new feature matrix X', and the new correct answer matrix Y'. Here, we will explain as a specific example the case where the three matrices are generated based on the graph after the majority voting process shown in Figure 6(B) above.

Figure 7 is an explanatory diagram showing a method for generating an instance matrix S as a precursor to calculating a new adjacency matrix A' in embodiment 1 of the present disclosure. Here, the instance matrix S corresponds to a matrix that describes the instance to which each node belongs. Figure 7(A) shows the graph after the majority voting process shown in Figure 6(B) above. Specifically, the graph shows a total of nine nodes classified for five instances: ADD1, ADD2, MUL1, SUB1, and FF1.

Figure 7(B) shows an instance matrix S with five instances in the columns and nine nodes in the rows. For example, ADD1 contains nodes 1 and 2, so in the first column of instance matrix S, the first and second rows are set to 1, and the other rows are set to 0.

Next, a method for generating a new adjacency matrix A' will be described. FIG. 8 is an explanatory diagram showing a method for generating a new adjacency matrix A' using the instance matrix S in the first embodiment of the present disclosure. In FIG. 8(A), the output side adjacency matrix Aout used in the R-GCN1 in the first stage and the instance matrix S shown in FIG. 7(B) are used to generate a new adjacency matrix A'.
S ^T × A out × S
The method for obtaining new adjacency matrices Aout', Ain', and Aown' based on the matrices obtained as a result of the calculation of (a) above is shown. Here, the new adjacency matrix Ain' corresponds to a new first adjacency matrix, the new adjacency matrix Aown' corresponds to a new second adjacency matrix, and the new adjacency matrix Aout' corresponds to a new third adjacency matrix.

8A, the matrix obtained as a result of the operation S ^T ×Aout ×S is rewritten so that the diagonal elements are set to 0 and all non-diagonal elements other than 0 are set to 1, thereby generating a new adjacent matrix Aout'. Furthermore, the new adjacent matrix Ain' is generated by transposing the new adjacent matrix Aout'. Furthermore, the new adjacent matrix Aown' is generated by setting only the diagonal elements to 1, thereby generating a unit matrix.

Figure 8(B) shows the graph after the majority voting process shown in Figure 6(B) and Figure 7(A). Also, Figure 8(C) shows the state in which a graph obtained after clustering from the graph in Figure 8(B) corresponds to the new adjacency matrix Aout', new adjacency matrix Ain', and new adjacency matrix Aown' shown in Figure 8(A). In this way, by performing the processes shown in Figures 7 and 8, a new adjacency matrix A' consisting of the three matrices, new adjacency matrix Aout', new adjacency matrix Ain', and new adjacency matrix Aown', is generated.

Next, a method for generating a new feature matrix X' will be described. Figure 9 is an explanatory diagram showing a method for generating a new feature matrix X' from a graph after clustering in embodiment 1 of the present disclosure. Figure 9 (A) shows the graph after clustering shown in Figure 8 (C) above.

Figure 9(B) shows the state in which new feature matrix X' has been generated from the clustered graph shown in Figure 9(A). Specifically, the columns are the five arithmetic operations ADD, SUB, MUL, MUX, and FF, and the rows are the five nodes in the clustered graph, Node 1' to Node 5', and new feature matrix X' is generated by setting 1 to the elements corresponding to the clustered graph shown in Figure 9(A).

Next, we will explain the method for generating the correct matrix Y'. Figure 10 is an explanatory diagram showing the method for generating a new correct matrix Y' from the application of the circuit shown in the graph after clustering in embodiment 1 of the present disclosure. Figure 10 (A) shows the graph after clustering shown in Figure 8 (C) above.

Figure 10(B) shows the state in which a new correct matrix Y' has been generated as an FIR from the application of the circuit shown in the graph after clustering in Figure 9(A). The specific method for generating the new correct matrix Y' is disclosed in Patent Document 2, and a detailed description will be omitted here.

As described above, the computer can execute the second estimation step in the case where instances are present by executing the series of processes described using Figures 5 to 10. Specifically, based on the estimation results from the first estimation step 10, a new feature matrix X' and three new adjacency matrices Aout', Ain', and Aown' are input to the second R-GCN, and a graph convolution operation is performed using the connection relationships between nodes and edges after clustering, thereby enabling second function estimation.

<Regarding the series of processes in the second estimation step when there are no instances>
Next, a detailed description will be given of the second estimation step 20, which performs a second function estimation using the R-GCN 2 based on the estimation result of the first estimation step 10 using the R-GCN 1 in the case where there is no instance.

When there are no instances, clustering processing is performed based on the output graph, which is the node classification result obtained by R-GCN1, to generate an input graph that serves as input for R-GCN2. Based on the input graph, three matrices used by R-GCN2 are generated: new adjacency matrix A', new feature matrix X', and new correct answer matrix Y'. In other words, new adjacency matrix A', new feature matrix X', and new correct answer matrix Y' are generated as matrices that represent the types of each node after clustering.

Figure 11 is an explanatory diagram showing a method for generating an input graph for R-GCN2 when there are no instances in embodiment 1 of the present disclosure. Note that in Figure 11, for simplicity of explanation, the nodes are shown as an undirected graph, but the smoothing and merging processes described below can also be applied to directed graphs.

To generate an input graph for R-GCN2 when there are no instances, a smoothing process is performed as preprocessing on the output graph, which is the node classification result obtained by R-GCN1, and then a clustering process is performed on the graph after the smoothing process.

Figure 11(A) shows an example of an output graph that is the node classification result obtained by R-GCN1, showing that 12 nodes are classified into one of four types of arithmetic operations. Furthermore, in Figure 11(A), three nodes n1 to n3, which have a different arithmetic operation from any of their neighboring nodes and are classified as isolated arithmetic operations, are identified as isolated nodes by using squares.

Fig. 11B shows the graph after smoothing processing has been performed on the three isolated nodes included in the graph shown in Fig. 11A. The smoothing processing corresponds to a process of removing isolated nodes based on a comparison of the functions of adjacent nodes, and is performed according to the following two rules 1 and 2.
Rule 1: By taking a majority vote on the classification results of the nodes adjacent to itself, the classification of the isolated node is rewritten to the most popular classification, thereby performing smoothing.
Rule 2: If the rule does not allow a single classification having the same function to be identified by majority vote, the classification of the isolated node will remain as it is.

In Figure 11 (B), rule 1 holds for node n1, so a smoothing process is performed to rewrite the node classification, but rule 2 holds for nodes n2 and n3, so the node classification remains unchanged.

11C shows the graph after the smoothing process shown in FIG. 11B has been performed and the merge process has been performed on the nodes having the same function. The merge process is performed in accordance with Rule 3 below.
Rule 3: Adjacent nodes that are classified into the same function are merged.

In Figure 11(C), the 12 nodes after the smoothing process in Figure 11(B) are merged according to Rule 3, resulting in a graph consisting of 6 nodes.

The merge process will be further explained using Figure 12. Figure 12 is an explanatory diagram of the merge process in embodiment 1 of the present disclosure. The merge process is performed according to steps 1 to 4 below.

Step 1: Find one pair of adjacent nodes that have the same classification.
Step 2: Add one equivalent node to one node pair having the same classification found in step 1, and add a connection relationship with an adjacent node in one node pair having the same classification.
Step 3: Delete one node pair having the same classification obtained in step 1.
Step 4: Repeat steps 1 to 3 for adjacent nodes until there are no more node pairs with the same classification.

Figure 12(A) shows an example of an output graph, which is the node classification result obtained by R-GCN1, similar to the graph shown in Figure 11(A) above, with the numbers 1 through 12 added to identify the 12 nodes. Furthermore, Figure 12(A) shows the case where, by performing procedure 1, node 1 and node 2 are determined to be a node pair with the same classification.

Figure 12(B) shows the state in which step 2 has been executed, resulting in the addition of node 1', which is equivalent to the node pair.

Figure 12(C) shows the state in which step 3 is performed, resulting in the deletion of the node pair with the same classification, node 1 and node 2, and their replacement with node 1'.

Figure 12(D) shows the final state, where the merge process of steps 1 to 3 is repeated according to step 4, resulting in six nodes, which is the same as the graph shown in Figure 11(C).

As a result of repeating steps 1 to 4, as shown in Figure 12(D), nodes 1 to 4 are merged as node 4', nodes 5 and 6 are merged as node 6', nodes 7 and 8 are merged as node 7', and nodes 9 and 10 are merged as node 9'. However, nodes 11 and 12 remain as they are because they do not form a node pair with the same classification as their adjacent nodes.

As described above, according to the first embodiment, a first function estimation is performed using a first R-GCN in the first estimation step, which is the first stage, and a second function estimation is performed using a second R-GCN in the second estimation step, which is the subsequent stage, based on the estimation results of the first estimation step. This configuration makes it possible to estimate circuit functions at higher levels, thereby achieving hierarchical function estimation.

Furthermore, by linking the output of each layer with the label in the higher layer, it is possible to take into account the quirks of the function estimation method used in the first stage and train it in the second stage. In other words, by adopting a configuration in which R-GCNs are connected in series in multiple stages, even if the estimation result in the first stage is incorrect, the incorrect result can be used as training data in the subsequent stage, thereby improving accuracy in an end-to-end manner.

In other words, by connecting multiple R-GCNs in series, it becomes possible to perform functional estimation of more complex and large-scale LSI netlists, which was not possible with conventional technology.

Furthermore, according to the function estimation method disclosed herein, clustering processing can be performed on the estimation results from the first estimation step, both when there are instances whose cluster boundaries are known from the netlist, and when there are no instances whose cluster boundaries are unknown from the netlist. In particular, even when there are no instances, it is possible to automatically determine the boundaries of functions based on the output graph from the previous stage and perform clustering.

Therefore, according to the first embodiment, it is possible to realize a function estimation method and a function estimation program that can improve the generalizability of function estimation for LSI netlists compared to conventional techniques.

Note that, in the above-described first embodiment, a two-tier connection configuration in which two R-GCNs are connected in series was described, but the function estimation method and function estimation program according to the present disclosure are not limited to a two-tier connection configuration. Figure 13 is a diagram showing a first specific example of a connection configuration according to the first embodiment of the present disclosure.

Figure 13 shows an example of a serial connection configuration when two layers are expanded to n layers (three or more layers). The specific example shown in Figure 13 has an n-layer configuration in which layers 1 to n are stacked in order. When i is an integer greater than or equal to two, creating an input data set for the i-th layer R-GCN from the output of the (i-1)-th layer R-GCN can achieve the same effect as that obtained with a two-layer connection configuration.

Figure 14 is a diagram showing a second specific example of a connection configuration according to the first embodiment of the present disclosure. As shown in Figure 14, even when a series-parallel configuration is adopted in which multiple hierarchical series connection configurations are connected in parallel, it is possible to achieve the same effect as that obtained with the two-tier connection configuration.

In addition, in the above-mentioned first embodiment, a function estimation method including a first estimation step and a second estimation step was described in detail, but it is also possible to realize a function estimation program that causes a computer to function as a first estimation means that performs a first function estimation by using a first R-GCN based on a netlist, and a second estimation means that performs a second function estimation by using a second R-GCN based on the estimation result of the first estimation means.

Furthermore, in the above-described first embodiment, a specific example was described in which an R-GCN is used as a GCN, which is a network with a folded graph structure. However, the present disclosure is applicable to deep learning in general that deals with graphs, and is characterized by performing classification at the node level in a GNN, which is a higher-level concept that includes a GCN.

10 First estimation step, 20 Second estimation step, S Instance matrix, Ain' New adjacency matrix (new first adjacency matrix), Aown' New adjacency matrix (new second adjacency matrix), Aout' New adjacency matrix (new third adjacency matrix).

Claims (9)

A function estimation method executed by a computer for estimating a function based on a netlist used in an LSI logic design using a GNN, which is a network having a graph structure, comprising:
a first estimation step of performing a first function estimation by using a first GNN based on the netlist;
a second estimation step of performing a second function estimation by using a second GNN based on the estimation result of the first estimation step,
The second estimation step
Clustering is performed on each node of the output graph that is the estimation result of the first estimation step, a matrix representing the type of each node after clustering is generated as input data for the second GNN, and the second function estimation is performed;
The first estimation step includes:
a first step of generating a graphed netlist by converting the netlist into a graph representation consisting of nodes and edges;
a second step of generating a feature matrix representing the type of each node in the graphed netlist and an adjacency matrix representing the connection relationship of each node in the netlist;
a third step of inputting the feature matrix and the adjacency matrix into the first GNN, and executing a calculation using the connection relationships between the nodes and the edges to execute the first function estimation, and generating, as the estimation result, an output graph that reflects node classification according to the result of the first function estimation for each node in the graphed netlist;
and
The second estimation step
A fourth step of performing clustering on each node of the output graph, which is the estimation result, and generating, as the input data to be input to the second GNN, a new feature matrix representing the type of each node after clustering and a new adjacency matrix representing the connection relationship of each node after clustering;
a fifth step of inputting the new feature matrix and the new adjacency matrix into the second GNN and performing an operation using the connection relationships of the nodes and edges after clustering, thereby performing the second function estimation;
A function estimation method having the following. When the boundaries of the clusters are known from the netlist, the computer:
In the fourth step,
2. The function estimation method according to claim 1, wherein the clustering is performed by assigning the same classification to all nodes in each cluster by taking a majority vote of the estimation results of each node for each cluster based on the netlist for the node classification results of the output graph, thereby generating the new adjacency matrix, and generating a new feature matrix expressing the type of each node in the matrix. If the boundaries of the clusters are unknown from the netlist, the computer:
In the fourth step,
For each node in the output graph, perform a smoothing process that removes isolated nodes based on a functional comparison of adjacent nodes;
The clustering is performed by performing a merge process on adjacent nodes with the same function for each node of the output graph after the smoothing process is performed;
The function estimation method according to claim 1 , further comprising generating the new feature matrix representing the type of each node after the clustering, and the new adjacency matrix representing the connection relationship of each node after the clustering. A function estimation method executed by a computer for estimating a function based on a netlist used in an LSI logic design using a GNN, which is a network having a graph structure, comprising:
a first estimation step of performing a first function estimation by using a first GNN based on the netlist;
a second estimation step of performing a second function estimation by using a second GNN based on the estimation result of the first estimation step,
The second estimation step
Clustering is performed on each node of the output graph that is the estimation result of the first estimation step, a matrix representing the type of each node after clustering is generated as input data for the second GNN, and the second function estimation is performed;
When an R-GCN, which is a network with a folded graph structure, is used as the GNN,
The first estimation step of performing the first function estimation by using a first R-GCN as the first GNN based on the netlist includes:
a first step of generating a graphed netlist by converting the netlist into a graph representation consisting of nodes and edges;
a second step of generating a feature matrix representing the type of each node in the graphed netlist, and three types of adjacency matrices representing the connection relationships and input/output relationships of each node in the netlist;
a third step of inputting the feature matrix and the three types of adjacency matrices into the first R-GCN, and executing a graph convolution operation using the connection relationships between the nodes and the edges to execute the first function estimation, and generating an output graph as the estimation result, which reflects node classification according to the result of the first function estimation for each node in the graphed netlist;
and
The second estimation step of performing the second function estimation by using a second R-GCN as the second GNN based on the estimation result of the first estimation step includes:
a fourth step of clustering each node of the output graph, which is the estimation result, and generating, as the input data to be input to the second R-GCN, a new feature matrix representing the type of each node after clustering and three new adjacency matrices representing the connection relationship and input/output relationship of each node after clustering;
a fifth step of inputting the new feature matrix and the new three types of adjacency matrices into the second R-GCN and performing a graph convolution operation using the connection relationships of the nodes and edges after clustering, thereby performing the second function estimation;
and
the three types of adjacency matrices generated in the second step are composed of a first adjacency matrix indicating a connection relationship between nodes in the graphed netlist with respect to inputs, a second adjacency matrix indicating an identity matrix with each node in the graphed netlist as an element, and a third adjacency matrix indicating a connection relationship between nodes in the graphed netlist with respect to outputs,
The three new adjacency matrices generated in the fifth step are composed of a new first adjacency matrix indicating the connection relationships between nodes regarding inputs at each node after the clustering, a new second adjacency matrix indicating an identity matrix with each node after the clustering as an element, and a new third adjacency matrix indicating the connection relationships between nodes regarding outputs at each node after the clustering.
Functional estimation methods. When the boundaries of the clusters are known from the netlist, the computer:
In the fourth step,
assigning the same classification to all nodes in each cluster by taking a majority vote of the estimation results of each node for each cluster based on the netlist for the node classification results of the output graph;
An instance matrix S describing the instances to which each node belongs is generated, and the third adjacency matrix Aout generated in the second step is used to calculate the following equation: S ^T ×Aout×S
The clustering is performed by generating a matrix according to
5. The function estimation method according to claim 4, further comprising: generating the new third adjacency matrix by setting diagonal elements to 0 and rewriting non-diagonal elements other than 0 to 1; generating the new first adjacency matrix by transposing the new third adjacency matrix; generating the new second adjacency matrix by setting all diagonal elements to 1 and all non-diagonal elements to 0 ; and generating a new feature matrix representing the type of each node in the matrix. If the boundaries of the clusters are unknown from the netlist, the computer:
In the fourth step,
For each node in the output graph, perform a smoothing process that removes isolated nodes based on a functional comparison of adjacent nodes;
The clustering is performed by performing a merge process on adjacent nodes with the same function for each node of the output graph after the smoothing process is performed;
The function estimation method according to claim 4 , further comprising generating the new feature matrix representing the type of each node after the clustering, and the new three types of adjacency matrices representing the connection relationships and input/output relationships of each node after the clustering. The computer
In the first estimation step, an arithmetic operation function included in the netlist is estimated as the first function estimation;
The function estimation method according to claim 1 , wherein in the second estimation step, a circuit function of an upper layer is estimated as the second estimated function based on a result of estimation of the arithmetic operation function. A function estimation method executed by a computer for estimating a function based on a netlist used in an LSI logic design using a GNN, which is a network having a graph structure, comprising:
a first estimation step of performing a first function estimation by using a first GNN based on the netlist;
a second estimation step of performing a second function estimation by using a second GNN based on the estimation result of the first estimation step,
The second estimation step
Clustering is performed on each node of the output graph that is the estimation result of the first estimation step, a matrix representing the type of each node after clustering is generated as input data for the second GNN, and the second function estimation is performed;
The computer
In the first estimation step, an arithmetic operation function included in the netlist is estimated as the first function estimation;
In the second estimation step, a circuit function of an upper layer is estimated as the second function estimation based on the estimation result of the arithmetic operation function.
Functional estimation methods. A function estimation program executed by a computer to estimate a function based on a netlist used in the logic design of an LSI using a GNN, which is a network having a graph structure, comprising:
a first estimation means for performing a first function estimation by using a first GNN based on the netlist;
a second estimation means for performing a second function estimation by using a second GNN based on the estimation result of the first estimation means;
The first estimation means
a first step of generating a graphed netlist by converting the netlist into a graph representation consisting of nodes and edges;
a second step of generating a feature matrix representing the type of each node in the graphed netlist and an adjacency matrix representing the connection relationship of each node in the netlist;
a third step of inputting the feature matrix and the adjacency matrix into the first GNN, and executing a calculation using the connection relationships between the nodes and the edges to execute the first function estimation, and generating, as the estimation result, an output graph that reflects node classification according to the result of the first function estimation for each node in the graphed netlist;
The second estimation means
A fourth step of clustering each node of the output graph, which is the estimation result, and generating a new feature matrix representing the type of each node after clustering and a new adjacency matrix representing the connection relationship of each node after clustering as input data to be input to the second GNN;
a fifth step of inputting the new feature matrix and the new adjacency matrix into the second GNN and performing an operation using the connection relationships of the nodes and edges after clustering, thereby performing the second function estimation.