Method for optimization of logic circuits for routability improvement

Abstract

Routability (or wiring congestion) in a VLSI chip is becoming increasingly important as chip complexity increases. Congestion has a significant impact on performance, yield, and chip area. The present invention targets the optimization of congestion early in technology independent synthesis prior to physical design. Instead of attempting to optimize the logic structure as well as the spatial placement of a circuit, we pose a more modest goal limiting such optimization to the scope of logic synthesis. That is, we propose an aggressive optimization approach that is cognizant of circuit structure during technology independent synthesis and produces more predictable implementations which give better routability and yield.

1 . A method for optimizing a circuit design, the method comprising:
 receiving a graph of the circuit design, wherein circuit elements of the circuit design are nodes in the graph, and connections between the circuit elements are edges between the nodes;   determining a structural metric from a structural characteristic of the graph; and   performing a technology-independent logical synthesis to predict wiring congestion on the circuit design using the structural metric to generate an optimized circuit design with a reduced wiring congestion.   
   
   
       2 . The method of  claim 1 , wherein determining the structural metric comprises:
 determining a plurality of distances, wherein each distance is between each pair of the nodes;   determining a neighborhood population for each distance, wherein the neighborhood population corresponds to the number of the nodes that are within the distance; and   setting the structural metric to an average of the neighborhood populations.   
   
   
       3 . The method of  claim 1 , wherein determining the structural metric comprises:
 determining the minimum number of the edges that must be cut to separate every pair of the nodes in the graph; and   setting the structural metric to the sum of the minimum number of edges for each pair.   
   
   
       4 . The method of  claim 1 , wherein determining the structural metric comprises:
 determining for each pair of the nodes, a number of the nodes that are shared within a predefined distance; and   setting the structural metric to sum of the numbers.   
   
   
       5 . The method of  claim 1 , wherein performing a technology-independent logical synthesis on the circuit design using the structural metric to generate an optimized circuit design comprises using the structural metric during a technology mapping stage of the logic synthesis. 
   
   
       6 . The method of  claim 1 , wherein performing a technology-independent logical synthesis on the circuit design using the structural metric to generate an optimized circuit design comprises using the structural metric during a buffering stage of the logic synthesis. 
   
   
       7 . The method of  claim 1 , further comprising incrementally updating the structural metric when logic changes are made to the circuit design. 
   
   
       8 . A method for optimizing a circuit design, comprising:
 receiving a register transfer level (RTL) textual description of a circuit design model;   generating a graph from the RTL, wherein nodes of the graph correspond to circuit elements in the RTL, and edges of the graph correspond to connections between the circuit elements;   determining a structural metric based on a structural characteristic of the graph; and   optimizing the RTL using a count of the number of nodes in the graph, a count of the number of levels in the graph, and the structural metric.   
   
   
       9 . The method of  claim 8 , wherein the optimizing is performed independently of the type of technology of the circuit elements. 
   
   
       10 . The method of  claim 9 , further comprising performing technology dependent logical synthesis on a result of the optimization. 
   
   
       11 . The method of  claim 10 , further comprising performing physical synthesis on a result of the technology dependent synthesis. 
   
   
       12 . The method of  claim 11 , further comprising determining whether a result of performing the physical synthesis is routable. 
   
   
       13 . The method of  claim 8 , wherein determining the structural metric comprises:
 determining a plurality of distances, wherein each distance is between each pair of the nodes;   determining a neighborhood population for each distance, wherein the neighborhood population corresponds to the number of the nodes that are within the distance; and   setting the structural metric to an average of the neighborhood populations.   
   
   
       14 . The method of  claim 8 , wherein determining the structural metric comprises:
 determining the minimum number of the edges that must be cut to separate every pair of the nodes in the graph; and   setting the structural metric to the sum of the minimum number of edges for each pair.   
   
   
       15 . The method of  claim 8 , wherein determining the structural metric comprises:
 determining for each pair of the nodes, a number of the nodes that are shared within a predefined distance; and   setting the structural metric to sum of the numbers.   
   
   
       16 . A method for optimizing a circuit design, the method comprising:
 receiving a graph of the circuit design, where circuit elements of the circuit design are nodes in the graph, and connections between the circuit elements are edges between the nodes;   determining a structural metric for all the nodes in the graph from a structural characteristic of the graph;   selecting at least one of a timing, area, or structural change to the circuit design;   determining whether the structural metrics are still valid based on the change; and   implementing the change to the circuit design upon determining that the change provides a cost improvement to the structural metrics and the change to the circuit design is valid.   
   
   
       17 . The method of  claim 16 , wherein the circuit design does not include information about the type of technology of the circuit elements. 
   
   
       18 . The method of  claim 16 , wherein determining the structural metric comprises:
 determining a plurality of distances, wherein each distance is between each pair of the nodes;   determining a neighborhood population for each distance, wherein the neighborhood population corresponds to the number of the nodes that are within the distance; and   setting the structural metric to an average of the neighborhood populations.   
   
   
       19 . The method of  claim 16 , wherein determining the structural metric comprises:
 determining the minimum number of the edges that must be cut to separate every pair of the nodes in the graph; and   setting the structural metric to the sum of the minimum number of edges for each pair.   
   
   
       20 . The method of  claim 16 , wherein determining the structural metric comprises:
 determining for each pair of the nodes, a number of the nodes that are shared within a predefined distance; and   setting the structural metric to sum of the numbers.