Method for clock skew cost calculation

• US 5,740,067 A
• Filed: 10/19/1995
• Issued: 04/14/1998
• Est. Priority Date: 10/19/1995
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Hathaway, David James
• Primary Examiner(s): Trans, Vincent N.
• Application Number:
  US08/547,686
• Time in Patent Office: 908 Days
• Field of Search: 364/488, 364/489, 364/490, 364/578
• US Class Current: 716/113
• CPC Class Codes: G06F 30/327 Logic synthesis; Behaviour synthesis, e.g. mapping logic, HDL to netlist, high-level language to RTL or netlist

Abstract

The present invention provides a method of computing the cost of a proposed clock tree change in the context of a clock skew optimization routine. According to the present invention, a recalculation of the clock skew cost due to a proposed change in the clock tree can be done without having to recompute the effect of the change to all of the sinks of that clock tree. The method stores the effects of past delay changes as unpropagated incremental changes until future changes make it necessary to propagate those changes. Thus, in this method only the parameters of the ancestors of the delayed node need to be recalculated to determine the cost of a proposed change in the clock tree. Not having to recalculate the rest of the tree greatly reduces the computational complexity and time required for the process, allowing the required iterations to be completed in a much shorter time period.

Claims

1. A method for determining a change in clock skew cost resulting from a delay change in a clock tree, said delay change affecting the delay to a delayed node, said clock tree comprising a root and a plurality of nodes, said plurality of nodes including a plurality of leaves, said plurality of nodes including ancestors and descendants in the clock tree, each of said plurality of nodes having an associated set of node values, the method comprising the steps of:

a) propagating any stored unpropagated incremental changes in the ancestors of said delayed node, to said delayed node;

b) updating said node values of said delayed node for effects of said proposed delay change;

c) propagating effects of said proposed delay change to said root of said clock tree; and

d) computing said change in clock skew cost based upon said propagated effects at said root of said clock tree.

2. The method of claim 1 wherein said proposed delay change is selected to move the clock skew of affected leaves toward a mean clock skew across said plurality of nodes in said clock tree.

3. The method of claim 1 wherein said proposed delay change is selected randomly.

4. The method of claim 1 wherein said clock skew cost C is defined as:

##EQU5## where n_root =number of leaves fed through said root, T_root =sum of all root-to-leaf path delays through said root and S_root =sum of squared root-to-leaf path delays through said root.

5. The method of claim 1 wherein said proposed delay change is accepted according to the change in clock skew cost, wherein said proposed delay change is accepted if it improves the clock skew cost, and wherein delay changes that degrade the cost clock skew cost are accepted according to a simulated annealing based probability.

6. The method of claim 1 wherein said proposed delay change is accepted if said change in clock skew cost improves the clock skew cost.

7. The method of claim 1 wherein said proposed delay change affects the delay along a plurality of branches, and wherein the step a) is completed for the deepest node affected by said proposed delay change, and wherein step b) and step c) are first completed for the deepest node affected by said proposed delay change, and wherein steps b) and c) are repeated up the tree until the shallowest node affected by the proposed delay change is reached.

8. A method for determining a change in a clock skew cost resulting from a proposed delay change in a clock network, said clock network arranged in a clock tree configuration, said clock tree configuration comprising a plurality of nodes, said plurality of nodes including a root and a plurality of leaves, said plurality of nodes including ancestors and descendants, said ancestors including a parent node, and said descendants including at least one child node, wherein nodes are siblings if they share the same parent, each of said plurality of nodes having an associated set of node values, wherein said proposed delay change affects the delay along a branch of said clock tree, said branch connecting a first node to a second node, with said first node being a ancestor to said second node, the method comprising the steps of:

a) distributing any stored unpropagated incremental changes in the ancestors of said second node, down to said second node;

b) updating said node values of said second node for effects of said proposed delay change;

c) propagating effects of said proposed delay change to said root of said clock tree; and

d) computing said change in said clock skew cost based upon said propagated effects at said root of said clock tree.

9. The method of claim 8 wherein said node values include:

number of leaves fed through said each node, sum of all root-to-leaf path delays through each said node, sum of squared root-to-leaf path delays through each said node, and unpropagated incremental changes of said each node.

10. The method of claim 8 wherein said proposed delay change is selected to move the clock skew of affected leaves toward a mean clock skew across said plurality of nodes in said clock tree.

11. The method of claim 8 wherein said proposed delay change is selected randomly.

12. The method of claim 8 wherein said clock skew cost C is defined as:

##EQU6## where n_root =number of leaves fed through said root, T_root =sum of all root-to-leaf path delays through said root and S_root =sum of squared root-to-leaf path delays through said root.

13. The method of claim 8 wherein said proposed delay change is accepted according to the change in said clock skew cost, wherein said proposed delay change is accepted if it improves the clock skew cost, and wherein delay changes that degrade the cost clock skew cost are accepted according to a simulated annealing based probability.

14. The method of claim 8 wherein said proposed delay change is accepted if said change in clock skew cost improves the clock skew cost.

15. The method of claim 8 wherein said proposed delay change affects the delay along a plurality of branches, and wherein the step a) is completed for the deepest node affected by said proposed delay change, and wherein step b) and step c) are first completed for the deepest node affected by said proposed delay change, and wherein steps b) and c) are repeated up the tree until the shallowest node affected by the proposed delay change is reached.

16. A method for optimizing clock skew of a clock network, said clock network arranged in a clock tree configuration, said clock tree comprising a plurality of nodes, said plurality of nodes including a root and a plurality of leaves, said plurality of nodes including ancestors and descendants, said ancestors including a parent node, and said descendants including at least one child node, wherein nodes are siblings if they share the same parent, each of said plurality of nodes having an associated set of node values, the method comprising the steps of:

a) storing said associated set of node values for each of said plurality of nodes, said associated set of node values including number of leaves fed through said each node, sum of all root-to-leaf path delays through said each node, sum of squared root-to-leaf path delays through said each node and unpropagated incremental changes of said each node;

b) selecting a delay change, said delay change effecting the delay along a branch of said clock tree, said branch connecting a first node to a second node, with said first node being parent to said second node;

c) updating said node values for each child of all ancestral nodes of said second node having any non-zero unpropagated incremental change, said updating commencing at nodes nearest said root of said clock tree, said updating to include the siblings of any child node that is updated;

e) updating said node values of said second node for said delay change, said updating resulting in a change in said node values of said second node;

f) storing said change in node values of said second node;

g) propagating effect of said delay change to all ancestors of said second node, starting at said first node and working towards said root, said step of propagating effect including use of said change in node values of said second node; and

h) computing said change in clock skew cost based upon said propagated effects at said root of said clock tree.

17. The method of claim 16 wherein said proposed delay change is selected to move the clock skew of affected leaves toward a mean clock skew across said plurality of nodes in said clock tree.

18. The method of claim 16 wherein said proposed delay change is selected randomly and wherein said delay changes that degrade the cost clock skew cost are accepted according to a simulated annealing based probability.

19. The method of claim 16 wherein said clock skew cost C is defined as:

##EQU7## where n_root =number of leaves fed through said root, T_root =sum of all root-to-leaf path delays through said root and S_root =sum of squared root-to-leaf path delays through said root.