Method to partition clock sinks into nets

Claim 3

The method of claim 1 wherein the step of making an initial assignment further comprises the steps of: assigning a first sink to a first clock net; assigning to said first clock net a subsequent sink which is closest to the sinks already assigned to said first clock net and repeating until the total number of sinks exceeds an upper limit; thereafter, removing the last assigned sink from said first clock net, starting a second clock net, and assigning said last assigned sink to said second clock net; and continuing to assign subsequent sinks which are closest to the set of sinks already assigned to a clock net, starting new clock nets as the total number of sinks in a net exceeds said upper limit, until said each sink has been assigned.

Claim 4

The method of claim 1 wherein the step of making an initial assignment further comprises the steps of: constructing a geometric tree structure having subtrees and tree nodes, said structure containing each sink, and marking each tree node of said geometric tree structure with the estimated load of all sinks in the subtrees rooted at said tree node; inserting subtree nodes rooted at the root of said geometric tree structure into a heap data structure sorted by said estimated loads; removing the highest estimated load subtree node from said heap data structure, dividing said subtree node into further subtree nodes rooted at said highest estimated load subtree node, and inserting said divided subtree nodes in said sorted heap data structure; repeating said removing, dividing, and inserting of the previous step until a desired number of subtree nodes are inserted in said heap; and designating each of said desired number of subtree nodes in said heap as a clock net with the sinks in each of said desired number of subtree nodes taken as said initial assignment of sinks to clock nets.

Claim 5

The method of claim 3 wherein said geometric tree structure is constructed as a k-D tree.

Claim 6

The method of claim 3 wherein said geometric tree structure is constructed as a quad-tree.

Claim 7

The method of claim 1 further comprising selecting two of said clock nets having the shortest distance between said two clock nets.

Claim 8

The method of claim 1 wherein the number of said remaining sinks is less than a pre-specified number.

Claim 9

The method of claim 7 further comprising selecting two of said clock nets having the shortest distance between said two clock nets.

Claim 10

The method of claim 1, further comprising the steps of: after said keeping said combination step, determining a required number of clock nets for said integrated circuit chip to meet a load-per-clock-net target; thereafter, either adding additional clock nets and re-assigning sinks from said two or more clock nets to said additional clock nets until said required number of clock nets is reached or a first stopping criteria is met, or deleting clock nets and re-assigning sinks from said deleted clock nets to remaining clock nets until said required number of clock nets is reached or a second stopping criteria is met; thereafter, dividing said integrated circuit chip into regions of two or more clock nets each so that each clock net lies within a region; determining a required number of clock nets for each said region to meet said load-per-clock-net target; and for each said region, either adding additional clock nets and re-assigning sinks from said two or more clock nets within said each region to said additional clock nets added to said each region until said required number of clock nets for said each region is reached or said first stopping criteria is met, or deleting clock nets from said each region and re-assigning sinks from said deleted clock nets to remaining clock nets in said each region until said required number of clock nets for said each region is reached or said second stopping criteria is met.

Claim 11

The method of claim 9 wherein said required number of clock nets for said integrated circuit chip is determined from the formula: Nr=Ct/Cr where Nr is said required number of clock nets, Ct is a sum of all loads of all clock nets on said integrated circuit chip, and Cr is said load-per-clock-net target.

Claim 12

The method of claim 9 wherein said integrated circuit chip is divided into first and second regions and said required number of clock nets for each of said first and second regions is determined from the formulas: Nr1=Nc1+(Ct1*(Nc2+Nr-Nc)-Ct2*Nc1)/(Ct1+Ct2) and Nr2=Nr-Nr1 where Nr1 and Nr2 are said required number of clock nets for said first and second regions respectively, Nc1 and Nc2 are the number of clock nets in said first and second regions respectively after dividing said integrated circuit chip into regions, Ct1 and Ct2 are the total loads of all clock nets in said first and second regions respectively, Nr is said required number of clock nets for said integrate circuit chip, and Nc is the total number of clock nets on said integrated circuit chip immediately prior to said step of dividing said chip into regions.

Claim 13

The method of claim 9, further comprising the steps of: sub-dividing a region into sub-regions of two or more clock nets each, so that each clock net lies within one of said sub-regions; determining a required number of clock nets for each said sub-region to meet said load-per-clock-net target; and for each said sub-region, either adding additional clock nets and re-assigning sinks from said two or more clock nets within said each sub-region to said additional clock nets added to said each sub-region until said required number of clock nets for said each sub-region is reached or said first stopping criteria is met, or deleting clock nets from said each sub-region and re-assigning sinks from said deleted clock nets to remaining clock nets in said each sub-region until said required number of clock nets for said each subregion is reached or said second stopping criteria is met.

Claim 14

A computer program product containing executable code for execution by a computer for designing the clocking circuitry of an integrated circuit chip having a plurality of separate clock nets and a plurality of sinks, said computer program product comprising: means for making an initial assignment of each sink to one of two or more separate clock nets; means for selecting two of said clock nets including all sinks assigned to either of said two clock nets; means for removing said all assigned sinks from said two selected clock nets, and re-assigning each of less than said all sinks, to one or the other of said two selected clock nets; means for thereafter forming all possible combinations of re-assigning each of the remaining sinks of said all sinks, to one or the other of said two selected clock nets; means for computing the value of a penalty function for each said combination of assignment; and means for keeping that said combination of assignment having the best computed value of said penalty function.

