Optimizing Place-and-Routing Using a Random Normalized Polish Expression

A method comprising:

• generating a first random normalized polish expression;
• using at least one computer processor, using the first random normalized polish expression, generating a first place-and-route placement of cells for an integrated circuit design;
• placing each cell of the first place-and-route placement adjacent to each other in a one direction based on the first random normalized polish expression;
• for the first place-and-route placement, generating a plurality of interconnect routing paths between cells of the first place-and-route placement, wherein each interconnect routing path can be formed on different interconnect layers;
• and
• determining a cost for each of the interconnect routing paths for the first place-and-route placement, wherein each of the plurality of interconnect routing paths comprises a first place-and-route solution,
• wherein the first place-and-route solution comprises at least one interconnect line formed in a gap between a first cell and second cell,
• a second place-and-route solution comprises at least one interconnect line having a 90-degree turn coupling the first and second cells, and
• a third place-and-route solution comprises at least one interconnect line having at least two 90-degree turns coupling the first and second cells, and
• calculating a cost function for the first, second, and third place-and-route solutions;
• based the calculating a cost function, selecting one of the first, second, and third place-and-route solutions.

A method comprising:

• generating a first random normalized polish expression;
• using at least one computer processor, using the first random normalized polish expression, generating a first place-and-route placement of cells for an integrated circuit design;
• placing each cell of the first place-and-route placement adjacent to each other in a one direction based on the first random normalized polish expression;
• for the first place-and-route placement, generating a plurality of interconnect routing paths between cells of the first place-and-route placement, wherein each interconnect routing path can be formed on different interconnect layers;
• determining a cost for each of the interconnect routing paths for the first place-and-route placement, wherein each of the plurality of interconnect routing paths comprises a first place-and-route solution;
• generating a second random normalized polish expression;
• using at least one computer processor, using the second random normalized polish expression, generating a second place-and-route solution for an integrated circuit design and a cost of the first place-and-route solution, wherein the cost includes a cost factor based on a wire length of interconnect in a space between two cells;
• and
• placing each cell of the second place-and-route solution adjacent to each other in a one direction based on the second random normalized polish expression.