# US 2021/0342516 A1 · Routing connections in integrated circuits based on reinforcement learning

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2021/0342516 A1
- Document ID: US20210342516A1
- Status: Published application
- Kind: A1
- Application number: 17/230,016
- Filed: 2021-04-14
- Published: 2021-11-04
- Earliest claimed: 2020-05-04
- Assignees: NVIDIA Corporation
- Applicants: Nvidia Corporation
- Inventors: Haoxing Ren; Matthew Fojtik
- Web page: https://patentgrep.com/patent/US20210342516A1

## CPC

- G06F 30/394: Routing (G06F30/396 takes precedence)
- G06F 30/27: using machine learning, e.g. artificial intelligence, neural networks, support vector machines [SVM] or training a model
- G06N 3/006: based on simulated virtual individual or collective life forms, e.g. social simulations or particle swarm optimisation [PSO]
- G06N 3/04: Architecture, e.g. interconnection topology
- G06N 3/045: Combinations of networks
- G06N 3/0464: Convolutional networks [CNN, ConvNet]
- G06N 3/08: Learning methods
- G06N 3/084: Backpropagation, e.g. using gradient descent
- G06N 3/092: Reinforcement learning
- G06N 3/096: Transfer learning
- G06N 3/048: Activation functions
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)
- G06N: COMPUTING ARRANGEMENTS BASED ON SPECIFIC COMPUTATIONAL MODELS

## Abstract

The disclosure provides a general solution for determining connections between terminals of various types of circuits using machine learning (ML). A ML method that uses reinforcement learning (RL), such as deep RL, to determine and optimize routing of circuit connections using a game process is provided. In one example a method of determining routing connection includes: (1) receiving a circuit design having known terminal groups, (2) establishing terminal positions for the terminal groups in a routing environment, and (3) determining, by the RL agent, routes of nets between the known terminal groups employing a model that is independent of a number of the nets of the circuit. A method of creating a model for routing nets using RL, a method of employing a game for training a RL agent to determine routing connections, and a RL agent for routing connections of a circuit are also disclosed.

## Claims

### Claim 1

A method of creating a model for routing nets of circuits using reinforcement learning, comprising:
creating a first image that represents connecting a group of terminals of a circuit in a routing environment using a net and a second image that represents blockages in the routing environment for the connecting, wherein the first and second images have multiple routing layers and are created for at least some of the nets of the circuit;
creating, using a neural network (NN), a feature space image for the at least some of the nets based on the first and second images of the at least some of the nets; and
creating a policy function that provides a probability for choosing a routing action for connecting the group of terminals based on the feature space image of the at least some of the nets, wherein parameters of the policy function are independent of a number of the nets of the circuit.

### Claim 2 (depends on 1)

The method as recited in claim 1, wherein the feature space image for the at least some of the nets is defined by a height and width.

### Claim 3 (depends on 2)

The method as recited in claim 2, wherein the height or width for multiple of the feature space images are different.

### Claim 4 (depends on 1)

The method as recited in claim 1, further comprising creating a value function, based on a pooling of the feature space image of the at least some of the nets, that provides a value predictor for a current routing state for the group of terminals.

### Claim 5 (depends on 4)

The method as recited in claim 4, wherein the creating the value function includes applying a vector generated by the pooling to fully connected layers (FC) and nonlinear layer (ReLu) of the NN to provide a single value for the value predictor.

### Claim 6 (depends on 4)

The method as recited in claim 4, wherein the creating the value function is based on a pooling of the feature space image of all of the nets.

### Claim 7 (depends on 1)

The method as recited in claim 1, wherein the creating the policy function includes applying the feature space image of at least some of the nets to fully connected layers (FC) and non-linear layers (ReLu) of the NN to create an array with outputs, combining all the outputs of the at least some of the nets to generate a combined output, and providing the combined output to a softmax layer of the NN to create the probability for choosing a routing action.

### Claim 8 (depends on 1)

The method as recited in claim 1, wherein the creating the first and second images is for all of the nets, the creating the feature space image is for all of the nets, and the creating the policy function is based on the feature space image of all of the nets.

### Claim 9 (depends on 1)

The method as recited in claim 1, wherein the routing layers at least include a terminal layer, a vertical layer, and a horizontal layer.

### Claim 10 (depends on 1)

The method as recited claim 1, wherein at least one of the routing layers is a multiple-direction routing layer.

### Claim 11 (depends on 1)

The method as recited in claim 1, wherein the routing environment is a three dimensional grid.

### Claim 12 (depends on 1)

The method as recited in claim 1, wherein an initial number of the nets is two.

### Claim 13 (depends on 1)

The method as recited in claim 1, wherein the parameters of the policy function are additionally independent of a size of the circuit.

### Claim 14 (depends on 1)

The method as recited in claim 1, wherein the NN is a graph neural network (GNN).

### Claim 15 (depends on 1)

The method as recited in claim 1, wherein the NN is a convolutional neural network (CNN).

### Claim 16

