JP7541902B2 - FUNCTION ESTIMATION METHOD, FUNCTION ESTIMATION DEVICE, AND FUNCTION ESTIMATION PROGRAM - Google Patents

Description

Article 30, paragraph 2 of the Patent Act is applicable. December 5, 2018: Disclosed at the Institute of Electronics, Information and Communication Engineers' VLSI Design Technology Study Group held at the Hiroshima Satellite Campus (1-5-3 Otemachi, Naka-ku, Hiroshima City, Hiroshima Prefecture)

Article 30, paragraph 2 of the Patent Act applies November 28, 2018 Website: https://www.ieice.org/ken/paper/20181205F1IC/ Published as "Study on netlist function estimation using graph convolution network" in the IEICE Technical Report of the Institute of Electronics, Information and Communication Engineers.

The present invention relates to the logical design of LSIs, and primarily relates to a function estimation method, a function estimation device, and a function estimation program that are equipped with built-in functions for generating design information and hardware language from a netlist.

As a design technique for semiconductor integrated circuits (hereafter referred to as LSIs), a Hardware Description Language (HDL) may be used, which is efficient in development and not limited to semiconductor vendors. In this case, logic synthesis is used to automatically convert the circuit design using HDL into a netlist that describes the connections between the components to be implemented in the circuit. Here, the HDL description level at which logic synthesis is possible is called the register transfer level (hereafter referred to as RTL).

In response to this, there is a demand to extract functions implemented in netlists or convert netlists to RTL, with the aim of utilizing past design assets for which RTL does not exist. However, technology has not yet been established to automatically abstract and convert descriptions, rather than simply converting the language, for the different netlists used by each semiconductor vendor, and so netlists are primarily read manually while referring to documentation.

To address this issue, there is a method for estimating the 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 of the matching function.

Japanese Unexamined Patent Publication No. 4-199369

However, in Patent Document 1, the focus is on estimating functions learned as conversion rules and circuit replacement. Therefore, there is no mechanism for estimating functions that are combinations of learned functions. Therefore, it is necessary to manually train each function to be judged.

The present invention has been made to solve the above-mentioned problems, and aims to provide a function estimation method, a function estimation device, and a function estimation program that can efficiently perform function estimation on an LSI netlist.

The function estimation method according to the present invention is a function estimation method executed on a computer to extract functions implemented in a netlist used in the logic design of an LSI using Graph Convolutional Networks (hereinafter referred to as GCN), which are networks with a folded graph structure, and includes a management process for constructing GCN class configuration information for the netlist from GCN configuration parameter information, and managing the GCN function labels held within each constructed GCN class and the GCN binary tree configuration that determines the GCN inference order during inference; a clustering process for converting the netlist into a graph representation composed of nodes and edges, and classifying the netlist according to the measured number of nodes and the constructed GCN class configuration information; a conversion process for performing a complementation process to match the number of nodes in each classified class; and a learning and inference process for learning and inferring functions based on the processing results of the management process and the conversion process.

The function estimation device according to the present invention is a function estimation device that uses a GCN, which is a network with a folded graph structure, to extract functions implemented in a netlist used in the logical design of an LSI. The device has a management unit that constructs GCN class configuration information for the netlist from parameter information for GCN configuration, and manages the GCN function labels held within each constructed GCN class and the GCN binary tree configuration that determines the GCN inference order during inference, a clustering unit that converts the netlist into a graph representation composed of nodes and edges, and performs classification according to the measured number of nodes and the constructed GCN class configuration information, a conversion unit that executes a complementation process to match the number of nodes in each classified class, and a learning and inference unit that learns and infers functions based on the processing results of the management unit and the conversion unit.

The function estimation program of the present invention is a function estimation program executed on a computer to extract functions implemented in a netlist used in the logic design of an LSI using a GCN, which is a network with a folded graph structure, and causes the computer to function as a management means for constructing GCN class configuration information of the netlist from GCN configuration parameter information, and for each constructed GCN class, managing the GCN function labels held within the class and the GCN binary tree configuration that determines the GCN inference order during inference, a clustering means for converting the netlist into a graph representation composed of nodes and edges, and classifying according to the measured number of nodes and the constructed GCN class configuration information, a conversion means for executing a complementation process to match the number of nodes in each classified class, and a learning and inference means for learning and inferring functions based on the processing results of the management means and the conversion means.

The present invention enables efficient function estimation even for large, complex netlists or netlists for which no documentation exists.

