Methods and systems for congestion prediction in logic synthesis using graph neural networks

Patent metadata

Field	Value
Publication number	US-11675951-B2
Application number	US-202117334657-A
Country	US
Kind code	B2
Filing date	May 28, 2021
Priority date	May 28, 2021
Publication date	Jun 13, 2023
Grant date	Jun 13, 2023

Abstract

Method and system for assisting electronic chip design, comprising: receiving netlist data for a proposed electronic chip design, the netlist data including a list of circuit elements and a list of interconnections between the circuit elements; converting the netlist data to a graph that represents at least some of the circuit elements as nodes and represents the interconnections between the circuit elements as edges; extracting network embeddings for the nodes based on a graph topology represented by the edges; extracting degree features for the nodes based on the graph topology; and computing, using a graph neural network, a congestion prediction for the circuit elements that are represented as nodes based on the extracted network embeddings and the extracted degree features.

First claim

The invention claimed is:

1. A computer implemented method for assisting electronic chip design, comprising:
receiving netlist data for a proposed electronic chip design, the netlist data including a list of circuit elements and a list of interconnections between the circuit elements;
converting the netlist data to a graph that represents at least some of the circuit elements as nodes and represents the interconnections between the circuit elements as edges;
extracting network embeddings for the nodes based on a graph topology represented by the edges;
extracting degree features for the nodes based on the graph topology; and
computing, using a graph neural network, a respective congestion prediction for each of the circuit elements that are represented as nodes, based on the extracted network embeddings and the extracted degree features.

2. The method of claim 1 comprising partitioning the graph into a plurality of partitioned graphs that each comprise a respective subset of the nodes and edges, and wherein computing the respective congestion predictions is performed independently for each of the plurality of partitioned graphs.

3. The method of claim 1 comprising partitioning the graph into a plurality of partitioned graphs that each comprise a respective subset of the nodes and edges, wherein extracting the network embeddings for the nodes comprises performing a matrix factorization for each of the plurality of partitioned graphs.

4. The method of claim 3 wherein performing a matrix factorization for each of the plurality of partitioned graphs comprises non-linear spectral network embedding using a Laplacian matrix.

5. The method of claim 1 wherein extracting network embeddings for the nodes comprises applying a random-walk based embedding.

6. The method of claim 1 wherein the congestion prediction for each circuit element is indicative of a demand for wire routing tracks at a location corresponding a placement location for the circuit element of the proposed electronic chip design.

7. The method of claim 1 wherein the circuit elements included in the netlist includes macros, standard cells and chip terminals, wherein macros are larger than standard cells, and converting the netlist data to the graph comprises representing only the standard cells as nodes.

8. The method of claim 7 wherein converting the netlist data to the graph comprises generating a node feature vector that includes a set of attributes for each node, wherein the set of attributes includes dimensions of the standard cell represented by the node.

9. The method of claim 8 comprising concatenating the set of attributes, the degree features and the networks embeddings for each node to generate an enhanced node feature vector, wherein the graph neural network is configured to generate the respective congestion predictions based on the enhanced node feature vectors.

10. The method of claim 1 comprising generating a set of training data by performing circuit element placement based on a plurality of instances of netlist data, and determining, for each instance of netlist data respective ground truth congestion labels for circuit elements included in the netlist data; and
performing supervised training of the graph neural network using the set of training data.

11. A computer system comprising one or more processing units and one or more non-transitory memories storing instructions for execution by the one or more processing devices, wherein execution of the instructions causes the computer system to:
convert netlist data to a graph that represents circuit elements identified in the netlist data as nodes and represents the interconnections between the circuit elements identified in the netlist data as edges;
extract network embeddings for the nodes based on a graph topology represented by the edges;
extract degree features for the nodes based on the graph topology; and
compute, using a graph neural network, a respective congestion prediction for each of the circuit elements that are represented as nodes, based on the extracted network embeddings and the extracted degree features.

12. The system of claim 11 , wherein execution of the instructions further causes the computer system to partition the graph into a plurality of partitioned graphs that each comprise a respective subset of the nodes and edges, and wherein computing the respective congestion predictions is performed independently for each of the plurality of partitioned graphs.

13. The system of claim 11 , wherein execution of the instructions further causes the computer system to partition the graph into a plurality of partitioned graphs that each comprise a respective subset of the nodes and edges, wherein extracting the network embeddings for the nodes comprises performing a matrix factorization for each of the plurality of partitioned graphs.

14. The system of claim 13 , wherein performing a matrix factorization for each of the plurality of partitioned graphs comprises non-linear spectral network embedding using a Laplacian matrix.

15. The system of claim 11 , wherein extracting network embeddings for the nodes comprises applying a random-walk based embedding.

16. The system of claim 11 , wherein the congestion prediction for each circuit element is indicative of a demand for wire routing tracks at a location corresponding a placement location for the circuit element of the proposed electronic chip design.

17. The system of claim 11 , wherein the circuit elements included in the netlist includes macros, standard cells and chip terminals, wherein macros are larger than standard cells, and converting the netlist data to the graph comprises representing only the standard cells as nodes.

18. The system of claim 11 , wherein execution of the instructions causes the computer system to convert the netlist data to the graph by generating a node feature vector that includes a set of attributes for each node, wherein the set of attributes includes dimensions of the standard cell represented by the node.

19. The system of claim 11 , wherein execution of the instructions further causes the computer system to concatenate the set of attributes, the degree features and the networks embeddings for each node to generate an enhanced node feature vector, wherein the graph neural network is configured to generate the respective congestion predictions based on the enhanced node feature vectors.

20. A non-transitory computer readable medium storing instructions, wherein execution of the instructions by one or more processors of a computer system causes the computer system to:
receive netlist data for a proposed electronic chip design, the netlist data including a list of circuit elements and a list of interconnections between the circuit elements;
convert the netlist data to a graph that represents at least some of the circuit elements as nodes and represents the interconnections between the circuit elements as edges;
extract network embeddings for the nodes based on a graph topology represented by the edges;
extract degree features for the nodes based on the graph topology; and
compute using a graph neural network, a respective congestion prediction for each of the circuit elements that are represented as nodes, based on the extracted network embeddings and the extracted degree features.

Assignees

• Ghose Amur
• Zhang Yingxue
• Zhang Zhanguang
• Huawei Tech Co Ltd

Inventors

• Ghose Amur
• Zhang Yingxue
• Zhang Zhanguang

Classifications

• G06F30/3947

  global · CPC title

• G06F18/29

  Graphical models, e.g. Bayesian networks · CPC title

• G06F30/392 Primary

  Floor-planning or layout, e.g. partitioning or placement · CPC title

• G06F30/398

  Design verification or optimisation, e.g. using design rule check [DRC], layout versus schematics [LVS] or finite element methods [FEM] (optical proximity correction [OPC] design processes G03F1/36) · CPC title

• G06F18/2163

  Partitioning the feature space · CPC title