Computer-aided design and analysis of circuits and semiconductor – Nanotechnology related integrated circuit design
Reexamination Certificate
1998-06-12
2002-09-10
Siek, Vythe (Department: 2825)
Computer-aided design and analysis of circuits and semiconductor
Nanotechnology related integrated circuit design
C716S030000, C716S030000
Reexamination Certificate
active
06449756
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to integrated circuit design and layout.
2. State of the Art
The design of integrated circuits follows several steps. The first step is designing the logical gate-level circuit that implements the function to be realized by the circuit (referred to as logic design or logic synthesis, of which logic optimizations are a key part). The next step is placing the gates (or cells) in a physical layout, and the final step is routing the interconnection between the cells. These steps may be done in sequence or possibly together. Typically the resulting design must meet certain timing constraints. Thus the logic synthesis, placement and routing steps need to ensure that these constraints are met. The constraints are met by monitoring how different parts of the circuit are contributing to the delay of the circuit using a data structure referred to as a timing graph. In addition to providing information about how the entire circuit is positioned with respect to meeting the timing constraints, the timing graph also provides information of how individual parts of the circuit affect the final timing result. Thus, the timing graph serves an important diagnostic function by pointing out which parts of the circuit may need modification in order for the circuit to meet the timing constraints.
Any modifications being made to the circuit in either the logic, the placement or the routing can result in a change of the timing properties of not just the part of the circuit modified, but also other parts of the circuit that this timing information can ripple through. This ripple effect may be felt through the entire circuit. Thus, the timing graph of the circuit needs to be updated to accurately reflect the impact of these changes. For large circuits, the number of times these modifications are made tends to be very high (many times the number of gates in the circuit). Thus, this updating step may need to be done a very large number of times, with each update possibly needing to update the entire timing graph. Consequently this update process can end up being too slow to enable designs to be completed in reasonable time.
Timing graphs have been used in integrated circuit design for many years. A conventional timing graph has edges from input pins of cells to their output pins, representing the delays of the cell, and edges from output pins of cells to input pins of succeeding cells, representing interconnect delay. U.S. Pat. No. 5,581,473 (assigned to Sun Microsystems), incorporated herein by reference, describes how a timing graph can be constructed using such edges.
The paper by Singh et al. in ICCAD 88 clearly describes the use of a slack graph in storing slack information. The use of the slack graph in incremental timing analysis is described in U.S. Pat. No. 5,508,937 entitled Incremental Timing Analysis (assigned to IBM), incorporated herein by reference. In incremental timing analysis, only the parts of the timing graph that need to be updated are updated. The foregoing patent describes updating the timing graph in response to multiple modifications. However, it does not actively defer the updates for a group of modifications until some suitable point.
SUMMARY OF THE INVENTION
This invention encompasses several distinct improvements to the existing updating process for the timing graphs. The first aspect deals with improving the accuracy of the information being represented by the timing graph. An improvement in the accuracy results in better accuracy for the timing properties of the design, as well as better diagnostic capability for identifying the parts of the design resulting in timing problems. In accordance with one embodiment of the invention, a timing graph model represents the delay from each input pin of a cell A to each input pin of the cells that the output of A is connected to. This graph is required to consider the impact of input pin selection on interconnect delay. Traditional timing graph models, on the other hand, represent the delay from the output pin of cell A to each input pin of the cells that A is connected to. While the latter representation is considered to be more concise, it is less accurate than the method of the present invention. The second aspect deals with improving the efficiency of the update process in response to modifications made in the design. In accordance with another embodiment of the invention, the accumulated results of many modifications are stored in a data structure specifically designed for this purpose before initiating an update of the timing graph. Since the timing graph is not updated after each modification, it may not provide accurate diagnostic capability. Using the aforementioned data structure, an algorithm carefully monitors the impact of the modifications on the diagnostic capabilities and initiates the update of the timing graph only when the diagnostic capabilities are in danger of being compromised. Thus it permits trade-offs between accuracy and computational requirements. One possible lazy update scheme for timing graphs is to initiate the update after a fixed number of modifications, or after a time when the total delay change in different parts of the circuit crosses a threshold. A suitable balance between accuracy and computational requirements is achieved. Lazy update becomes especially powerful when coupled with update techniques that take advantage of parallel processing capabilities. Various techniques for parallel update are described.
REFERENCES:
patent: 5508937 (1996-04-01), Abato et al.
patent: 5581473 (1996-12-01), Rusu et al.
patent: 5778216 (1998-07-01), Venkatesh
patent: 5877965 (1999-03-01), Hieter et al.
patent: 5980093 (1999-11-01), Jones et al.
patent: 6000038 (1999-12-01), Scepanovic et al.
Swartz, W. and Sechen, C., “Timing Driven Placement for Large Standard Cell Circuits”, Proceedings of the 32nd ACM/IEEE Conference on Design Automation, 1995, pp. 211-215, Jan. 1995.*
Lee, J. and Tang, D.T., “An Algorithm for Incremental Timing Analysis”, Proceedings of the 32nd ACM/IEEE Conference on Design Automation, 1995, pp. 696-701, Jan. 1995.*
Wilson, Robert J., Introduction to Graph Theory, Third Edition, Longman Scientific & Technical, Hong Kong, 1986.*
Singh et al., “Timing Optimization of Combinational Logic”, IEEE Proceedings of the International Conference on computer Aided Design, pp. 282-285 (1988).
Hitchcock, “Timing Verification and the Timing Analysis Program”, IEEE, 19thDesign Automation Conference, 34.2:594-604 (1982).
Boyle Douglas B.
Chakraborty Abhijeet
Malik Sharad
McCaughrin Eric
Pileggi Lawrence
Monterey Design Systems
Siek Vythe
Vierra Magen Marcus Harmon & DeNiro LLP
LandOfFree
Method for accurate and efficient updates of timing... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method for accurate and efficient updates of timing..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method for accurate and efficient updates of timing... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2878696