1 is a diagram showing a functional configuration of a program for estimating implemented functions for an LSI netlist according to the first embodiment of the present invention; 1 is a diagram showing a method for constructing a GCN class configuration based on the circuit scale of a netlist in the first embodiment of the present invention. FIG. 1 is a diagram showing a binary tree structure for determining the order of function determination during function estimation in a GCN in accordance with the first embodiment of the present invention. FIG. FIG. 2 is a diagram showing a netlist converted into a graph representation in the first embodiment of the present invention. 4 is a flowchart showing a series of processes executed by a GCN configuration management unit in the first embodiment of the present invention. 1 is a diagram showing differences in GCN class configurations based on GCN configuration parameter information in the first embodiment of the present invention. FIG. 11 is a flowchart showing a series of processes executed by a node number clustering unit in the first embodiment of the present invention. 4 is a flowchart showing a series of processes executed by a netlist matrix conversion unit in the first embodiment of the present invention. FIG. 4 is a diagram showing an example of conversion of a feature vector matrix X in the first embodiment of the present invention. FIG. 11 is a diagram showing an example of conversion of a connection matrix A in the first embodiment of the present invention. FIG. 11 is a diagram showing an example of conversion of a correct label matrix Y in the first embodiment of the present invention. 4 is a flowchart showing a series of processes executed by a learning/inference unit in the first embodiment of the present invention. FIG. 4 is a diagram showing an example of adding learning data in the first embodiment of the present invention. FIG. 4 is a diagram showing an example of adding learning data in the first embodiment of the present invention. 4 is a diagram showing an example of automatic generation of a learning matrix by a learning/inference unit in embodiment 1 of the present invention. FIG. 1 is a diagram showing a graph representation and an adjacency matrix for representing the connection relationship between nodes in the GCN already described in the first embodiment of the present invention. FIG. 11 is a diagram showing a graph representation and an adjacency matrix for representing the connection relationship between nodes in an R-GCN described in a second embodiment of the present invention. 13 is a flowchart showing a series of processes executed by a netlist matrix conversion unit in the second embodiment of the present invention.

Below, preferred embodiments of the function estimation method, function estimation device, and function estimation program of the present invention will be described with reference to the drawings. In particular, the present invention is characterized by efficiently estimating functions implemented in an LSI netlist using GCN or Relational Graph Convolutional Networks (hereinafter referred to as R-GCN), which is a type of NN and a network with a folded graph structure. The case where GCN is used will be described in detail in embodiment 1, and the case where R-GCN is used will be described in detail in embodiment 2.

Embodiment 1.
1 is a diagram showing a functional configuration of a program for estimating on-chip functions for an LSI netlist in the first embodiment of the present invention. As shown in Fig. 1, input data includes GCN configuration parameter information 1, a learning or inference netlist 2, function label information 3 that is input as a function identification tag of the netlist during learning and becomes an inference candidate during inference, and standard cell information 4 specific to an LSI device for learning or inference.

As shown in FIG. 1, the program according to the first embodiment is composed of a GCN configuration management unit 5 that manages the GCN class configuration and the GCN binary tree configuration within each class based on the GCN configuration parameter information 1, a node number clustering unit 6 that replaces the composite gates and their connection relationships in the netlist as nodes and edges to perform class classification according to the number of nodes in the netlist, a netlist matrix conversion unit 7 for GCN internal calculations, and a learning and inference unit 8 that learns functions. The program according to the first embodiment is then executed on a computer so as to output the function label name that matches during inference or the absence of a function as an inference result 9.

Next, each of the functional components shown in FIG. 1 will be described individually.
The GCN configuration management unit 5 constructs classes according to the circuit scale of the netlist from the input GCN configuration parameter information 1. The GCN configuration management unit 5 also manages the GCN function labels held in each constructed class and the GCN binary tree configuration that determines the GCN inference order during inference. If function label information 3 is input when the netlist is input, the GCN configuration management unit 5 operates as a learning process, and if function label information 3 is not input, it operates as an inference process.

First, class management will be explained. Figure 2 is a diagram showing a method for constructing a GCN class configuration based on the circuit scale of the netlist in embodiment 1 of the present invention. GCN configuration parameter information 1 specifies three types of parameters, and constructs a GCN class hierarchy as shown in Figure 2, with a lowest class 11 and higher classes 12 and 13. In order to classify the GCN to be inferred based on the circuit scale of the netlist, the number of classes to be managed is input as parameter P1 (hereinafter referred to as P1).

It also has a function to automatically generate function labels that combine function labels of lower classes. To perform this automatic generation, the maximum number of nodes in the lowest class 11 is input as parameter P2 (hereafter referred to as P2), and the number of combinations of functions in the lowest class 11 is input as parameter P3 (hereafter referred to as P3).

Next, we will explain function labels. Function labels may be provided by the user as correct answer information during learning, or they may be automatically generated and notified by the learning and inference unit 8. Function labels define one function per GCN as a function to be inferred by the GCN.

Next, we will explain binary tree configuration management. Figure 3 is a diagram showing a binary tree configuration that determines the order of function judgment during function estimation in a GCN in embodiment 1 of the present invention. When multiple function labels are held within a GCN class, there are as many GCNs that judge each function label as there are function labels. Therefore, the GCN configuration management unit 5 needs to manage the judgment order of these multiple GCNs during inference.

The GCN configuration management unit 5 manages the GCN as a binary tree. Specifically, the GCN configuration management unit 5 performs function estimation from the GCN located at the top of the tree, and ends the estimation if it is determined that the function is present, and manages the GCN as a binary tree in such a configuration that function estimation is performed on a child GCN if it is determined that the function is not present.

During learning, the GCN configuration management unit 5 determines whether the functional label provided by the user is a new label. If the result of the determination is that the functional label is a new label, or if a notification of automatic generation of a GCN is input from the learning/inference unit 8, the GCN configuration management unit 5 adds the GCN to the apex of the GCN binary tree configuration.

On the other hand, during inference, the GCN configuration management unit 5 outputs the GCN binary tree configuration information of the corresponding class to the learning and inference unit 8. If the learning and inference unit 8 determines that the function is present, it ends the inference as the functional label at that time matches, and if it determines that the function is not present, it switches to the GCN located in the child and performs function estimation.

