Maximum turn constraint for routing of integrated circuit designs

A method comprising:

• accessing, from memory, data describing an integrated circuit design, the design comprising a net specifying a connection between a first pin and a second pin;
• receiving, from a user, a maximum turn constraint for the integrated circuit design, the maximum turn constraint specifying a maximum number of turns for connection paths generated in routing the integrated circuit design;
• routing the net based on the maximum turn constraint, the routing of the net resulting in a routed net comprising a connection path between the first pin and the second pin, the connection path comprising a number of turns that satisfy the maximum turn constraint, the routing of the net comprising:
• identifying, based on a grid graph representing the net, one or more paths between the first pin and the second pin that satisfy the maximum turn constraint, the grid graph comprising a plurality of grid cells and a plurality of edges, the plurality of grid cells being organized into rows and columns, each edge of the plurality of edges connecting two grid cells and being associated with an edge score representing an availability of routing resources, the identifying of the one or more paths comprising performing score propagation in a vertical direction, the performing of score propagation in the vertical direction comprising:
• determining a first edge score associated with a first edge between a first grid cell and a second grid cell that is adjacent to the first grid cell in a column of the grid graph;
• determining a first cell score associated with the first edge;
• and
• setting a second cell score associated with the second grid cell based on a sum of the first edge score and the first cell score;
• and
• selecting, from the one or more paths, the connection path between the first pin and the second pin based on a routing score determined for each of the one or more routes;
• and
• generating a layout instance for the integrated circuit design based in part on the routed net, the layout instance describing physical layout dimensions of the integrated circuit design.

A computer storage medium storing instructions, which when executed by a machine, cause the machine to perform operations comprising:

• accessing, from memory, data describing an integrated circuit design, the integrated circuit design comprising a net specifying a connection between a first pin and a second pin;
• receiving, from a user, a maximum turn constraint for the integrated circuit design, the maximum turn constraint specifying a maximum number of turns for connection paths generated in routing the integrated circuit design;
• routing the net based on the maximum turn constraint, the routing of the net resulting in a routed net comprising a connection path between the first pin and the second pin, the connection path comprising a number of turns that satisfy the maximum turn constraint, the routing of the net comprising:
• identifying, based on a grid graph representing the net, one or more paths between the first pin and the second pin that satisfy the maximum turn constraint, the grid graph comprising a plurality of grid cells and a plurality of edges, the plurality of grid cells being organized into rows and columns, each edge of the plurality of edges connecting two grid cells and being associated with an edge score representing an availability of routing resources, the identifying of the one or more paths comprising performing score propagation in a vertical direction, the performing of score propagation in the vertical direction comprising:
• determining a first edge score associated with a first edge between a first grid cell and a second grid cell that is adjacent to the first grid cell in a column of the grid graph;
• determining a first cell score associated with the first edge;
• and
• setting a second cell score associated with the second grid cell based on a sum of the first edge score and the first cell score;
• and
• selecting, from the one or more paths, the connection path between the first pin and the second pin based on a routing score determined for each of the one or more routes;
• and
• updating the data describing the integrated circuit design based in part on the routed net.