Global routing determination method and storage medium

• US 6,532,583 B1
• Filed: 05/12/1999
• Issued: 03/11/2003
• Est. Priority Date: 06/16/1998
• Status: Expired due to Fees

• Current Assignee: Fujitsu Limited
• Original Assignee: Fujitsu Limited
• Inventors: Shibuya, Toshiyuki
• Primary Examiner(s): Siek, Vuthe
• Application Number:
  US09/310,205
• Time in Patent Office: 1,399 Days
• Field of Search: 716/13, 716/12, 716/14
• US Class Current: 716/114
• CPC Class Codes: G06F 30/394 Routing G06F30/396 takes precedence

Abstract

A global routing determination method successively divides a region which includes cells forming a circuit into a plurality of blocks, and hierarchically determines a global routing among the cells while arranging the cells in the blocks. The global routing determination method includes the steps of selecting a K-pattern which indicates a position of at least one terminal which is to be coupled by a wiring with respect to a predetermined number of blocks, from a registered K-pattern group, reading Q-patterns which indicate wiring patterns with respect to the selected K-pattern, from a registered Q-pattern group, and determining, as a global routing, a Q-pattern which has a wiring from a source terminal to a target terminal within the selected K-pattern with a signal delay time satisfying a predetermined condition, from among the read Q-patterns, where the predetermined condition places priority on a total wiring length than a density or disorder of wirings among the blocks in which the source terminal and the target terminal exist.

Claims

1. A global routing determination method which successively divides a region which includes cells forming a circuit into a plurality of blocks, and hierarchically determines a global routing among the cells while arranging the cells in the blocks, comprising the steps of:

(a) selecting a K-pattern which indicates a position of at least one terminal which is to be coupled by a wiring with respect to a predetermined number of blocks, from a registered K-pattern group;

(b) reading Q-patterns which indicate wiring patterns with respect to the selected K-pattern, from a registered Q-pattern group; and

(c) determining, as a global routing, a Q-pattern which has a wiring from a source terminal to a target terminal within the selected K-pattern with a signal delay time satisfying a predetermined condition, from among the read Q-patterns,

said predetermined condition placing priority on a total wiring length over a density or disorder of wirings among the blocks in which the source terminal and the target terminal exist.

2. The global routing determination method as claimed in claim 1, wherein said step (c) determines, as the global routing, a Q-pattern which minimizes COST(Q) described by a formula

  COST(Q)=COST_V1(Q)×

δ

(Q, V1)+COST_V2(Q)×

δ

(Q, V2)+COST_H1(Q)×

δ

(Q, H1)+COST_H2(Q)×

δ

(Q, H2)

where each read Q-pattern is made up of 2×

2 blocks, boundaries x between two mutually adjacent blocks of the read Q-pattern are respectively denoted by V1, V2, H1 and H2, a function δ

(Q, x) has a value 1 when a wiring passes through the boundary x and has a value 0 when a wiring does not pass through the boundary x, C1 and C2 are constants, C(x) denotes a number of wirings passing through the boundary x, W(x) denotes a number of wirings which can pass through the boundary, and relationships

3. A global routing determination method which successively divides a region which includes cells forming a circuit into a plurality of blocks, and hierarchically determines a global routing among the cells while arranging the cells in the blocks, comprising the steps of:

(a) selecting a K-pattern which indicates a position of at least one terminal which is to be coupled by a wiring with respect to a predetermined number of blocks, from a registered K-pattern group;

(b) reading Q-patterns which indicate wiring patterns with respect to the selected K-pattern, from a registered Q-pattern group; and

(c) determining, as a global routing, a Q-pattern which has a wiring from a source terminal to a target terminal within the selected K-pattern with a signal delay time satisfying a predetermined condition, from among the read Q-patterns,

said step (c) determining, as the global routing, a Q-pattern which minimizes a slack S described by formulas $S=\underset{\forall <br><br>\mathrm{targeti}}{\sum <br><br>}<br><br>0;<br><br>\mathrm{maxDelay}<br><br>\text{\hspace{1em}<br><br>}<br><br>\left(i\right)-\mathrm{delay}<br><br>\text{\hspace{1em}<br><br>}<br><br>\left(i\right)\geqq <br><br>0$ 

delay(i)−

maxDelay(i);

maxDelay(i)−

delay(i)<

0