The node number clustering unit 6 converts the netlist 2 into a graph representation consisting of nodes and edges. The node number clustering unit 6 also performs class classification judgment based on the measured node count and the GCN class configuration information from the GCN configuration management unit 5.

Figure 4 is a diagram showing the netlist converted into a graph representation in the first embodiment of the present invention. As shown in Figure 4, the node number clustering unit 6 creates a graph representation in which the composite gates in the netlist are represented as nodes, and the connections between each composite gate are represented as edges.

Nodes are created from standard cell information used during logic synthesis from RTL to netlist. At this time, nodes that have the same circuit configuration and differ only in drive capacity are treated as the same node type because they have the same function.

The node number clustering unit 6 outputs node type information classified from the standard cell information and a graph-represented netlist to the netlist matrix conversion unit 7. The node number clustering unit 6 also performs classification based on the class hierarchy information acquired from the GCN configuration management unit 5, and notifies the learning and inference unit 8 of the judgment result.

The netlist matrix conversion unit 7 creates a feature vector matrix X, an adjacency matrix A, and a correct label matrix Y from the graph representation input from the node count clustering unit 6.

The netlist matrix conversion unit 7 expresses the type of composite gate at each node in the netlist as a feature vector matrix X. Specifically, the netlist matrix conversion unit 7 expresses nodes as rows and composite gates as columns, creating the number of rows as the maximum number of nodes in each class and the number of columns as the number of composite gates.

The netlist matrix conversion unit 7 also expresses the connection relationships at each node in the netlist as an adjacency matrix A. Specifically, the netlist matrix conversion unit 7 expresses the nodes as rows and columns, and expresses nodes in a connection relationship as 1 and other nodes as 0.

Furthermore, the netlist matrix conversion unit 7 expresses the GCN judgment result at each node in the netlist as a label data matrix Y. Specifically, the netlist matrix conversion unit 7 creates the label data matrix Y when notified by the GCN configuration management unit 5 that it is learning time, and does not create the label data matrix Y when notified that it is inference time.

The learning and inference unit 8 learns and infers functions. During learning, if the GCN configuration management unit 5 notifies the learning and inference unit 8 of an existing function, the learning and inference unit 8 inputs the feature vector matrix X, the adjacency matrix A, and the correct label matrix Y to the notified GCN, and updates the weight parameters within the GCN.

When a new function is notified from the GCN configuration management unit 5, the learning and inference unit 8 creates a new GCN. If a new GCN can be created as a combined function with an existing function in the class classified by the node count clustering unit 6 after learning, the learning and inference unit 8 automatically generates the GCN and notifies the GCN configuration management unit 5 of the function label information.

During inference, the learning and inference unit 8 inputs the feature vector matrix X and the adjacency matrix A to obtain an output matrix Z that is a function determination result. Specifically, the learning and inference unit 8 expresses nodes as rows, and the determination results of whether or not a function is present as columns,
{Number of nodes with the judgement result that the function is present ≧ Number of nodes with the judgement result that the function is present}
If the above is true, it is determined that the determined function is present.

On the other hand, if the function is determined to be absent, the learning and inference unit 8 continues the judgment according to the GCN binary tree structure within the class, and if there is no match, outputs that the corresponding function does not exist.

Next, we will explain the processing within the program explained so far using the processing flow for each block in Figure 1.

Figure 5 is a flowchart showing a series of processes executed by the GCN configuration management unit 5 in embodiment 1 of the present invention. The flow of processes of the GCN configuration management unit 5 in Figure 1 will be explained using this Figure 5.

In step S100, the GCN configuration management unit 5 inputs the netlist's function label information 3 or the class's GCN configuration parameter information 1.

Next, in step S101, the GCN configuration management unit 5 updates the GCN class configuration, sets the class from the node count information of each class input in step S100, and notifies the node count clustering unit 6 of the class setting.

Figure 6 shows the difference in GCN class configuration according to GCN configuration parameter information in the first embodiment of the present invention. Each class shown in Figure 6 is classified by the number of nodes. In order to perform calculations in GCN, the number of nodes must match. Therefore, the netlist matrix conversion unit 7 performs a matrix complement process from the number of nodes in the input netlist to the maximum number of nodes in the classified class.

The learning and inference unit 8 also has a function of automatically generating a function label that combines the function labels of lower classes. The learning and inference unit 8 then realizes the automatic generation of function labels by renumbering the nodes of the functions to be combined.

Therefore, the maximum number of nodes in an automatically generated matrix is
{Maximum number of nodes in the lowest class (P2) × number of combined functions (P3)}
Therefore, the GCN configuration management unit 5 inputs the GCN configuration parameter information 1 in order to perform GCN calculations in the higher class.

Next, in step S102, the GCN configuration management unit 5 judges whether learning or inference is to be performed. If the function label information 3 is input in step S100, the GCN configuration management unit 5 judges it as learning, and if nothing is input, it judges it as inference. If the GCN configuration management unit 5 judges it as learning, it notifies the netlist matrix conversion unit 7 that it should perform a learning process.

In step S102, if the GCN configuration management unit 5 determines that learning has occurred, it proceeds to processing in step S103, and if it determines that inference has occurred, it proceeds to processing in step S108.

