Cycle cutting with timing path analysis

Abstract

The timing cycles in a circuit design are identified and cut such that timing constraint paths in the circuit design are preserved. Timing cycles in the circuit design may be identified by traversing an adjacency list data structure, in which elements of the circuit design are represented as vertices interconnected by edges. Timing constraint paths may be distinguished from false timing paths using timing analysis, such as a greatest common path heuristic. Timing constraint paths may be marked as “constrained” to prevent these paths from being cut. With the cycles and timing constraint paths identified, cuts may be selected that cut the identified timing cycles while preserving the timing constraint paths. The cycle cuts allow the circuit design to be correctly processed within a conventional CAD tool design flow.

What is claimed is: 
     
         1 . A method for circuit design cycle cutting using timing path analysis, the method comprising:
 using a computing device to perform the steps of:
 accessing a circuit design comprising a plurality of elements interconnected by a plurality of edges, the circuit design further comprising timing constraints; 
 identifying cycles in the circuit design; 
 selecting a cycle cut to cut an identified cycle in the circuit design, the selection configured to preserve the timing constraints of the circuit design; and 
 generating a directive to cause a computer-aided drafting (CAD) tool to implement the selected cut. 
   
     
     
         2 . The method of  claim 1 , further comprising providing the directive to the CAD tool, the CAD tool to perform static timing analysis on the circuit design using the directive. 
     
     
         3 . The method of  claim 1 , wherein the directive is configured to cause the CAD tool to remove a timing arc passing through an element of the circuit design. 
     
     
         4 . The method of  claim 1 , wherein the directive is configured to cause the CAD tool to disable a timing path through an element of the circuit design. 
     
     
         5 . The method of  claim 1 , further comprising:
 identifying a must-cut timing path in the circuit design; and   generating a directive to cut the identified must-cut timing path.   
     
     
         6 . The method of  claim 5 , wherein the must-cut timing path corresponds to a global architectural cycle. 
     
     
         7 . The method of  claim 1 , wherein identifying cycles comprises traversing edges of the circuit design, wherein a cycle is identified when a traversal comprising a first element returns to the first element. 
     
     
         8 . The method of  claim 1 , wherein identifying cycles comprises:
 constructing a data structure comprising representations of the elements of the circuit design and representations of the edges interconnecting the elements; and   searching of the data structure to identify cycles in the circuit design.   
     
     
         9 . The method of  claim 1 , further comprising:
 identifying a plurality of timing constraint paths in the circuit design, each timing constraint path satisfying a timing constraint of the circuit design; and   marking input edges of elements in the timing constraint paths as constrained,   wherein selecting the cycle cut comprises preventing edges marked as constrained from being included in the cycle cut.   
     
     
         10 . The method of  claim 9 , wherein generating a timing constraint path satisfying a timing constraint of the circuit design comprises traversing the circuit design to form a timing path comprising elements coupling a first element of the timing constraint with a second element of the timing constraint. 
     
     
         11 . The method of  claim 9 , further comprising:
 identifying a set of timing paths satisfying the same timing constraint;   selecting one of the set of timing paths as a timing constraint path; and   marking input edges of elements on the selected timing constraint path as constrained.   
     
     
         12 . The method of  claim 11 , wherein the timing constraint path is selected using a greatest common path (GCP) heuristic. 
     
     
         13 . The method of  claim 12 , wherein selecting the timing constraint path comprises generating a plurality of timing constraints from a non-GCP timing path in the circuit design. 
     
     
         14 . The method of  claim 9 , wherein selecting the cycle cut comprises:
 identifying a set of edges interconnecting elements in the cycle, wherein cutting any of the edges cuts the cycle; and   selecting an edge in the identified set of edges for the cycle cut that is not marked as constrained.   
     
     
         15 . The method of  claim 9 , wherein selecting the cycle cut for a plurality of cycles comprises:
 identifying a set of edges for each of a plurality of cycles identified in the circuit design, each set of edges interconnecting the elements in a respective cycle, wherein cutting any of the edges cuts the respective cycle; and   selecting an edge in the set of edges that cuts a plurality of cycles and is not marked as constrained.   
     
     
         16 . The method of  claim 15 , further comprising selecting the edge to maximize a number of cycles cut by the edge. 
     
     
         17 . The method of  claim 1 , wherein the cycle cut is selected to prevent orphaning an element in the circuit design. 
     
     
         18 . The method of  claim 1 , further comprising calculating a quality metric based on a number of cycles remaining uncut in the circuit design and a number of orphaned elements in the circuit design. 
     
     
         19 . A machine-readable storage medium comprising instructions which when executed cause a machine to perform a method, the method comprising:
 identifying a plurality of cycles in the circuit design by traversing a data structure comprising elements of the circuit design interconnected by edges of the circuit design;   marking constrained edges within the circuit design;   selecting cuts to cut one or more of the identified cycles in the circuit design, each of the cuts selected to prevent cutting edges marked as constrained; and   providing the selected cuts to a computer-aided design (CAD) tool.   
     
     
         20 . The machine-readable storage medium of  claim 19 , wherein the selected cuts are selected to prevent orphaning an element of the circuit design. 
     
     
         21 . The machine-readable storage medium of  claim 19 , the method further comprising calculating a quality metric of the selected cuts based on a number of identified cycles remaining uncut and a number of orphaned elements resulting from the selected cuts. 
     
     
         22 . A system for cycle cutting using timing analysis, comprising:
 a circuit design comprising one or more cycles to be processed by a computer-aided design (CAD) tool, the CAD tool capable of correctly processing acyclic circuit designs;   a computing device comprising a processor; and   a cyclical timing module executed by the processor of the computing device, the cyclical timing module configured to identify a plurality of cycles in the circuit design by traversing a data structure comprising elements of the circuit design interconnected by edges of the circuit design, and to mark constrained edges of the circuit design, select cuts configured to cut one or more of the identified cycles, wherein each cut is configured to prevent cutting edges marked as constrained, and to provide the cuts to the CAD tool.