Computer-aided design and analysis of circuits and semiconductor – Nanotechnology related integrated circuit design
Reexamination Certificate
1999-06-18
2002-04-02
Smith, Matthew (Department: 2825)
Computer-aided design and analysis of circuits and semiconductor
Nanotechnology related integrated circuit design
C716S030000
Reexamination Certificate
active
06367060
ABSTRACT:
FIELD OF THE INVENTION
The present invention pertains to the field of integrated circuit (IC) design. More particularly, this invention relates to the art of synthesizing clock tree solutions.
BACKGROUND OF THE INVENTION
Since the advent of the integrated circuit (IC), circuit components have become smaller and smaller. An IC may include millions of components packed into an incredibly small package. With each new generation of smaller integration, more functionality, and therefore more value, can be derived from ICs. Reliably manufacturing these highly integrated ICs, however, presents significant design challenges.
In particular, designing ICs that meet timing constraints can be particularly difficult. An IC may include tens of thousands of registers that need to be connected to one or more clock sources. For each clock “tick”, or clock transition, thousands of registers have to operate in concert. A complex network is needed to propagate the clock signal to each of the registers. If the difference in propagation delay through two different paths in the network is too large or too small, errors may occur that can cause the entire IC to fail.
Those skilled in the art will be familiar with numerous processes for synthesizing clock networks, or clock tree solutions. One of the most common approaches is a binary clock tree. A binary clock tree often begins by coupling registers into pairs. Then, pairs of register pairs are coupled together, pairs of pairs of register pairs are coupled together, and so on until the clock source, commonly referred to as the “root” or root node, is reached.
The result is a clock tree having a root and a series of branches reaching out to the registers. The registers are commonly referred to as “leaf nodes” on the tree. Between the root and the leaf nodes there may be several levels of intermediate nodes where paths branch.
Each register and each path adds a certain amount of load to the tree. The root usually cannot drive enough current into the tree to operate the cumulative load. In order to handle large trees, buffers are inserted into the tree at various intermediate nodes. Buffers receive a signal from an upstream driver, such as another buffer or the root node, and drive the signal to a number of down stream nodes.
A wide variety of approaches have been used to insert buffers in clock trees. For instance, the number of nodes coupled to a root may be counted, and one or more buffers inserted as needed. Then, each buffer can be treated like a root in a “sub-tree,” and nodes can be counted and buffers inserted to create further sub-trees in a hierarchy that reaches out to the leaf nodes. Various design constraints can be tested, and the process repeated with different types of buffers and tree structures until a suitable solution is found.
As ICs continue to become more complex, having tens of thousand of registers which may be clocked by several different source clocks, at several different clock frequencies, through gated clocks, inverted clocks, etc., the processing time and expense required to meet continually more stringent design constraints using known approaches is becoming increasingly prohibitive.
Therefore, an improved method and apparatus for synthesizing clock tree solutions is needed.
SUMMARY OF THE INVENTION
The present invention beneficially provides an improved method and apparatus for synthesizing clock tree solutions. At a particular level of a clock tree in a circuit description, balanced cluster sets of nodes are calculated based on a set of available buffer types. Each balanced cluster set is tested to see if it meets a design constraint. If the design constraint is not met for a particular balanced cluster set, the particular cluster set is removed from consideration in the clock tree solution. For the cluster sets that do meet the design constraint, a cost associated with each cluster set is calculated. A balanced cluster set that has the lowest cost is selected for the clock tree solution.
In one embodiment, the lowest cost balanced cluster set for one level in the clock tree forms the nodes for the next higher level in the clock tree, and the process is repeated at each level of the clock tree up to a root node. In another embodiment, the entire clock tree is tested to see if it meets a second design constraint. In another embodiment, the clock tree is tested for setup time and/or hold time violations, and register positions within the clock tree are changed to eliminate any violations. In another embodiment, the clock tree in the circuit description is modified with the lowest cost balanced cluster set for each level of the clock tree solution, wherein each cluster includes the buffer on which the cluster calculation was based.
REFERENCES:
patent: 5140526 (1992-08-01), McDermith et al.
patent: 5410491 (1995-04-01), Minami
patent: 5519351 (1996-05-01), Matsumoto
patent: 5553002 (1996-09-01), Dangelo et al.
patent: 5557779 (1996-09-01), Minami
patent: 5740067 (1998-04-01), Hathaway
patent: 5963728 (1999-10-01), Hathaway et al.
Minami et al., “Clock Tree Synthesis Based on RC Delay Balancing,” IEEE 1992 Custom Integrated Circuits Conference, pp. 28.3.1-28.3.4.*
Balboni et al., “Clock Skew Reduction in ASIC Logic Design: A Methodology for Clock Tree Management,” IEEE Trans. on CAD of ICs and Systems, vol. 17, No. 4, Apr. 1998, pp. 344-356.*
Cho et al., “A Buffer Distribution Algorithm for High-Performance Clock Net Optimizatin,” IEEE Trans. on VLSI Systems, vol. 3, No. 1, Mar. 1995, pp. 84-98.*
Krishnamurthy et al., “A New Partitioning Framework for Uniform Clock Distribution During High-Level Synthesis,” 1988 IEEE, pp. 381-384.*
Mehta et al., “Clustering and Load Balancing for Buffered Clock Tree Synthesis,” 1997 IEEE, pp. 217-223.
Chao Liang-Jih
Cheng C. K.
Columbia IP Law Group, PC
Garbowski Leigh Marie
LandOfFree
Method and apparatus for clock tree solution synthesis based... 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 and apparatus for clock tree solution synthesis based..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for clock tree solution synthesis based... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2896941