When the process proceeds to step S103, the GCN configuration management unit 5 performs a new function determination based on the comparison result between the function label for each class based on the class classification result input by the node count clustering unit 6 and the function label identified by the function label information 3 already acquired in step S100.

If the GCN configuration management unit 5 obtains a comparison result in which the function labels of both do not match, it determines that it is a new function and proceeds to processing in step S104. On the other hand, if the GCN configuration management unit 5 obtains a comparison result in which the function labels of both match, it determines that it is not a new function and proceeds to processing in step S107.

If the process proceeds to step S104, the GCN configuration management unit 5 issues a learning instruction and notifies the learning/inference unit 8 of the new function.

Next, in step S105, the GCN configuration management unit 5 obtains information about the GCN added by the learning and inference unit 8 from the learning and inference unit 8.

Next, in step S106, the GCN configuration management unit 5 reflects the added GCN at the apex position of the binary tree configuration. By having a GCN that determines whether a function exists or not in a binary tree configuration, the GCN configuration management unit 5 can determine that the function input by inference does not exist as a learned function. In this case, by preparing learning data for the input function, it is possible to easily add a judgment function.

On the other hand, if the process proceeds from step S103 to step S107, the GCN configuration management unit 5 notifies the learning and inference unit 8 of an instruction to learn the functional labels.

Also, when the process proceeds from step S102 to step S108, the GCN configuration management unit 5 notifies the GCN class configuration information of the corresponding class based on the class information input from the node count clustering unit 6.

Next, we will explain the process flow of the node number clustering unit 6 in Figure 1. Figure 7 is a flowchart showing a series of processes executed by the node number clustering unit 6 in embodiment 1 of the present invention.

The node number clustering unit 6 inputs the learning or inference netlist 2 specified by the user, the standard cell information 4 specific to the LSI device, and the GCN configuration information that specifies the node number information on a class basis from the GCN configuration management unit 5. The node number clustering unit 6 is able to perform appropriate classification by specifying the number of nodes, taking into consideration that the configuration of the composite gate differs depending on the standard cell information used, resulting in a change in the number of nodes.

In step S200, the node number clustering unit 6 performs node conversion so that the composite gates in the netlist 2 of the circuit data are represented as nodes and the connections between each composite gate are represented as edges.

Nodes can be created from standard cell information 4 used for logic synthesis. In addition to the composite gate type, the standard cell information 4 also includes an identification number that is assigned based on the drive capacity of the circuit. The drive capacity of the circuit is not required for function estimation. Therefore, the node number clustering unit 6 creates a conversion table that treats composite gates that have the same input/output but different drive capacities as the same node.

Furthermore, the node number clustering unit 6 converts the nodes into compound gate units according to a conversion table, and performs numbering by treating the edges between each node.

Next, in step S201, the node count clustering unit 6 measures the number of numbered nodes.

Next, in step S202, the node number clustering unit 6 performs class determination based on the measured node number and the node number information for each class input from the GCN configuration management unit 5, thereby classifying the nodes. At the same time, the node number clustering unit 6 obtains the maximum number of nodes for the corresponding class, and notifies the netlist matrix conversion unit 7 and the GCN configuration management unit 5 of the maximum number of nodes.

Next, we will explain the process flow of the netlist matrix conversion unit 7 in Figure 1. Figure 8 is a flowchart showing a series of processes executed by the netlist matrix conversion unit 7 in embodiment 1 of the present invention.

In step S300, the netlist matrix conversion unit 7 creates a feature vector matrix X by using the maximum number of nodes for the class notified by the node number clustering unit 6 as rows and an additional column representing no match for the number of composite gate types on the conversion table generated from the standard cell information 4 as columns.

Figure 9 is a diagram showing an example of conversion of feature vector matrix X in embodiment 1 of the present invention. Feature vector matrix X represents the composite gate type for each node. Therefore, when creating feature vector matrix X, as shown in Figure 9, netlist matrix conversion unit 7 sets only one 1 in each row of the matrix, and sets the remaining elements to 0. In addition, for column elements that are not applicable, netlist matrix conversion unit 7 sets 1 to the node number numbers that are equal to or greater than the number of nodes in the input netlist in the classified class.

Next, in step S301, the netlist matrix conversion unit 7 creates an adjacency matrix A with the maximum number of nodes in the class notified by the node number clustering unit 6 as rows and columns.

Figure 10 is a diagram showing an example of conversion of the connection matrix A in the first embodiment of the present invention. When creating the connection matrix A, the netlist matrix conversion unit 7 sets the elements of the node numbers connected to each row to 1, as shown in Figure 10, and sets the remaining elements to 0. Unlike the feature vector matrix X, the connection matrix A expresses the connection relationships, so there are cases where two or more elements are set to 1.

Next, in step S302, the netlist matrix conversion unit 7 performs processing according to the learning instruction or inference instruction notified by the GCN configuration management unit 5. If a learning instruction is notified, the process proceeds to step S303, where the netlist matrix conversion unit 7 creates a label data matrix Y.

The label data matrix Y is expressed with the maximum number of nodes in the class notified by the node number clustering unit 6 as rows, and with/without function for each node as columns. Figure 11 is a diagram showing an example of conversion of the correct answer label matrix Y in embodiment 1 of the present invention. As shown in Figure 11, in order to learn the netlist in function units, the netlist matrix conversion unit 7 creates a label data matrix Y with a correct answer label of with function for all nodes.

