CN118839658B - A method for timing prediction before circuit wiring based on graph neural network - Google Patents
A method for timing prediction before circuit wiring based on graph neural network Download PDFInfo
- Publication number
- CN118839658B CN118839658B CN202411320123.3A CN202411320123A CN118839658B CN 118839658 B CN118839658 B CN 118839658B CN 202411320123 A CN202411320123 A CN 202411320123A CN 118839658 B CN118839658 B CN 118839658B
- Authority
- CN
- China
- Prior art keywords
- layer
- time
- predicted value
- unit
- node
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Active
Links
- 238000000034 method Methods 0.000 title claims abstract description 47
- 238000013528 artificial neural network Methods 0.000 title claims abstract description 15
- 238000003062 neural network model Methods 0.000 claims abstract description 19
- 238000012549 training Methods 0.000 claims abstract description 12
- 238000012360 testing method Methods 0.000 claims abstract description 10
- 238000012216 screening Methods 0.000 claims abstract description 7
- 238000012545 processing Methods 0.000 claims abstract description 6
- 230000004927 fusion Effects 0.000 claims description 57
- 239000013598 vector Substances 0.000 claims description 21
- 238000006243 chemical reaction Methods 0.000 claims description 19
- 239000011159 matrix material Substances 0.000 claims description 9
- 238000010606 normalization Methods 0.000 claims description 6
- 230000007704 transition Effects 0.000 claims description 5
- 230000002457 bidirectional effect Effects 0.000 claims description 4
- 230000009466 transformation Effects 0.000 claims description 4
- 238000004140 cleaning Methods 0.000 claims description 3
- 230000011218 segmentation Effects 0.000 claims description 3
- 230000004913 activation Effects 0.000 claims description 2
- 238000010586 diagram Methods 0.000 abstract description 9
- 230000007246 mechanism Effects 0.000 abstract description 2
- 230000008569 process Effects 0.000 description 7
- 238000004364 calculation method Methods 0.000 description 6
- 238000004458 analytical method Methods 0.000 description 5
- 230000003068 static effect Effects 0.000 description 5
- 238000013461 design Methods 0.000 description 4
- 238000011156 evaluation Methods 0.000 description 3
- 238000005457 optimization Methods 0.000 description 3
- ORILYTVJVMAKLC-UHFFFAOYSA-N Adamantane Natural products C1C(C2)CC3CC1CC2C3 ORILYTVJVMAKLC-UHFFFAOYSA-N 0.000 description 2
- 238000012300 Sequence Analysis Methods 0.000 description 2
- 230000003213 activating effect Effects 0.000 description 1
- 230000004931 aggregating effect Effects 0.000 description 1
- 230000009286 beneficial effect Effects 0.000 description 1
- 230000005540 biological transmission Effects 0.000 description 1
- 239000003990 capacitor Substances 0.000 description 1
- 230000002596 correlated effect Effects 0.000 description 1
- 230000003071 parasitic effect Effects 0.000 description 1
- 230000009467 reduction Effects 0.000 description 1
- 230000008054 signal transmission Effects 0.000 description 1
Classifications
-
- G—PHYSICS
- G06—COMPUTING; CALCULATING OR COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F30/00—Computer-aided design [CAD]
- G06F30/30—Circuit design
- G06F30/39—Circuit design at the physical level
- G06F30/394—Routing
-
- G—PHYSICS
- G06—COMPUTING; CALCULATING OR COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F30/00—Computer-aided design [CAD]
- G06F30/20—Design optimisation, verification or simulation
- G06F30/27—Design optimisation, verification or simulation using machine learning, e.g. artificial intelligence, neural networks, support vector machines [SVM] or training a model
-
- G—PHYSICS
- G06—COMPUTING; CALCULATING OR COUNTING
- G06N—COMPUTING ARRANGEMENTS BASED ON SPECIFIC COMPUTATIONAL MODELS
- G06N3/00—Computing arrangements based on biological models
- G06N3/02—Neural networks
- G06N3/04—Architecture, e.g. interconnection topology
- G06N3/042—Knowledge-based neural networks; Logical representations of neural networks
-
- G—PHYSICS
- G06—COMPUTING; CALCULATING OR COUNTING
- G06N—COMPUTING ARRANGEMENTS BASED ON SPECIFIC COMPUTATIONAL MODELS
- G06N3/00—Computing arrangements based on biological models
- G06N3/02—Neural networks
- G06N3/04—Architecture, e.g. interconnection topology
- G06N3/045—Combinations of networks
-
- G—PHYSICS
- G06—COMPUTING; CALCULATING OR COUNTING
- G06N—COMPUTING ARRANGEMENTS BASED ON SPECIFIC COMPUTATIONAL MODELS
- G06N3/00—Computing arrangements based on biological models
- G06N3/02—Neural networks
- G06N3/04—Architecture, e.g. interconnection topology
- G06N3/048—Activation functions
-
- G—PHYSICS
- G06—COMPUTING; CALCULATING OR COUNTING
- G06N—COMPUTING ARRANGEMENTS BASED ON SPECIFIC COMPUTATIONAL MODELS
- G06N3/00—Computing arrangements based on biological models
- G06N3/02—Neural networks
- G06N3/08—Learning methods
-
- Y—GENERAL TAGGING OF NEW TECHNOLOGICAL DEVELOPMENTS; GENERAL TAGGING OF CROSS-SECTIONAL TECHNOLOGIES SPANNING OVER SEVERAL SECTIONS OF THE IPC; TECHNICAL SUBJECTS COVERED BY FORMER USPC CROSS-REFERENCE ART COLLECTIONS [XRACs] AND DIGESTS
- Y04—INFORMATION OR COMMUNICATION TECHNOLOGIES HAVING AN IMPACT ON OTHER TECHNOLOGY AREAS
- Y04S—SYSTEMS INTEGRATING TECHNOLOGIES RELATED TO POWER NETWORK OPERATION, COMMUNICATION OR INFORMATION TECHNOLOGIES FOR IMPROVING THE ELECTRICAL POWER GENERATION, TRANSMISSION, DISTRIBUTION, MANAGEMENT OR USAGE, i.e. SMART GRIDS
- Y04S10/00—Systems supporting electrical power generation, transmission or distribution
- Y04S10/50—Systems or methods supporting the power network operation or management, involving a certain degree of interaction with the load-side end user applications
Landscapes
- Engineering & Computer Science (AREA)
- Theoretical Computer Science (AREA)
- Physics & Mathematics (AREA)
- Evolutionary Computation (AREA)
- General Physics & Mathematics (AREA)
- General Engineering & Computer Science (AREA)
- Software Systems (AREA)
- Artificial Intelligence (AREA)
- Computing Systems (AREA)
- Mathematical Physics (AREA)
- General Health & Medical Sciences (AREA)
- Molecular Biology (AREA)
- Computational Linguistics (AREA)
- Biophysics (AREA)
- Biomedical Technology (AREA)
- Data Mining & Analysis (AREA)
- Life Sciences & Earth Sciences (AREA)
- Health & Medical Sciences (AREA)
- Computer Hardware Design (AREA)
- Geometry (AREA)
- Computer Vision & Pattern Recognition (AREA)
- Medical Informatics (AREA)
- Computer Networks & Wireless Communication (AREA)
- Design And Manufacture Of Integrated Circuits (AREA)
Abstract
本发明公开一种基于图神经网络的电路布线前时序预测方法，包括根据真实基准电路构建有向图；获取真实基准电路的时序报告，并筛选出与到达时间相关的特征参数；将有向图和与到达时间相关的特征参数构建数据集，同时设定标签；构建基于RGAT的图神经网络模型，进行训练和测试。本发明采用RGAT进行图嵌入阶段的节点特征更新，通过考虑不同邻居节点的影响力以及有向图中多种类型的边，为不同关系分配不同权重，这种精细化的权重处理机制提高了模型对电路图中串扰等复杂因素影响的预测能力，增强了对到达时间预测的准确度，尤其是在考虑到邻居节点和邻边信息对到达时间的影响。
The present invention discloses a method for timing prediction before circuit wiring based on graph neural network, including constructing a directed graph according to a real reference circuit; obtaining a timing report of the real reference circuit, and screening out characteristic parameters related to arrival time; constructing a data set of the directed graph and the characteristic parameters related to arrival time, and setting labels at the same time; constructing a graph neural network model based on RGAT, and performing training and testing. The present invention adopts RGAT to update node features in the graph embedding stage, and assigns different weights to different relationships by considering the influence of different neighbor nodes and multiple types of edges in the directed graph. This refined weight processing mechanism improves the model's ability to predict the influence of complex factors such as crosstalk in the circuit diagram, and enhances the accuracy of arrival time prediction, especially considering the influence of neighbor nodes and neighbor edge information on arrival time.
Description
Technical Field
The invention belongs to the technical field of electronic design automation, and particularly relates to a pre-wiring time sequence prediction method based on a graph neural network.
Background
Static timing analysis engines are often used at various stages of a physical design to guide design optimization to achieve timing closure. In the layout stage, due to the lack of information such as wire parasitics, the timing estimation result of the static timing analysis engine is inaccurate. Inaccurate results can lead to non-ideal layout quality and greatly impact the quality of downstream routing tasks, resulting in increased design iterations.
In order to solve the above problems, an accurate and efficient pre-wiring timing prediction model based on layout results is important, which helps to achieve an efficient timing driven layout, avoiding redundant wiring processes. The current pre-wiring time sequence prediction method is characterized in that firstly, net embedding is generated through simulating the calculation process of a static time sequence analysis engine, and then, layer-by-layer prediction is carried out according to the topological sequence. The wire mesh embedding method of the method is limited to aggregating local information of the current wire mesh edge, ignoring influences such as crosstalk between adjacent edges or points, lacking modeling capability for global information, and adopting an excessively complex algorithm in predicting unit delay, so that complexity and calculation cost of a model are increased, and prediction performance and reasoning speed of the model are influenced.
Disclosure of Invention
The invention aims to solve the problems that the current pre-wiring time sequence prediction work lacks modeling capability for global information and an excessively complex algorithm is adopted in the prediction of unit delay, and provides a pre-wiring time sequence prediction method based on a graph neural network.
In order to solve the above problems, the present invention provides a circuit pre-wiring timing prediction method based on a graph neural network, the method comprising:
step S1, constructing a data set, which specifically comprises the following steps:
Constructing a directed graph according to the real reference circuit;
acquiring a time sequence report of a real reference circuit, and screening out characteristic parameters related to the arrival time;
constructing a data set by using the directed graph and the characteristic parameters related to the arrival time, and setting a label at the same time, wherein the label comprises the arrival time, the unit delay time, the connection delay time and the conversion time of each device unit pin in the time sequence report;
step S2, performing data cleaning and normalization processing on the generated data set, and dividing the processed data set into a training set and a testing set;
Step S3, constructing a map neural network model based on RGAT, and training and testing the map neural network model by using a training set and a testing set;
and S4, predicting a post-wiring time sequence result of the circuit by using the trained and tested map neural network model based on RGAT.
Preferably, the step S1 specifically includes:
S101, taking pins of a device unit in a real reference circuit as nodes of a directed graph, taking a connecting line edge and a unit edge of the device unit as edges between the nodes of the directed graph, namely, connecting the nodes, wherein the connecting line edge is a connecting line between two device units and is set to be a bidirectional edge;
S102, obtaining an adjacency matrix A of the directed graph according to the connection relation among the nodes of the directed graph;
and S103, generating a time sequence report of the real reference circuit, and screening out characteristic parameters related to the arrival time according to the time sequence report.
Preferably, the characteristic parameters related to the arrival time in step S103 include node characteristics and unit edge characteristics.
More preferably, the node characteristics in step S103 include distances from 4 boundaries of the chip in the real reference circuit, pin capacitance, pin type, and node type, where the pin type includes PI pins and PO pins, the node type includes fan-in nodes and fan-out nodes, and the unit edge characteristics include index values and delay values of the LUT lookup table.
Preferably, the map neural network model based on RGAT in step S3 includes a map embedding stage and a delay propagation stage;
the graph embedding stage is to update node characteristics by RGAT using multi-layer residual error connection for all nodes in the directed graph;
the delay propagation stage analyzes the topology layer of the directed graph, and starts from the initial layer of the topology layer, the information propagation of the wire outgoing side or the unit side is realized layer by layer;
More preferably, in the step S3, the first layer input of the multi-layer residual connection RGAT is node characteristic, the other layers except the first layer input is the output of the upper layer, each layer RGAT updates the input characteristic, adds the input characteristic and the updated characteristic through residual connection, and adds the result as the output of the layer;
The updating of the input features by each layer RGAT comprises an attention head feature fusion stage, a relation head feature fusion stage and a fusion stage;
The fusion stage is used for splicing the feature vector after the attention head feature fusion and the feature vector after the relationship head feature fusion, and linear transformation are adopted And performing residual connection on the result after the function is activated and the input of the current layer to obtain updated node characteristics.
More preferably, in step S3, the initial layer of the topology layer of the directed graph in the delay propagation stage is composed of source nodes with outgoing edges of the connection lines.
More preferably, in the step S3, in the wire delay propagation layer in the delay propagation stage, the input of each wire delay propagation layer is the source node predicted value of the current wire edge, the embedded fusion characteristic of the source node and the embedded fusion characteristic of the target node, wherein the source node predicted value of the wire edge adopts the target node predicted value of the last unit delay propagation layer, and the source node predicted value of the first wire delay propagation layer is initialized to 0;
Splicing the source node predicted value of the current connecting edge, the embedded fusion characteristic of the source node and the embedded fusion characteristic of the target node, and finally outputting the target node predicted value through a multi-layer perceptron MLP, wherein the predicted value comprises a predicted value of arrival time and a predicted value of conversion time.
More preferably, in the unit delay propagation layer in the delay propagation stage of step S3, the input of each unit delay propagation layer is the source node predicted value of the current unit side, the embedded fusion characteristic of the source node, the embedded fusion characteristic of the target node and the unit side characteristic, wherein the source node predicted value of the unit side adopts the target node predicted value of the last connection delay propagation layer, the embedded fusion characteristic of the source node is the spliced result of the initial node characteristic of the source node and the updated node characteristic of the graph embedding stage, and the embedded fusion characteristic of the target node is the spliced result of the initial node characteristic of the target node and the updated node characteristic of the graph embedding stage;
Splicing the source node predicted value of the current unit edge, the embedded fusion characteristic of the source node, the embedded fusion characteristic of the target node and the unit edge characteristic, and outputting the result through a multi-layer perceptron MLP;
then, the output vector of the multi-layer perceptron MLP is subjected to segmentation operation and is divided into four parts, wherein the first part is a weight parameter with the length of 1, the second part and the third part are two groups of intermediate features with equal length, and the fourth part is used as a unit delay time predicted value;
The first partial result is passed through And then, respectively carrying out summation operation and maximum value operation on the two groups of weighted intermediate features of all the unit edges connected to the same target node, splicing the summation operation result and the maximum value operation result, and finally, outputting the result through a multi-layer perceptron MLP to obtain the target node predicted value of the unit delay propagation layer.
More preferably, the loss function during training of the map neural network model based on RGAT in step S3 is composed of a loss function of predicted arrival time and transition time, a loss function of predicted link delay time and a loss function of predicted unit delay time, and the formulas are as follows:
(1)
Wherein the method comprises the steps ofIs a loss function of predicted arrival time and transition time,、The loss function of the predicted line delay time and the loss function of the predicted unit delay time are respectively;
(2)
Wherein the method comprises the steps ofIs the number of all nodes in the directed graph,Is a concatenation of the arrival time actual value and the conversion time actual value,Splicing the arrival time predicted value and the conversion time predicted value;
(3)
Wherein the method comprises the steps ofIs the number of fan-in nodes in the directed graph,Is the actual value of the link delay time,Is a predicted value of the delay time of the connection;
(4)
Wherein the method comprises the steps ofIs the number of cell edges in the directed graph,Is the actual value of the cell delay time,Is a unit delay time prediction value.
The beneficial effects of the invention are as follows:
The node characteristic updating in the graph embedding stage is carried out by adopting RGAT (Relational Graph Attention Network) technical means, different weights are distributed for different relations by considering influence of different neighbor nodes and various types of edges (relations) in the directed graph, and the characteristics required by predicting the arrival time are effectively extracted. RGAT can allocate different weights for different relations in the circuit diagram, the refined weight processing mechanism improves the prediction capability of the model on the influence of complex factors such as crosstalk in the circuit diagram, and enhances the accuracy of arrival time prediction, especially considering the influence of neighbor nodes and adjacent side information on the arrival time.
In the invention, the predicted values of the arrival time and the conversion time of the last layer of connection propagation layer are utilized in the unit delay propagation layer of the delay propagation stage, the graph embedded information of the target node and the characteristic vector of the unit edge are utilized to predict the unit delay and the arrival time, and the process simulates the process of searching the unit delay of the modern static time sequence analysis (STA): and using the conversion time, namely the predicted value of the conversion time of the last layer of connection propagation layer, outputting the graph embedded information of the capacitor, namely the target node, as the index value input in the process of searching the unit delay, and matching and checking the index value of the LUT and the unit delay value, namely the unit edge feature vector, to obtain the predicted unit delay. The LUT has high dimensionality, the characteristic dimension of the unit edge is as high as 512, and compared with the process of simulating the modern STA to calculate the unit delay by using an interpolation algorithm, the LUT does not involve inter-high-dimensional matrix multiplication, the complexity of the model and the reasoning time of the model are greatly reduced, and the accuracy of the model prediction unit delay and the arrival time is improved.
Drawings
Fig. 1 is a flowchart of a pre-wiring time sequence prediction method based on a graph neural network.
Fig. 2 is a diagram node and edge division of a circuit diagram in S1 in the pre-wiring timing prediction method based on a neural network of the present invention.
Fig. 3 is a schematic diagram of S301 graph embedding in the pre-wiring timing prediction method based on the graph neural network provided by the present invention.
Fig. 4 is a schematic diagram of a delay propagation layer of a connection line of S302 in the pre-wiring timing prediction method based on the neural network according to the present invention.
Fig. 5 is a schematic diagram of a cell delay propagation layer of S302 in the pre-wiring timing prediction method based on the neural network according to the present invention.
Detailed Description
The principle and features of the pre-wiring timing prediction method based on a neural network according to the present invention will be described in further detail with reference to the accompanying drawings, and the examples are only used for explaining the present invention, not limiting the scope of the present invention. It should be noted that the drawings are in a very simplified form and are all to a non-precise scale, merely for convenience and clarity in aiding in the description of embodiments of the invention. Furthermore, the structures shown in the drawings are often part of actual structures. In particular, the drawings are shown with different emphasis instead being placed upon illustrating the various embodiments.
The invention provides a pre-wiring time sequence prediction method based on a graph neural network, wherein a scheme flow chart is shown in fig. 1, and the method comprises the following steps:
S1, constructing a data set:
Constructing a directed graph according to the real reference circuit;
Acquiring a time sequence report of a real reference circuit by using open source software OpenROAD, and screening out characteristic parameters related to the arrival time;
Constructing a data set by using the directed graph and the characteristic parameters related to the arrival time, and setting a label at the same time, wherein the label adopts the arrival time, the unit delay time, the connection delay time and the conversion time of each device unit pin in the time sequence report;
The method specifically comprises the following sub-steps:
S101, taking pins of a device unit in a real reference circuit as nodes of a directed graph, taking a connecting line edge and a unit edge of the device unit as edges between nodes of the directed graph, namely, connecting the nodes, wherein the connecting line edge is a connecting line between the two device units, and is set to be a bidirectional edge which is a connecting line outgoing edge and a connecting line incoming edge respectively, wherein the connecting line outgoing edge refers to an edge of an output pin of the device unit connected to an input pin of another device unit, and the connecting line incoming edge and the connecting line outgoing edge are opposite in direction, and refer to an edge of an input pin of the device unit connected to an output pin of another device unit;
Fig. 2 shows a schematic diagram of a circuit converted into a graph format of a graph neural network, wherein pins of units in the circuit are used as nodes of the graph, connection lines between the units are used as connection edges, and connection relations between input pins and output pins of the units are used as unit edges. The connection line side is a bidirectional side, and the unit side is a unidirectional side pointing from the input pin to the output pin.
S102, obtaining an adjacency matrix A of the directed graph according to the connection relation among nodes of the directed graph, wherein the adjacency matrix reflects the connection relation among the nodes, 1 represents connection and 0 represents disconnection;
s104, generating a time sequence report of a real reference circuit, and screening out characteristic parameters related to the arrival time according to the time sequence report;
the characteristic parameters related to the arrival time comprise node characteristics, connection line edge characteristics and unit edge characteristics, wherein the node characteristics comprise distances relative to 4 boundaries (an upper boundary, a left boundary, a right boundary and a lower boundary) of a chip in a real reference circuit, pin capacitance, a pin type and a node type, the pin type comprises a PI pin and a PO pin, the node type comprises a fan-in node and a fan-out node, the connection line edge characteristics comprise distances between two nodes along the X axis or the Y axis, and the unit edge characteristics comprise index values of an LUT lookup table and delay values of the LUT lookup table.
S2, performing data cleaning and normalization processing on the generated data set, and dividing the processed data set into a 2/3 training set and a 1/3 testing set;
The data cleansing includes processing outliers for the time-of-arrival related feature parameters, setting all outliers to 0, where the outliers include values that are significantly outside of the normal range and invalid values.
The normalization is that the label is subjected to Min-Max normalization, and the Min-Max normalization calculation formula is as follows:
Wherein the method comprises the steps of Is the value of the original data and,Is the maximum value in the data and,As the minimum value in the data,Is the normalized data value.
S3, constructing a map neural network model based on RGAT, dividing the model into two stages, namely map embedding and delay propagation, and initializing parameters of the model;
Specifically, the RGAT-based graph neural network model includes a graph embedding stage and a delay propagation stage;
(1) The graph embedding stage is shown in FIG. 3, in which node characteristics are updated using RGAT of the layer 3 residual connections for all nodes in the directed graph;
The input of the first layer of the multi-layer residual connection RGAT is a node characteristic. The inputs of the other layers except the first layer are the outputs of the previous layer. Each layer RGAT updates the input features and adds the input features to the updated features through the residual connection, the result of which is the output of this layer.
The updating of the input features by each layer RGAT comprises an attention head feature fusion stage, a relation head feature fusion stage and a fusion stage;
the mathematical description of the attention head feature fusion phase is as follows:
Wherein, Represent the firstLayer nodeNew features of the node features of (a) after the attention head features are fused; The number of heads representing attention; Representation pair The attention results of the different heads are spliced; Representing nodes Is a neighbor node of (a); Is composed of A pair of adjacent nodes of a layerAndFirst, theAttention weights calculated by the attention heads; Is the first Layer numberA weight matrix of the individual attention heads; Represent the first Layer nodeIs described.
The mathematical description of the relationship head feature fusion stage is as follows:
Wherein, Representing nodesIn the first placeFeature vectors of the layer after the feature of the layer is subjected to relationship head feature fusion; representing the number of relationship heads; Is composed of A pair of adjacent nodes of a layerAndFirst, theThe normalized attention coefficient obtained by calculation of each relation head; Represent the first Layer numberA weight matrix of the relationship head; Representing nodes And nodeFeature vectors embedded in the dependency relationship; representation of Activating a function;、 In order for the weight matrix to be learnable, 、Is a bias term;
The fusion stage is used for splicing the feature vector after the attention head feature fusion and the feature vector after the relationship head feature fusion, and linear transformation are adopted Residual connection is carried out on the result after the function is activated and the input of the current layer, so that updated node characteristics are obtained, and the mathematical description is as follows:
Wherein, Is a stitching operation between features; Represent the first Layer nodeUpdated features; as a matrix of weights that can be learned, Is a bias term; Represent the first Layer nodeUpdated features, i.e. the firstLayer input.
The mathematical description of the residual connection is as follows:
Wherein, Is an input to which the user is exposed,Is the output obtained by the transformation of the current layer,Is the output of the layer after the residual connection.
The result output by the last layer RGAT is obtained through a multi-layer perceptron MLP, the pre alpha vector dimension of the updated node feature is set as a predicted value of the link delay time, and alpha=4 is obtained.
(2) The delay propagation stage is to analyze the topology layer of the directed graph after the graph embedding stage, take the embedded fusion feature as input, start from the initial layer of the topology layer and realize the information propagation of the line outgoing side or the unit side layer by layer, wherein the information propagation of the line outgoing side and the unit side is respectively realized by a set line delay propagation layer and a unit delay propagation layer until reaching the termination layer of the topology layer, and the embedded fusion feature is the result after the initial node feature and the node feature updated in the graph embedding stage are spliced. The model takes a predicted value of a source node, an embedded fusion characteristic of the source node and an embedded fusion characteristic of a target node of a connecting line outlet as input in a connecting line delay propagation layer, obtains a predicted value of arrival time and conversion time of a pin through MLP output, achieves information transmission on the connecting line side, simulates the influence of signal propagation and delay in an actual circuit, and takes the predicted value of the target node, the embedded fusion characteristic of the source node and the embedded fusion characteristic of the target node and the unit edge characteristic of the unit edge as input in a unit delay propagation layer to learn and select the delay value of the unit table. This method is similar to the cell delay lookup method in static timing analysis. And then, sending the calculated unit side information into two reduction channels, and carrying out summation and maximum value operation. The calculated pin feature vector is output through the MLP to obtain the predicted value of the arrival time and the conversion time of the pin.
The path of the timing report analysis is composed of circuit connection lines and device units alternately, so that after the circuit is converted into a directed graph, the topological hierarchy structure of the directed graph is arranged alternately according to the connection line sides and the unit sides, and the starting point of the timing report analysis is usually set as the signal transmission starting position in the circuit connection lines, so that the initial layers of the topological layers of the directed graph are all composed of source nodes with connection line out sides. The source node is the starting point of the edge in the directed graph, and the target node is the ending point of the edge in the directed graph.
(2.1) In the wire delay propagation layers, the input of each wire delay propagation layer is the source node predicted value of the current wire outlet, the embedded fusion characteristic of the source node and the embedded fusion characteristic of the target node, wherein the source node predicted value of the wire outlet adopts the target node predicted value of the last unit delay propagation layer, and the source node predicted value of the first wire delay propagation layer is initialized to 0;
And as shown in fig. 4, splicing the source node predicted value of the current connecting edge, the embedded fusion characteristic of the source node and the embedded fusion characteristic of the target node, and finally outputting the target node predicted value through the multi-layer perceptron MLP to obtain the target node predicted value, wherein the target node predicted value comprises the predicted value of the arrival time and the predicted value of the conversion time.
The mathematical description of the link delay propagation layer is as follows:
Wherein, A target node predicted value representing the outgoing edge of the connecting line; A source node predicted value representing the outgoing edge of the connecting line; And And respectively representing the embedded fusion characteristics of the connecting line edge-out source node and the embedded fusion characteristics of the connecting line edge-out target node.
In the unit delay propagation layers, the input of each unit delay propagation layer is the source node predicted value of the current unit side, the embedded fusion characteristic of the source node, the embedded fusion characteristic of the target node and the unit side characteristic, as in the step (2), the topological hierarchical structure of the directed graph is alternately arranged according to the wire side and the unit side, and the initial layers of the topological layers of the directed graph are all composed of source nodes with wire outgoing sides, so that the first unit delay propagation layer inevitably exists in the last wire delay propagation layer, and the source node predicted value of the unit side adopts the target node predicted value of the last wire delay propagation layer;
And as shown in fig. 5, splicing the source node predicted value of the current connecting edge, the embedded fusion characteristic of the source node, the embedded fusion characteristic of the target node and the unit edge characteristic, and outputting the result through the multi-layer perceptron MLP.
The mathematical description of the splicing operation is as follows:
Wherein, Representing a predicted value of a unit edge source node; And Respectively representing the embedded fusion characteristics of the unit edge source nodes and the embedded fusion characteristics of the unit edge target nodes; Representing the cell edge features.
Then the output vector of the MLP is cut according to the set proportion and divided into four parts, wherein the first part is a weight parameter with the length of 1, the second part and the third part are two groups of intermediate features with the same length, and the fourth part is used as a unit delay time predicted value.
The mathematical description of the slicing operation of the output vector of the MLP is as follows:
Wherein, Representing a segmentation vectorIs a first value of (a); Representing the slave vector Starting to split the second value of (2) for a split length of;Representing the slave vectorIs the first of (2)The individual values start to be split, the splitting length is;A unit delay prediction value representing a unit edge; Representing the slave vector Is the first of (2)The values start to be split, and the splitting length is the vector dimension of the unit delay。
The first partial result (i.e. weight parameter) is passed throughThe activation function is processed and then multiplied by a second part and a third part (namely two groups of intermediate features) respectively to obtain two groups of weighted intermediate features, the two groups of weighted intermediate features of all the unit edges connected to the same target node are subjected to summation and maximum value calculation respectively, the values obtained by the summation and maximum value calculation are spliced, and finally the target node predicted value of the unit delay propagation layer is obtained through the output of a multi-layer perceptron MLP, and the mathematical description of the process is as follows:
Wherein, Representing a predicted value of a unit edge target node; Representing all connections to the same target node Is a set of cell edges; And Respectively representing the summation operation and the maximum operation of the feature set; representation of U represents an edge source node;
s4, inputting a training set into the map neural network model based on RGAT, and then performing iterative training by using an Adam optimization algorithm to obtain a trained map neural network model, wherein the method specifically comprises the following steps:
Loss function for whole using Adam optimization algorithm Optimizing, wherein the integral loss function consists of a loss function of predicted arrival time and conversion time, a loss function of predicted link delay time and a loss function of predicted unit delay time, and the formula is as follows:
Wherein the method comprises the steps of Is a loss function of predicted arrival time and transition time,,The loss function of the predicted link delay time and the loss function of the predicted cell delay time, respectively.
Wherein the method comprises the steps ofIs the number of all nodes in the directed graph,Is a concatenation of the arrival time true value and the conversion time true value (tag value),Is a concatenation of arrival time predictions and transition time predictions.
Wherein the method comprises the steps ofIs the number of fan-in nodes in the directed graph,Is the actual value of the link delay time,Is a predicted value of the link delay time.
Wherein the method comprises the steps ofIs the number of cell edges in the directed graph,Is the actual value of the cell delay time,Is a unit delay time prediction value.
And obtaining a post-wiring time sequence result of the circuit according to the arrival time predicted value and the conversion time predicted value predicted by the wire delay propagation layer, the unit delay time predicted value predicted by the unit delay propagation layer and the wire delay time predicted value predicted by the graph embedding stage.
And S5, model evaluation, namely inputting the test set into the trained graph neural network model to obtain a comparison result of the predicted arrival time and the real arrival time of the graph neural network model based on RGAT, and calculating an evaluation index to evaluate the performance of the graph neural network model. The evaluation index adopts a determination coefficient%). When (when)The closer to 1, the better the model fits the data, and the predicted value is highly correlated with the actual observed value.
The experimental environment parameters of the graph neural network model for predicting the arrival time of the time sequence end point after wiring are presented in the invention are as follows in table 1:
TABLE 1
The predicted results of the trained model on the test set, and the time it takes for the model to infer the arrival time are as follows in Table 2:
TABLE 2
While the fundamental and principal features of the invention and advantages of the invention have been shown and described, it will be apparent to those skilled in the art that the invention is not limited to the details of the foregoing exemplary embodiments, but may be embodied in other specific forms without departing from the spirit or essential characteristics thereof. The present embodiments are, therefore, to be considered in all respects as illustrative and not restrictive, the scope of the invention being indicated by the appended claims rather than by the foregoing description, and all changes which come within the meaning and range of equivalency of the claims are therefore intended to be embraced therein. Any reference sign in a claim should not be construed as limiting the claim concerned.
Claims (4)
1. A circuit pre-wiring timing prediction method based on a graph neural network, the method comprising:
step S1, constructing a data set, which specifically comprises the following steps:
Constructing a directed graph according to the real reference circuit;
acquiring a time sequence report of a real reference circuit, and screening out characteristic parameters related to the arrival time;
constructing a data set by using the directed graph and the characteristic parameters related to the arrival time, and setting a label at the same time, wherein the label comprises the arrival time, the unit delay time, the connection delay time and the conversion time of each device unit pin in the time sequence report;
step S2, performing data cleaning and normalization processing on the generated data set, and dividing the processed data set into a training set and a testing set;
Step S3, constructing a map neural network model based on RGAT, and training and testing the map neural network model by using a training set and a testing set;
s4, predicting a post-wiring time sequence result of the circuit by using a trained and tested map neural network model based on RGAT;
the step S1 specifically comprises the following steps:
S101, taking pins of a device unit in a real reference circuit as nodes of a directed graph, taking a connecting line edge and a unit edge of the device unit as edges between the nodes of the directed graph, namely, connecting the nodes, wherein the connecting line edge is a connecting line between two device units and is set to be a bidirectional edge;
S102, obtaining an adjacency matrix A of the directed graph according to the connection relation among the nodes of the directed graph;
S103, generating a time sequence report of a real reference circuit, and screening out characteristic parameters related to the arrival time according to the time sequence report;
The map neural network model based on RGAT in step S3 includes a map embedding stage and a delay propagation stage;
the graph embedding stage is to update node characteristics by RGAT using multi-layer residual error connection for all nodes in the directed graph;
the delay propagation stage analyzes the topology layer of the directed graph, and starts from the initial layer of the topology layer, the information propagation of the wire outgoing side or the unit side is realized layer by layer;
Step S3, the input of the first layer of the multi-layer residual connection RGAT in the embedding stage is node characteristics, the input of other layers except the first layer is the output of the upper layer, each layer RGAT updates the input characteristics, adds the input characteristics and the updated characteristics through residual connection, and adds the added result as the output of the layer;
The updating of the input features by each layer RGAT comprises an attention head feature fusion stage, a relation head feature fusion stage and a fusion stage;
The fusion stage is used for splicing the feature vector after the attention head feature fusion and the feature vector after the relationship head feature fusion, and carrying out residual connection on the result after the linear transformation and relu activation function and the input of the current layer to obtain updated node features;
In the step S3, in the wire delay propagation layer in the delay propagation stage, the input of each wire delay propagation layer is the source node predicted value of the current wire edge, the embedded fusion characteristic of the source node and the embedded fusion characteristic of the target node, wherein the source node predicted value of the wire edge adopts the target node predicted value of the last unit delay propagation layer, and the source node predicted value of the first wire delay propagation layer is initialized to 0;
splicing a source node predicted value of a current connecting edge, an embedded fusion characteristic of a source node and an embedded fusion characteristic of a target node, and finally outputting the target node predicted value through a multi-layer perceptron MLP (multi-layer perceptron) to obtain a target node predicted value, wherein the predicted value comprises a predicted value of arrival time and a predicted value of conversion time;
In the step S3, in the unit delay propagation layer in the delay propagation stage, the input of each unit delay propagation layer is the source node predicted value of the current unit side, the embedded fusion characteristic of the source node, the embedded fusion characteristic of the target node and the unit side characteristic, wherein the source node predicted value of the unit side adopts the target node predicted value of the last line delay propagation layer;
Splicing the source node predicted value of the current unit edge, the embedded fusion characteristic of the source node, the embedded fusion characteristic of the target node and the unit edge characteristic, and outputting the result through a multi-layer perceptron MLP;
then, the output vector of the multi-layer perceptron MLP is subjected to segmentation operation and is divided into four parts, wherein the first part is a weight parameter with the length of 1, the second part and the third part are two groups of intermediate features with equal length, and the fourth part is used as a unit delay time predicted value;
The first partial result is passed through The two groups of weighted intermediate features connected to the unit edges of the same target node are respectively subjected to summation operation and maximum value operation, summation operation results and maximum value operation results are spliced, and finally target node predicted values of the unit delay propagation layer are obtained through MLP output of a multi-layer perceptron;
Step S3 is based on RGAT the loss function of the graph neural network model training is composed of the loss function of the predicted arrival time and the conversion time, the loss function of the predicted link delay time and the loss function of the predicted unit delay time, and the formula is as follows:
(1)
Wherein the method comprises the steps ofIs a loss function of predicted arrival time and transition time,、The loss function of the predicted line delay time and the loss function of the predicted unit delay time are respectively;
(2)
Wherein the method comprises the steps ofIs the number of all nodes in the directed graph,Is a concatenation of the arrival time actual value and the conversion time actual value,Splicing the arrival time predicted value and the conversion time predicted value;
(3)
Wherein the method comprises the steps ofIs the number of fan-in nodes in the directed graph,Is the actual value of the link delay time,Is a predicted value of the delay time of the connection;
(4)
Wherein the method comprises the steps ofIs the number of cell edges in the directed graph,Is the actual value of the cell delay time,Is a unit delay time prediction value.
2. The method according to claim 1, wherein the characteristic parameters related to the arrival time in step S103 include node characteristics and unit edge characteristics.
3. The method of claim 1, wherein the node characteristics in step S103 include distances in a real reference circuit relative to 4 boundaries of a chip, pin capacitance, pin type, and node type, wherein the pin type includes PI pins and PO pins, wherein the node type includes fan-in nodes and fan-out nodes, and wherein the cell edge characteristics include index values and delay values of an LUT lookup table.
4. The method according to claim 1, characterized in that the initial layer of the topology layer of the directed graph in step S3 delay propagation phase is constituted by source nodes of the outgoing edge of the connection.
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN202411320123.3A CN118839658B (en) | 2024-09-23 | 2024-09-23 | A method for timing prediction before circuit wiring based on graph neural network |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN202411320123.3A CN118839658B (en) | 2024-09-23 | 2024-09-23 | A method for timing prediction before circuit wiring based on graph neural network |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| CN118839658A CN118839658A (en) | 2024-10-25 |
| CN118839658B true CN118839658B (en) | 2024-12-27 |
Family
ID=93149923
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| CN202411320123.3A Active CN118839658B (en) | 2024-09-23 | 2024-09-23 | A method for timing prediction before circuit wiring based on graph neural network |
Country Status (1)
| Country | Link |
|---|---|
| CN (1) | CN118839658B (en) |
Citations (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN115293082A (en) * | 2022-09-30 | 2022-11-04 | 深圳鸿芯微纳技术有限公司 | Training and predicting method, device, equipment and storage medium of time sequence prediction model |
| CN117473943A (en) * | 2023-10-30 | 2024-01-30 | 中国科学技术大学 | A method for generating connectivity graphs in chip wiring |
Family Cites Families (4)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US11403700B2 (en) * | 2019-04-23 | 2022-08-02 | Target Brands, Inc. | Link prediction using Hebbian graph embeddings |
| US11651194B2 (en) * | 2019-11-27 | 2023-05-16 | Nvidia Corp. | Layout parasitics and device parameter prediction using graph neural networks |
| CN118606940B (en) * | 2024-05-24 | 2025-03-07 | 北京时代民芯科技有限公司 | Trojan horse detection method for FPGA netlist based on graph neural network |
| CN118607434A (en) * | 2024-06-07 | 2024-09-06 | 华南理工大学 | A pre-routing time series prediction system based on graph neural network |
-
2024
- 2024-09-23 CN CN202411320123.3A patent/CN118839658B/en active Active
Patent Citations (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN115293082A (en) * | 2022-09-30 | 2022-11-04 | 深圳鸿芯微纳技术有限公司 | Training and predicting method, device, equipment and storage medium of time sequence prediction model |
| CN117473943A (en) * | 2023-10-30 | 2024-01-30 | 中国科学技术大学 | A method for generating connectivity graphs in chip wiring |
Also Published As
| Publication number | Publication date |
|---|---|
| CN118839658A (en) | 2024-10-25 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| CN109120462B (en) | Method, apparatus, and readable storage medium for predicting an opportunistic network link | |
| CN114615019A (en) | Anomaly detection method and system based on micro-service topological relation generation | |
| CN114186519B (en) | Timing bottleneck detection method, device, terminal equipment and storage medium | |
| CN118884191A (en) | Integrated circuit testing method and system | |
| CN115130544A (en) | Data classification method and device based on multi-head self-attention hypergraph neural network | |
| CN116151324A (en) | RC interconnection delay prediction method based on graph neural network | |
| CN114626506A (en) | A neural network unit structure search method and system based on attention mechanism | |
| CN112348269A (en) | A Time Series Predictive Modeling Method Fusion Graph Structure | |
| CN111756587A (en) | A method for predicting temporal network links using GraphSAGE | |
| CN114821420A (en) | Temporal Action Localization Method Based on Multi-Temporal Resolution Temporal Semantic Aggregation Network | |
| CN115438575B (en) | Analysis method for high-precision airfoil flow field prediction | |
| CN116484016A (en) | A time series knowledge graph reasoning method and system based on automatic maintenance of time series paths | |
| CN118839658B (en) | A method for timing prediction before circuit wiring based on graph neural network | |
| CN119173876A (en) | Method and apparatus for electronic design automation | |
| CN118607434A (en) | A pre-routing time series prediction system based on graph neural network | |
| CN118802473A (en) | Equipment failure root cause location method, device, equipment, storage medium and product | |
| CN113065321A (en) | User behavior prediction method and system based on LSTM model and hypergraph | |
| CN116861782B (en) | Line delay prediction method based on machine learning and node effective capacitance | |
| CN115664976B (en) | A key node identification method based on network generalized energy and information entropy | |
| CN117376097A (en) | Root alarm positioning method, device, electronic equipment and readable medium | |
| CN116542634A (en) | Work order processing method, apparatus and computer readable storage medium | |
| CN117093712A (en) | Text classification method based on multi-display diagram attention network model | |
| CN118152842A (en) | A Classification and Device for Dialogue Text | |
| CN116302088A (en) | A code clone detection method, storage medium and device | |
| CN115510335A (en) | Graph neural network session recommendation method fusing correlation information |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| PB01 | Publication | ||
| PB01 | Publication | ||
| SE01 | Entry into force of request for substantive examination | ||
| SE01 | Entry into force of request for substantive examination | ||
| GR01 | Patent grant | ||
| GR01 | Patent grant |