where maxDelay (i) denotes a signal delay time caused by a wiring from a requested source terminal to a target terminal, and delay(i) denotes a signal delay time which is obtained as a result of actually forming the wiring from the source terminal to the target terminal.

4. The global routing determination method as claimed in claim 3, wherein the signal delay time delay(i) is an Elmore delay described by a formula $D$

 



(v)=rdCs0+∑

ev∈

path

 



(s0,v)

 



rev

 



(Cev/2+Cv)

where a tree T has a source s0, an edge from a node v towards the source s0 is denoted by ev, a resistance of the edge ev is denoted by r_ev, a capacitance of the edge ev is denoted by C_ev, a subtree of the node v is denoted by Tv, a capacitance of the subtree Tv is denoted by Cv, an ON-resistance of an output driver of the source s0 is denoted by rd, a sum total of wiring lengths is denoted by C_s0, and the Elmore delay D(v) indicates a delay from the source s0 to the target v.

5. The global routing determination method as claimed in claim 3, wherein, when the target terminal is connected to another target terminal which is included in a block different from a predetermined block which includes the target terminal, with respect to the Q-patterns satisfying S>

0, said step (c) branches a wiring from a block which includes the source terminal to a block other than the predetermined block which includes the target terminal, and if a signal delay time of the branched wiring is smaller than that of an original wiring and a relationship maxDelay(j)−

delay(j)≧

0 is satisfied, where maxDelay(j) denotes the signal delay time caused by the branched wiring and delay(j) denotes the signal delay time of the branched wiring which is actually formed from the target terminal to the other target terminal, said step (c) determines the Q-pattern which includes the branched wiring as the global routing.

6. The global routing determination method as claimed in claim 5, wherein, when the target terminal is connected to another target terminal which is included in a block different from a predetermined block which includes the target terminal, said step (c) removes a wiring from the target terminal to the other target terminal and forms another wiring which connects to the other target terminal via a path other than the that of the removed wiring, and if a signal delay time of the other wiring is smaller than that of an original wiring, and a relationship maxDelay(k)−

delay(k)≧

0 is satisfied, where maxDelay(k) denotes a signal delay time caused by the other wiring and delay(k) denotes a signal delay time of the other wiring which is actually formed from the target terminal to the other target terminal, and said step (c) determines the Q-pattern which includes the other wiring as the global routing.

7. The global routing determination method as claimed in claim 3, wherein, when the target terminal is connected to another target terminal which is included in a predetermined block which includes the target terminal, and no further target terminals connected to the target terminal exist in blocks other than the predetermined block, said step (c) branches a wiring from a block which includes the source terminal into the predetermined block, and if a signal delay time of the branched wiring is smaller than that of an original wiring, and a relationship maxDelay(j)−

delay(j)≧

0 is satisfied, where maxDelay(j) denotes a signal delay time caused by the branched wiring and delay(j) denotes a signal delay time of the branched wiring which is actually formed from the source terminal to the other target terminal, said step (c) determines the Q-pattern which includes the branched wiring as the global routing.

8. The global routing determination method as claimed in claim 7, wherein, when the target terminal is connected to another target terminal which is included in a predetermined block which includes the target terminal, and a further target terminal connected to the target terminal exists in a block other than the predetermined block, said step (c) removes a wiring from the target terminal to the other target terminal, and forms another wiring which connects to the other target terminal via a path different from that of the removed wiring, and if a signal delay time of the other wiring to the other target terminal is smaller than that of an original wiring, and a relationship maxDelay(k)−

delay(k)≧

0 is satisfied, where maxDelay(k) denotes a signal delay time caused by the other wiring and delay(k) denotes a signal delay time of the other wiring which is actually formed from the target terminal to the other target terminal, said step (c) determines the Q-pattern which includes the other wiring as the global routing.

9. The global routing determination method as claimed in claim 3, wherein, with respect to the Q-pattern which satisfies the relationship S≧

0, when the target terminal is connected to another target terminal which is included in a block other than a predetermined block which includes the target terminal, said step (c) inserts a buffer in a wiring from the target terminal to the other target terminal, and if a signal delay time of the wiring to the other target terminal and inserted with the buffer is smaller than that of an original wiring which does not include the buffer, and a relationship maxDelay(j)−

delay(j)≧

