Computer-aided design and analysis of circuits and semiconductor – Nanotechnology related integrated circuit design
Reexamination Certificate
1999-12-09
2002-02-26
Smith, Matthew (Department: 2825)
Computer-aided design and analysis of circuits and semiconductor
Nanotechnology related integrated circuit design
C716S030000, C716S030000, C716S030000, C716S030000
Reexamination Certificate
active
06351840
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates in general to methods for designing integrated circuits (ICs) and in particular to a method for assigning clocked circuit devices of an IC into clusters to be clocked by a balanced clock tree.
2. Description of Related Art
A digital IC typically employs many flip-flops, latches and other circuit devices (“syncs”) that are periodically clocked by edges of a clock signal distributed to all such syncs. Since an IC circuit typically has a very large number (thousands or millions) of syncs, a single clock signal driver normally cannot directly supply a clock signal to all such syncs. Instead an IC typically includes a “clock tree” consisting of a set of buffers arranged in a tree-like network as illustrated in
FIG. 1
that fans out a clock signal (CLOCK) so that no one buffer has to drive more than a relatively few syncs.
To ensure proper synchronization between the various parts of the circuit, each clock signal edge should reach all synchronization points at substantially the same time. Thus the time required for a clock signal edge to travel from its source to any sync should be substantially the same for all paths it follows through the clock tree. The time required for a clock signal edge to work its way through the tree from its source to a sync depends on many factors including the lengths of the conductors in the path, the number of buffers the edge must pass through, the switching delay of each buffer, the amount of attenuation of the clock signal incurs between buffer stages, and the load each buffer must drive. Accordingly designers try to “balance” the clock tree by ensuring that all clock signal paths between any two tree levels are of substantially similar length and impedance, by ensuring that all buffers at any level of the tree drive the same number of buffers or syncs at the next level of the tree, and by ensuring that all buffers on any given level have similar characteristics.
To balance the load on buffers forming a clock tree, designers group syncs into a set of “clusters” with each cluster including a similar number of syncs. The clock tree is then designed so that all syncs of a given cluster are clocked by the output of the same clock tree buffer, but wherein each cluster is clocked by the output of a separate clock tree buffer. To minimize variation in clock signal path lengths from a clock tree buffer to the syncs of a cluster that it clocks, designers would like to group syncs into clusters in a way that minimizes the separation between syncs within each cluster. When an IC includes thousands of syncs it is not practical for a designer to manually determine how to organize the syncs into clusters; computer-aided design (CAD) software typically does this automatically.
One widely employed algorithm for organizing clock tree called the “K-center” algorithm organizes a set of K×N syncs into a set of K clusters of N syncs each. The K-center algorithm randomly chooses a first sync to be the “center” of a first cluster. A second sync, the sync most distant from the first sync, is chosen to be the center of a second cluster. A third sync, the sync most remote from the first and second syncs, is then assigned as the center of a third cluster. When the process is repeated until a separate sync is assigned as the center of each of K clusters, the K cluster centers are widely distributed over the surface of the IC. Each of the remaining K(N−1) syncs are then preliminarily assigned to the cluster of the nearest center. Since syncs are often unevenly distributed on an IC, some of the clusters will typically contain more than N syncs while other clusters will contain fewer than N syncs. To balance the number of syncs per cluster, syncs most distant from the center of each cluster containing too many syncs are successively reassigned to nearest clusters containing too few syncs.
In this way the syncs are organized into a balanced set of K clusters with each cluster including N syncs. However the syncs the K-center method assigns to many clusters will often not be as tightly grouped as possible. An increase in distances between syncs of a cluster leads to increased variation in clock signal paths to those syncs and therefore reduced accuracy in synchronizing logic operations. When we reduce the synchronization accuracy we limit the frequency at which the IC can be operated.
What is needed is an improved method for organizing syncs into clusters that provides tightly packed clusters to minimize distances between syncs within each cluster.
SUMMARY OF THE INVENTION
The present invention is an improvement to the prior art K-center method for assigning a set of K×N clocked circuit devices (“syncs”) on an IC to a set of K clusters with N syncs per cluster so that they may be clocked by a balanced clock tree.
In accordance with the invention, after employing the conventional K-center method to assign the K×N syncs to K clusters with N syncs per cluster, positions of syncs within each cluster are investigated to determine the boundaries of a rectangular area of the IC containing all the syncs of the cluster. With the boundaries of all clusters determined, the IC areas occupied by all clusters are then compared to determine whether any of these areas overlap. When any group of M>1 clusters is found to overlap, the cluster assignments for the M×N syncs within that group of M clusters are abandoned and the K-center method is used to reassign that set of M×N syncs to a new set of M clusters. The new set of M clusters is likely to have less overlapping. When any subset of the new set of M clusters is found to have overlapping areas, the K-center method is applied to the subset. Similarly the K-center method is applied iteratively until all cluster overlapping is eliminated or until application of the K-center method fails to effect further change in cluster assignments. This iterative, multipass application of the K-center method will typically produce more tightly grouped clusters than the prior art single pass application of the K-center algorithm.
Accordingly it is an object of the invention to provide a method for assigning syncs within an IC to a balanced set of tightly packed clusters.
The concluding portion of this specification particularly points out and distinctly claims the subject matter of the present invention. However those skilled in the art will best understand both the organization and method of operation of the invention, together with further advantages and objects thereof, by reading the remaining portions of the specification in view of the accompanying drawing(s) wherein like reference characters refer to like elements.
REFERENCES:
patent: 5410491 (1995-04-01), Minami
patent: 5557779 (1996-09-01), Minami
patent: 5860108 (1999-01-01), Horikawa
patent: 5866924 (1999-02-01), Zhu
patent: 5983224 (1999-11-01), Singh et al.
patent: 6006025 (1999-12-01), Cook et al.
patent: 6286128 (2001-09-01), Pileggi et al.
patent: 2001/0010090 (2001-07-01), Boyle et al.
patent: 2001/0011776 (2001-08-01), Igarashi et al.
A.D. Mehta et al., Clustering and Load Balancing for Buffered Tree Synthesis, 1997 IEEE International Conference on Computer Design: VLSI in Computers and Processors, Oct. 12, 1997, pp. 217-223.
Bedell Daniel J.
Silicon Perspective Corporation
Smith-Hill and Bedell
Thompson A. M.
LandOfFree
Method for balancing a clock tree 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 balancing a clock tree, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method for balancing a clock tree will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2985520