A method of training a Reinforcement Learning (RL) agent, employing a game, to determine routing connections for circuits, comprising:
observing, by the RL agent, a current routing state between terminal positions of a circuit in a routing environment;
providing, from the RL agent to the routing environment, a routing action that changes the current routing state between the terminal positions, wherein the RL agent provides the routing action based on a model for routing nets that is independent of a number of the nets of the circuit;
evaluating, by the routing environment, the routing action; and
providing, from the routing environment to the RL agent, one or more reward based on the evaluating.

### Claim 17 (depends on 16)

The method as recited in claim 16, wherein a number of the nets for the model is two.

### Claim 18 (depends on 17)

The method as recited in claim 17, wherein the method is repeated multiple times and the number of the nets and a size of the circuit incrementally increase during the multiple times to create additional models for the method of training.

### Claim 19 (depends on 16)

The method as recited in claim 16, wherein the model provides a probability for choosing routing actions for connecting the terminal positions based on a feature space image of the nets and provides a value predictor for a current routing state for the terminal positions based on a pooling of the feature space image of the nets.

### Claim 20 (depends on 16)

The method as recited in claim 16, wherein the RL agent is implemented using a Proximal Policy Optimization algorithm.

### Claim 21 (depends on 16)

The method as recited in claim 16, wherein the RL agent optimizes routing between the terminal positions based on the one or more rewards.

### Claim 22 (depends on 16)

The method as recited in claim 16, wherein the one or more awards include a reward that indicates legality of a routing action, an award that indicates whether the routing action created a connected routing segment, and an award that indicates when a net is fully routed.

### Claim 23 (depends on 16)

The method as recited in claim 16, wherein the model for routing nets is independent of the number of the nets of the circuit and a size of the circuit.

### Claim 24

A method of determining routing connections between terminals of a circuit employing a game process for a Reinforcement Learning (RL) agent, comprising:
receiving a circuit design having known terminal groups;
establishing terminal positions for the known terminal groups in a routing environment; and
determining, by the RL agent, routes of nets between the known terminal groups employing a model that is independent of a number of the nets of the circuit.

### Claim 25 (depends on 24)

The method as recited in claim 24, wherein the determining includes receiving routing actions from the RL agent that change routing states, evaluating the routing actions in the routing environment, rewarding the RL agent with one or more rewards based on the evaluating, and selecting routing actions for the routes of the nets based on the one or more rewards.

### Claim 26 (depends on 25)

The method as recited in claim 25, wherein the determining further includes the RL agent computing the probability of the routing actions and selecting routing actions to send to the routing environment that have a higher probability than remaining ones of the routing actions.

### Claim 27 (depends on 25)

The method as recited in claim 25, wherein the one or more rewards are provided by the routing environment and include a reward that indicates legality of the routing action, a reward that indicates whether the routing action created a connected routing segment between a pair of the known terminal groups, and a reward that indicates when a net is fully routed.

### Claim 28 (depends on 27)

The method as recited in claim 27, wherein the one or more rewards further include a reward for design rule checks.

### Claim 29 (depends on 24)

The method as recited in claim 24, wherein the determining the routes of the nets is performed by inferencing the model.

### Claim 30 (depends on 24)

The method as recited in claim 24, wherein the method is an automated method.

### Claim 31 (depends on 24)

The method as recited in claim 24, wherein the model is independent of the number of the nets of the circuit and a size of the circuit.

### Claim 32 (depends on 24)

A cell library including standard cells created by the method of claim 24.

### Claim 33 (depends on 32)

A GPU constructed using one or more of the standard cells of claim 32.

### Claim 34 (depends on 24)

A computer program product having a series of operating instructions stored on a non-transitory computer-readable medium that directs a processor when executed thereby to perform operations to execute the method of claim 24.

### Claim 35 (depends on 24)

A design flow that incorporates the method of claim 24.

### Claim 36 (depends on 24)

A system including a processor that performs at least some of the steps of the method of claim 24.

### Claim 37

A Reinforcement Learning (RL) Agent for routing connections of a circuit, comprising:
a function approximator that generates routing actions for connecting terminal groups of nets of the circuit based on probabilities for taking different routing actions, and send the routing actions to a routing environment; and
a learning processor that receives game images from the routing environment and provide therefrom parameters for the function approximator that are independent of a number of nets of the circuit.

### Claim 38 (depends on 37)

The RL agent as recited in claim 37, wherein the function approximator is one or more neural network and includes a policy network that employs the parameters and generates the routing actions.

### Claim 39 (depends on 37)

The RL agent as recited in claim 37, wherein the learning processor is one or more convolutional neural network.

### Claim 40 (depends on 37)

The RL agent as recited in claim 37, wherein the game images includes two images created for each of the nets, wherein one of the images is for the routing of one of the nets itself, and the other one of the images is for the routing of the other ones of the nets, which represents blockages to the routing of the one of the nets.

### Claim 41 (depends on 37)

The RL agent as recited in claim 37, wherein the parameters provided by the learning processor are independent of the number of nets of the circuit and a design size of the circuit.