0 is satisfied, where maxDelay(j) denotes a signal delay time caused by the wiring from the target terminal to the other target terminal and inserted with the buffer and delay(j) denotes a signal delay time of the wiring which is actually formed from the target terminal to the other target terminal and is inserted with the buffer, said step (c) determines the Q-pattern which includes the wiring to the other target terminal and inserted with the buffer as the global routing.

10. The global routing determination method as claimed in claim 3, wherein, when the target terminal is connected to another target terminal which is included in a predetermined block which includes the target terminal, and no further target terminal connected to the target terminal exists in a block other than the predetermined block, said step (c) inserts a buffer in a wiring from the target terminal to the other target terminal, and if a signal delay time of the wiring to the other target terminal and inserted with the buffer is smaller than that of an original wiring, and a relationship maxDelay(j)−

delay(j)≧

0 is satisfied, where maxDelay(j) denotes a signal delay time caused by the wiring inserted with the buffer and delay(j) denotes a signal delay time of the wiring which is inserted with the buffer and is actually formed from the target terminal to the other target terminal, said step (c) determines the Q-pattern which includes the wiring inserted with the buffer as the global routing.

11. A computer-readable storage medium which stores a program for causing a computer to successively divide a region which includes cells forming a circuit into a plurality of blocks, and to hierarchically determine a global routing among the cells while arranging the cells in the blocks, comprising:

first means for causing the computer to select a K-pattern which indicates a position of at least one terminal which is to be coupled by a wiring with respect to a predetermined number of blocks, from a registered K-pattern group;

second means for causing the computer to read Q-patterns which indicate wiring patterns with respect to the selected K-pattern, from a registered Q-pattern group; and

third means for causing the computer to determine, as a global routing, a Q-pattern which has a wiring from a source terminal to a target terminal within the selected K-pattern with a signal delay time satisfying a predetermined condition, from among the read Q-patterns,

said predetermined condition placing priority on a total wiring length over a density or disorder of wirings among the blocks in which the source terminal and the target terminal exist.

12. The computer-readable storage medium as claimed in claim 11, wherein said third means causes the computer to determine, as the global routing, a Q-pattern which minimizes COST(Q) described by a formula

13. A computer-readable storage medium which stores a program for causing a computer to successively divide a region which includes cells forming a circuit into a plurality of blocks, and to hierarchically determine a global routing among the cells while arranging the cells in the blocks, comprising:

first means for causing the computer to select a K-pattern which indicates a position of at least one terminal which is to be coupled by a wiring with respect to a predetermined number of blocks, from a registered K-pattern group;

second means for causing the computer to read Q-patterns which indicate wiring patterns with respect to the selected K-pattern, from a registered Q-pattern group; and

third means for causing the computer to determine, as a global routing, a Q-pattern which has a wiring from a source terminal to a target terminal within the selected K-pattern with a signal delay time satisfying a predetermined condition, from among the read Q-patterns,

said third means determining, as the global routing, a Q-pattern which minimizes a slack S described by formulas $S=\underset{\forall <br><br>\mathrm{targeti}}{\sum <br><br>}<br><br>0;<br><br>\mathrm{maxDelay}<br><br>\text{\hspace{1em}<br><br>}<br><br>\left(i\right)-\mathrm{delay}<br><br>\text{\hspace{1em}<br><br>}<br><br>\left(i\right)\geqq <br><br>0$ 

delay(i)−

maxDelay(i);

maxDelay(i)−

delay(i)<

0

where maxDelay (i) denotes a signal delay time caused by a wiring from a requested source terminal to a target terminal, and delay(i) denotes a signal delay time which is obtained as a result of actually forming the wiring from the source terminal to the target terminal.

14. The computer-readable storage medium as claimed in claim 13, wherein the signal delay time delay(i) is an Elmore delay described by a formula $D$

 



(v)=rdCs0+∑

ev∈

path

 



(s0,v)

 



rev

 



(Cev/2+Cv)

where a tree T has a source s0, an edge from a node v towards the source s0 is denoted by ev, a resistance of the edge ev is denoted by r_ev, a capacitance of the edge ev is denoted by C_ev, a subtree of the node v is denoted by Tv, a capacitance of the subtree Tv is denoted by Cv, an ON-resistance of an output driver of the source s0 is denoted by rd, a sum total of wiring lengths is denoted by C_s0, and the Elmore delay D(v) indicates a delay from the source s0 to the target v.