Modifying timing graph to avoid given set of paths

Abstract

Integrated circuit chips (IC's) require proper placement of many cells (groups of circuit components) and complex routing of wires to connect the pins of the cells. Designing of the IC's require meeting real-world constraints such as minimization of the circuit area, minimization of wire length within the circuit, and minimization of the time the IC requires to perform its function, referred to as the IC delay. In order to design circuits to meet a given set of requirements, each signal path of the circuit must be analyzed. Because of the large number of the cells and the complex connections, the number of paths is very large and requires much computing power to analyze. Also, some of the paths are not important for the purposes of the operations of the chip and can be discounted during the analysis process. The present invention discloses a method and apparatus used to avoid analyzing non-important paths, referred to as false paths of a directed timing graph. To avoid the false paths, the timing graph representing the circuit is modified to exclude the false paths before the graph is analyzed. To modify the timing graph, duplicate nodes are constructed, duplicate edges are constructed, and some edges of the original graph are cut and replaced by mixed edges connecting non-duplicate nodes to duplicate nodes. Finally, mixed edges are created to connect duplicate nodes to non-duplicate nodes, integrating the duplicate graph with the original graph.