Next, we will explain the process flow of the learning and inference unit 8 in Figure 1. Figure 12 is a flowchart showing a series of processes executed by the learning and inference unit 8 in embodiment 1 of the present invention.

In step S400, the learning/inference unit 8 acquires parameter information 1 for GCN configuration.

Next, in step S401, the learning/inference unit 8 determines whether the instruction notified from the GCN configuration management unit 5 is a learning instruction or an inference instruction. If a learning instruction is notified, the learning/inference unit 8 proceeds to step S402, and if an inference instruction is notified, the learning/inference unit 8 proceeds to step S406.

When the process proceeds to step S402, the learning and inference unit 8 determines whether the learning data notified by the GCN configuration management unit 5 is a new function. If it is determined that the learning data is a new function, the process proceeds to step S403, where the learning and inference unit 8 adds a new GCN.

Figures 13 and 14 show an example of adding learning data in embodiment 1 of the present invention. Specifically, Figures 13 and 14 show an example of a case in which the GCN configuration management unit 5 configures a class with GCN configuration parameter information 1 set as P1 = 2, P2 = 100, and P3 = 2.

As shown in the specific example of Figure 13, when a new function label A having a node count in class 1 that is not managed is input, the learning and inference unit 8 creates a new GCN function A in step S403. The learning and inference unit 8 repeatedly learns the netlist having the new function label A the number of times prepared by the user. In addition, there is only one function in class 1, function label A, and the learning and inference unit 8 does not automatically generate a GCN in class 2, which is the higher class.

Next, if a new function label B with a node count in class 1 that is not managed is input, the learning and inference unit 8 creates a new GCN function B in step S403. The learning and inference unit 8 repeatedly learns the netlist with the new function label B the number of times prepared by the user. In addition, there are two functions in class 1, function labels A and B, and the learning and inference unit 8 automatically generates a GCN with the combined function label AB in class 2, which is the higher class.

In this way, the learning and inference unit 8 creates a new matrix from the learning data of function label A and function label B prepared by the user, and performs repeated learning. FIG. 15 is a diagram showing an example of automatic generation of a learning matrix by the learning and inference unit 8 in the first embodiment of the present invention. The learning and inference unit 8 converts the node numbers nB0 to nB99 of function label B from the matrices of function label A and function label B created by the netlist matrix conversion unit 7 into nAB100 to nAB199 to create each matrix.

In the specific example of FIG. 14, when a new function label C that is not managed by the GCN configuration management unit 5 is input, the learning and inference unit 8 creates a new GCN function C in step S403. The learning and inference unit 8 repeatedly learns the netlist with the new function label C the number of times prepared by the user. In addition, the functions in class 1 are three, function labels A, B, and C, and the learning and inference unit 8 automatically generates a GCN with combination function labels AC and BC in class 2, which is the higher class.

After adding a new GCN in step S403, the learning/inference unit 8 notifies the GCN configuration management unit 5 of the functional label information of the added GCN in step S404.

Also, if it is determined in the previous step S402 that the instruction is to learn an existing label, the process proceeds to step S405, where the learning and inference unit 8 performs learning of an additional GCN.

Also, if it is determined in the previous step S401 that the instruction is an inference instruction, the process proceeds to step S406, where the learning/inference unit 8 prepares the GCN for inference notified by the GCN configuration management unit 5.

As shown in FIG. 3, the GCN configuration management unit 5 manages the GCN for each class as a binary tree configuration. Then, in step S406, the learning and inference unit 8 selects whether or not there is a functional label for the GCN at the apex of the binary tree.

Next, if it is determined in step S407 that there is a functional label for the GCN at the apex of the binary tree, the process proceeds to step S409, where the learning and inference unit 8 outputs the functional label of the GCN used in the determination as the inference result.

On the other hand, if it is determined in step S407 that there is no functional label for the GCN at the apex of the binary tree, the process proceeds to step S408, where the learning and inference unit 8 determines whether or not the GCN can be updated. If there is a GCN one level lower in the binary tree configuration of the GCN acquired in step S400, the learning and inference unit 8 determines that the GCN can be updated, returns to step S406, and updates the GCN.

On the other hand, if there is no GCN in a lower hierarchy to update in the binary tree structure of the GCN obtained in step S400, the learning/inference unit 8 determines that the GCN cannot be updated, proceeds to step S409, and outputs the functional label of the GCN used in the judgment as the inference result.

As described above, according to the first embodiment, function estimation is performed using Graph Convolutional Networks (GCN), which is a type of NN. The graph used in this method is a data structure based on graph theory that is composed of nodes, edges, weights, etc. Examples of such data structures include various familiar things such as the Internet, transportation networks, and SNS connections.

In GCN, a NN is constructed for such graphs using convolution operations based on the connections between nodes and edges, and graph features are extracted to classify the graphs. In prior art documents, features are extracted for each node, and the extracted features are used to classify the nodes.

In contrast, in the first embodiment, the extracted features are applied to a netlist that has one function in the entire graph, and a determination is made as to whether or not a learned function exists. By configuring these GCNs as a binary tree as a function discriminator, it becomes possible to extract unlearned functions. This reduces misclassification of unlearned functions.