Claim 15

A computer program product containing executable code for execution by a computer for designing the clocking circuitry of an integrated circuit chip having a plurality of separate clock nets and a plurality of sinks, said computer program product comprising: means for making an initial assignment of each sink to one of two or more separate clock nets; means for selecting two of said clock nets including all sinks assigned to either of said two clock nets; means for removing said all assigned sinks from said two selected clock nets, and re-assigning each of less than said all sinks, to one or the other of said two selected clock nets; means for thereafter forming all possible combinations of re-assigning each of the remaining sinks of said all sinks, to one or the other of said two selected clock nets; means for computing the value of a penalty function for each said combination of assignment; and means for keeping that said combination of assignment having the best computed value of said penalty function.

Claim 16

The computer program product as set forth in claim 13 wherein said means for making an initial assignment further comprises: means for assigning a first sink to a first clock net; means for assigning to said first clock net a subsequent sink which is closest to the sinks already assigned to said first clock net and repeating until the total number of sinks exceeds an upper limit; means for removing the last assigned sink from said first clock net, and for starting a second clock net, and for assigning said last assigned sink to said second clock net; and means for continuing to assign subsequent sinks which are closest to the set of sinks already assigned to a clock net, and for starting new clock nets as the total number of sinks in a net exceeds said upper limit, until said each sink has been assigned.

Claim 17

The computer program product as set forth in claim 13 wherein said means for making an initial assignment further comprises: means for constructing a geometric tree structure having subtrees and tree nodes, said structure containing each sink, and for marking each tree node of said geometric tree structure with the estimated load of all sinks in the subtrees rooted at said tree node; means for inserting subtree nodes rooted at the root of said geometric tree structure into a heap data structure sorted by said estimated loads; means for removing the highest estimated load subtree node from said heap data structure, for dividing said subtree node into further subtree nodes rooted at said highest estimated load subtree node, and for inserting said divided subtree nodes in said sorted heap data structure; means for repeating said removing, dividing, and inserting of the previous step until a desired number of subtree nodes are inserted in said heap; and means for designating each of said desired number of subtree nodes in said heap as a clock net with the sinks in each of said desired number of subtree nodes taken as said initial assignment of sinks to clock nets.

Claim 18

A computer system for designing the clocking circuitry of an integrated circuit chip having a plurality of separate clock nets and a plurality of sinks, comprising: means for making an initial assignment of each sink to one of two or more separate clock nets; means for selecting two of said clock nets including all sinks assigned to either of said two clock nets; means for removing said all assigned sinks from said two selected clock nets, and re-assigning each of less than said all sinks, to one or the other of said two selected clock nets; means for thereafter forming all possible combinations of re-assigning each of the remaining sinks of said all sinks, to one or the other of said two selected clock nets; means for computing the value of a penalty function for each said combination of assignment; and means for keeping that said combination of assignment having the best computed value of said penalty function.

Claim 19

A computer system for designing the clocking circuitry of an integrated circuit chip having a plurality of separate clock nets and a plurality of sinks, comprising: means for making an initial assignment of each sink to one of two or more separate clock nets; means for selecting two of said clock nets including all sinks assigned to either of said two clock nets; means for removing said all assigned sinks from said two selected clock nets, and re-assigning each of less than said all sinks, to one or the other of said two selected clock nets; means for thereafter forming all possible combinations of re-assigning each of the remaining sinks of said all sinks, to one or the other of said two selected clock nets; means for computing the value of a penalty function for each said combination of assignment; and means for keeping that said combination of assignment having the best computed value of said penalty function.

Claim 20

The computer system as set forth in claim 16 wherein said means for making an initial assignment further comprises: means for assigning a first sink to a first clock net; means for assigning to said first clock net a subsequent sink which is closest to the sinks already assigned to said first clock net and repeating until the total number of sinks exceeds an upper limit; means for removing the last assigned sink from said first clock net, and for starting a second clock net, and for assigning said last assigned sink to said second clock net; and means for continuing to assign subsequent sinks which are closest to the set of sinks already assigned to a clock net, and for starting new clock nets and the total number of sinks in a net exceeds said upper limit, until said each sink has been assigned.

Claim 21

The computer system as set forth in claim 16 wherein said means for making an initial assignment further comprises: means for constructing a geometric tree structure having subtrees and tree nodes, said structure containing each sink, and for marking each tree node of said geometric tree structure with the estimated load of all sinks in the subtrees rooted at said tree node; means for inserting subtree nodes rooted at the root of said geometric tree structure into a heap data structure sorted by said estimated loads; means for removing the highest estimated load subtree node from said heap data structure, for dividing said subtree node into further subtree nodes rooted at said highest estimated load subtree node, and for inserting said divided subtree nodes in said sorted heap data structure; means for repeating said removing, dividing, and inserting of the previous step until a desired number of subtree nodes are inserted in said heap; and means for designating each of said desired number of subtree nodes in said heap as a clock net with the sinks in each of said desired number of subtree nodes taken as said initial assignment of sinks to clock nets.