Method and apparatus for determining wire routing
First Claim
1. A method of determining the edges for routing of wires for a net having pins, said method comprising the steps of:
- a. defining a grid;
b. defining each pin of the net as a set of connected pins (c-p-set);
c. identifying a pair of c-p-sets being closer to each other than any other pair of c-p-sets of the net;
d. connecting said pair of c-p-sets so as to form a single c-p-set; and
e. repeating steps c to d until one c-p-set remains.
10 Assignments
0 Petitions
Accused Products
Abstract
Integrated circuit chips (IC'"'"'s) require proper placement of many cells (groups of circuit components) and complex routing of wires to connect the pins of the cells. Because of the large number of the cells and the complex connections required, it is essential that wire routine be done correctly to avoid any congestion of wires. Congestion of wires can be determined by actually routing of the wires to connect the cells; however, the routing process is computationally expensive. For determination of congestion, the only required information are the location of the connections, or edges, to connect the pins of the IC. The present invention discloses a method to quickly provide a good estimate of the location of the edges, or connections for an IC. The present invention provides for a method to determine all the edges and superedges (bounding boxes, or areas where an edge will take space) of an IC without requiring to determine the actual routing of the wires of an IC.
24 Citations
18 Claims
-
1. A method of determining the edges for routing of wires for a net having pins, said method comprising the steps of:
-
a. defining a grid;
b. defining each pin of the net as a set of connected pins (c-p-set);
c. identifying a pair of c-p-sets being closer to each other than any other pair of c-p-sets of the net;
d. connecting said pair of c-p-sets so as to form a single c-p-set; and
e. repeating steps c to d until one c-p-set remains. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13)
determining distance between all pairs of c-p-sets of the net; and
selecting a pair of c-p-sets having smallest distance between them.
-
-
5. A method according to claim 4 wherein said distance between two c-p-sets is the smaller distance between a pin, a Steiner pin, or a Steiner pin candidate of one of said pair c-p-set to a pin, Steiner pin, or a Steiner pin candidate of the other of said pair of c-p-set.
-
6. A method according to claim 4 wherein said distance is rectilinear distance.
-
7. A method according to claim 1 wherein said step of connecting said pair of c-p-sets comprises the steps of:
-
defining a superedge for each of said pair of c-p-sets;
defining Steiner pins, if necessary, for each of said pair of c-p-sets;
connecting a first pin, a member of the first c-p-set of said pair, to a second pin, a member of the second c-p-set of said pair; and
defining a single c-p-set comprising pins of both said pairs of c-p-sets including Steiner pins.
-
-
8. A method according to claim 1 farther comprising a step of maintaining an edgelist.
-
9. A method according to claim 8 wherein said edgelist comprises a sets of edges.
-
10. A method according to claim 9 wherein an edge, a member of a set of edges, is defined by a pair of end pins wherein an end pin may be a pin or a Steiner pin.
-
11. A method according to claim 1 further comprising the steps of:
-
grouping the pins of the net into groups of a predetermined number of pins prior to defining the grid;
applying the steps a through e for each group; and
applying the steps a through e for the net using the group as the c-p-set.
-
-
12. A method according to claim 11 her comprising the step of applying the steps of claim 11 iteratively for multiple levels of groups.
-
13. A method according to claim 11 wherein said predetermined number of pins is 15.
-
14. An integrated circuit chip (IC) having pins optimally routed, said optimal routing method comprising the steps of:
-
a. defining a grid;
b. defining each pin of the net as a set of connected pins (c-p-set);
c. identifying a pair of c-p-sets being closer to each other than any other pair of c-p-sets of the net;
d. connecting said pair of c-p-sets so as to form a single c-p-set; and
e. repeating steps c to d until one c-p-set remains.
-
-
15. An apparatus for determining the edges for routing a set of pins, said apparatus comprising:
-
a processor;
a memory connected to said processor;
said memory having instructions for said processor to a. define a grid for the pins;
b. define each pin as a set of connected pins (c-p-set);
c. identify a pair of c-p-sets being closer to each other than any other pair of c-p-sets of the set of pins;
d. connect said pair of c-p-sets so as to form a single c-p-set; and
e. repeat steps c to d until one c-p-set remains. - View Dependent Claims (16)
-
-
17. A machine-readable storage medium containing instructions for a processor, said instructions comprising the steps for the processor to:
-
a. read a net;
b. define a grid for the pins of said net;
c. define each pin as a set of connected pins (c-p-set);
d. identify a pair of c-p-sets being closer to each other than any other pair of c-p-sets of the set of pins;
e. connect said pair of c-p-sets so as to form a single c-p-set; and
f. repeat steps c to e until one c-p-set remains. - View Dependent Claims (18)
-
Specification