Furthermore, in this first embodiment, the netlist is classified according to the circuit size, and the GCNs are managed for each class. This allows functions of classes with small circuit sizes to be combined to automatically generate GCNs of higher-level classes, which can be used as candidates for determining combined functions. In addition, it is possible to select the GCNs to be determined during inference, which improves efficiency.

Embodiment 2.
In the above embodiments, a function estimation method, a function estimation device, and a function estimation program executed on a computer have been described in order to extract functions implemented in a netlist used in the logical design of an LSI by using a GCN, which is a network formed by folding a graph structure.

In contrast, in the second embodiment, we will explain a function estimation method, a function estimation device, and a function estimation program that are executed on a computer to extract functions implemented in a netlist used in the logical design of an LSI by using an R-GCN instead of a GCN.

First, the difference between GCN and R-GCN will be explained using Figures 16 and 17. Figure 16 is a diagram showing a graph representation and an adjacency matrix for representing the connection relationships between nodes using GCN, which has already been explained in embodiment 1 of the present invention. On the other hand, Figure 17 is a diagram showing a graph representation and an adjacency matrix for representing the connection relationships between nodes using R-GCN, which will be explained in embodiment 2 of the present invention.

Figures 16 and 17 show an example of the connection relationship when five nodes, n0 to n4, are used. The GCN described in the first embodiment uses an undirected graph in which the input/output relationships of the netlist are not maintained, as shown in Figure 16(a). In other words, the GCN shows which nodes are connected to each other, but does not show the input/output relationship information showing which node outputs a signal to which node.

Therefore, the adjacency matrix A corresponding to the graph representation in the GCN shown in Figure 16(a) was expressed as 1 when there was a connection between nodes and 0 when there was no connection, as shown in Figure 16(b).

In contrast, the R-GCN described in this second embodiment uses a directed graph that holds the input/output relationships of the netlist, as shown in FIG. 17(a). That is, the R-GCN expresses which nodes are connected to which other nodes, and also expresses the input/output relationship information, which indicates which node outputs a signal to which other node, as arrows.

Therefore, the adjacency matrix A corresponding to the graph representation in the R-GCN shown in Figure 17(a) can be expressed using three types of adjacency matrix: the adjacency matrix (input side) Ain shown in Figure 17(b), the adjacency matrix (self) Aown shown in Figure 17(c), and the adjacency matrix (output side) Aout shown in Figure 17(d).

In other words, in this second embodiment, the three types of adjacency matrices that represent the connection relationships and input/output relationships at each node in the netlist are composed of a first adjacency matrix Ain that indicates the connection relationships regarding inputs between nodes at each node, a second adjacency matrix Aown that indicates a unit matrix with each node as an element, and a third adjacency matrix Aout that indicates the connection relationships regarding outputs between nodes at each node.

In the adjacency matrix (input side) Ain, which corresponds to the first adjacency matrix shown in FIG. 17(b), the rows indicate the nodes on the input side, and the columns indicate the nodes on the output side, with the value 1 representing an input relationship between nodes, and the value 0 representing no input relationship. For example, when looking at node n1, the element in the second row and first column of the adjacency matrix (input side) Ain is "1" because it receives a signal from node n0.

Also, the adjacency matrix (self) Aown, which corresponds to the second adjacency matrix shown in Figure 17(c), is a unit matrix in which elements of nodes in the same row and column are "1".

Furthermore, in the adjacency matrix (output side) Aout, which corresponds to the third adjacency matrix shown in FIG. 17(d), the rows indicate the nodes on the output side, and the columns indicate the nodes on the input side, with an output relationship between the nodes represented as 1 and no output relationship represented as 0. For example, when focusing on node n0, the element in the first row and second column of the adjacency matrix (output side) Aout is "1" since it outputs a signal to node n1.

In this way, when one adjacency matrix A in a GCN is used, only information on the connection relationships between nodes is obtained, and information on the input/output relationships is not obtained. Therefore, as is clear from Figures 16(a) and 16(b), for example, although information that nodes n0 and n1 are connected can be obtained, it is not possible to obtain information on whether the signal is from node n0 to node n1 or from node n1 to node n0.

In other words, when a signal is output from node n0 to node n1 and when a signal is output from node n1 to node n0, the same graph representation and the same adjacency matrix A are obtained, and it is not possible to distinguish between the two.

In contrast, when using the three adjacency matrices (input) Ain, adjacency matrix (self) Aown, and adjacency matrix (output) Aout in the R-GCN, information on the connection relationships between nodes as well as information on the input/output relationships can be obtained.

Therefore, as is clear from Figures 17(a) to 17(d), for example, in addition to information that nodes n0 and n1 are connected, it is also possible to obtain information that a signal is being output from node n0 to node n1.

In other words, it is possible to distinguish between the case where a signal is output from node n0 to node n1 and the case where a signal is output from node n1 to node n0 using a graph representation and three types of adjacency matrices. Therefore, by using R-GCN, it is possible to achieve more versatile and highly accurate function estimation compared to the case where GCN is used.

The configuration of the function estimation device in this embodiment 2 is basically the same as the configuration described in FIG. 1 in the previous embodiment 1 when using GCN. However, the process of the netlist matrix conversion unit 7 in this embodiment 2 differs in that, instead of generating one type of adjacency matrix A as shown in FIG. 16, it generates three types of adjacency matrices: an (input) Ain, an adjacency matrix (self) Aown, and an adjacency matrix (output side) Aout as shown in FIG. 17.

The processing flow of the netlist matrix conversion unit 7 in the second embodiment will now be described. Figure 18 is a flowchart showing a series of processes executed by the netlist matrix conversion unit 7 in the second embodiment of the present invention.

Compared to the flowchart shown in FIG. 8 in the first embodiment, the flowchart shown in FIG. 18 has been modified in that the process of creating the adjacency matrix in step S301 is modified to generate three types of adjacency matrix: input Ain, self Aown, and output Aout. Therefore, the following explanation focuses on the modified process in step S301.

In this second embodiment, step S301 is composed of three steps: S301-1, S301-2, and S301-3. After creating the feature vector matrix X in step S300, the netlist matrix conversion unit 7 creates an adjacency matrix (input) Ain in step S301-1, with the maximum number of nodes of the class notified by the node number clustering unit 6 as the rows and columns.

Next, in step S301-2, the netlist matrix conversion unit 7 creates an adjacency matrix (self) Aown, with the maximum number of nodes in the class notified by the node number clustering unit 6 as the row and column.

Furthermore, in step S301-3, the netlist matrix conversion unit 7 creates an adjacency matrix (output) Aout with the maximum number of nodes of the class notified by the node number clustering unit 6 as rows and columns.

Then, the netlist matrix conversion unit 7 executes the processes of steps S302 and S303.

As described above, according to the second embodiment, function estimation is performed using Relational Graph Convolutional Networks (R-GCN), which is a type of NN. The graph used in this method is a data structure based on graph theory that is composed of nodes, edges, weights, etc., just like in the first embodiment where function estimation is performed using a GCN. Examples of such data structures include various familiar things such as the Internet, transportation networks, and SNS connections.

In R-GCN, a NN is constructed for such graphs using convolutional calculations based on the connections between nodes and edges, and the graph features are extracted taking into account the input/output relationships between nodes, thereby classifying the graphs. In prior art documents, features are extracted for each node, and the extracted features are used to classify the nodes.

In contrast, in the second embodiment, the extracted features are applied to a netlist that has one function in the entire graph, and a determination is made as to whether or not a learned function exists. By configuring these R-GCNs as a binary tree discriminator for functions, it becomes possible to extract unlearned functions. This reduces misclassification of unlearned functions.

Furthermore, in this second embodiment, the netlist is classified according to the circuit size, and the R-GCN is managed for each class. This makes it possible to combine functions of classes with small circuit sizes to automatically generate R-GCNs of higher classes, which can be used as candidates for determining combined functions. In addition, it is possible to select the R-GCNs to be determined during inference, which improves efficiency.

Furthermore, in this second embodiment, by using R-GCN, function estimation based on directed graph representation and three types of adjacency matrices becomes possible. As a result, it becomes possible to realize more versatile and highly accurate function estimation compared to the case where GCN is used.

1 GCN configuration parameter information, 2 Netlist, 3 Function label information, 4 Standard cell information, 5 GCN configuration management unit (management process, management unit, management means), 6 Node number clustering unit (clustering process, clustering unit, clustering means), 7 Netlist matrix conversion unit (conversion process, conversion unit, conversion means), 8 Learning and inference unit (learning and inference process, learning and inference means), 9 Inference result, 11 Lowest class, 12, 13 Highest class.

Claims (9)

A function estimation method executed on a computer to extract functions implemented in a netlist used in an LSI logic design using a GCN, which is a network formed by convolving a graph structure, comprising the steps of:
A management process for constructing GCN class configuration information of the netlist from GCN configuration parameter information, and for each constructed GCN class, managing a GCN function label held within the class and a GCN binary tree configuration that determines a GCN inference order during inference;
A clustering process for converting the netlist into a graph representation composed of nodes and edges, and classifying the netlist into classes according to the number of nodes measured and the GCN class configuration information constructed;
a conversion step of executing a complementation process to make the number of nodes in each of the classes obtained by the classification consistent;
a learning and inference step of learning and inferring the function based on the processing results of the management step and the conversion step. In the converting step,
a feature vector matrix representing a type of a composite gate at each node in the netlist;
an adjacency matrix representing a connection relationship between each node in the netlist;
A correct label matrix representing the GCN determination result for each node in the netlist is created;
In the learning and inference step,
The function estimation method according to claim 1 , wherein the learning is performed based on the feature vector matrix, the adjacency matrix, and the correct label matrix created in the conversion step. In the learning and inference step,
The function estimation method according to claim 1 or 2, wherein when a new label not managed in the management process is input, a new GCN function is generated, and a new GCN is automatically generated by combining each of the newly generated GCN functions. In the management step,
The function estimation method according to claim 1 , further comprising: determining whether or not the function has been learned by utilizing the GCN binary tree structure. A function estimation device that extracts functions implemented in a netlist used in an LSI logic design by using a GCN, which is a network formed by folding a graph structure, comprising:
A management unit that constructs GCN class configuration information of the netlist from GCN configuration parameter information, and manages a GCN function label held in each constructed GCN class and a GCN binary tree configuration that determines a GCN inference order during inference;
a clustering unit that converts the netlist into a graph representation composed of nodes and edges, and performs classification according to the measured number of nodes and the constructed GCN class configuration information;
a conversion unit that executes a complementation process to make the number of nodes in each of the classes obtained by the classification consistent;
a learning and inference unit that learns and infers the function based on processing results of the management unit and the conversion unit. A function estimation program executed on a computer to extract functions implemented in a netlist used in an LSI logic design using a GCN, which is a network formed by folding a graph structure, comprising:
The computer,
A management means for constructing GCN class configuration information of the netlist from GCN configuration parameter information, and for each constructed GCN class, managing a GCN function label held within the class and a GCN binary tree configuration for determining a GCN inference order during inference;
A clustering means for converting the netlist into a graph representation composed of nodes and edges, and classifying the netlist into classes according to the number of nodes measured and the GCN class configuration information that has been constructed;
A conversion means for executing a complementation process for matching the number of nodes in each of the classes obtained by the classification;
A function estimation program that functions as a learning and inference means for learning and inferring the function based on the processing results of the management means and the conversion means. A function estimation method executed on a computer to extract functions implemented in a netlist used in an LSI logic design, using an R-GCN as a GCN that is a network obtained by folding a graph structure, comprising:
A management process for constructing GCN class configuration information of the netlist from GCN configuration parameter information, and for each constructed GCN class, managing a GCN function label held within the class and a GCN binary tree configuration that determines a GCN inference order during inference;
A clustering process for converting the netlist into a graph representation composed of nodes and edges, and classifying the netlist into classes according to the number of nodes measured and the GCN class configuration information constructed;
a conversion step of executing a complementation process to make the number of nodes in each of the classes obtained by the classification consistent;
a learning and inference step of learning and inferring the function based on the processing results of the management step and the conversion step,
In the converting step,
a feature vector matrix representing a type of a composite gate at each node in the netlist;
Three types of adjacency matrices that represent connection relationships and input/output relationships at each node in the netlist;
A correct label matrix representing the GCN determination result for each node in the netlist is created;
In the learning and inference step,
The learning is performed based on the feature vector matrix, the three types of adjacency matrices, and the correct label matrix created in the conversion process;
The three types of adjacency matrices are composed of a first adjacency matrix indicating a connection relationship between the nodes regarding inputs at each of the nodes, a second adjacency matrix indicating a unit matrix with each of the nodes as elements, and a third adjacency matrix indicating a connection relationship between the nodes regarding outputs at each of the nodes. A function estimation device that extracts functions implemented in a netlist used in an LSI logic design by using an R-GCN as a GCN that is a network obtained by folding a graph structure, comprising:
A management unit that constructs GCN class configuration information of the netlist from GCN configuration parameter information, and manages a GCN function label held in each constructed GCN class and a GCN binary tree configuration that determines a GCN inference order during inference;
a clustering unit that converts the netlist into a graph representation composed of nodes and edges, and performs classification according to the measured number of nodes and the constructed GCN class configuration information;
a conversion unit that executes a complementation process to make the number of nodes in each of the classes obtained by the classification consistent;
a learning and inference unit that learns and infers the function based on a processing result of the management unit and the conversion unit,
The conversion unit is
a feature vector matrix representing a type of a composite gate at each node in the netlist;
Three types of adjacency matrices that represent connection relationships and input/output relationships at each node in the netlist;
A correct label matrix representing the GCN determination result for each node in the netlist is created;
The learning and inference unit includes:
The learning is performed based on the feature vector matrix, the three types of adjacency matrices, and the correct label matrix created by the conversion unit;
The three types of adjacency matrices are composed of a first adjacency matrix indicating a connection relationship between the nodes regarding inputs at each of the nodes, a second adjacency matrix indicating a unit matrix with each node as an element, and a third adjacency matrix indicating a connection relationship between the nodes regarding outputs at each of the nodes. A function estimation program executed on a computer to extract functions implemented in a netlist used in an LSI logic design, using an R-GCN as a GCN that is a network obtained by folding a graph structure, comprising:
The computer,
A management means for constructing GCN class configuration information of the netlist from GCN configuration parameter information, and for each constructed GCN class, managing a GCN function label held within the class and a GCN binary tree configuration for determining a GCN inference order during inference;
A clustering means for converting the netlist into a graph representation composed of nodes and edges, and classifying the netlist into classes according to the number of nodes measured and the GCN class configuration information that has been constructed;
A conversion means for executing a complementation process for matching the number of nodes in each of the classes obtained by the classification;
a function estimation program for causing the program to function as a learning and inference means for learning and inferring the function based on processing results of the management means and the conversion means,
The conversion means is
a feature vector matrix representing a type of a composite gate at each node in the netlist;
Three types of adjacency matrices that represent connection relationships and input/output relationships at each node in the netlist;
A correct label matrix representing the GCN determination result for each node in the netlist is created;
The learning and inference means includes:
The learning is performed based on the feature vector matrix, the three types of adjacency matrices, and the correct label matrix created by the conversion means;
The three types of adjacency matrices are composed of a first adjacency matrix indicating the connection relationship between the nodes regarding inputs at each of the nodes, a second adjacency matrix indicating an identity matrix with each node as an element, and a third adjacency matrix indicating the connection relationship between the nodes regarding outputs at each of the nodes.