Method for routing of nets in an electronic device

• US 6,505,331 B1
• Filed: 10/15/1996
• Issued: 01/07/2003
• Est. Priority Date: 10/15/1996
• Status: Expired due to Term

• Current Assignee: Freescale Semiconductor, Inc. (NXP Semiconductors NV)
• Original Assignee: Motorola, Inc. (Motorola Solutions, Inc.)
• Inventors: Bracha, Gabriel, Weisberger, Eytan, Algor, Ilan
• Primary Examiner(s): Smith, Matthew
• Assistant Examiner(s): DO, THUAN V
• Application Number:
  US08/730,046
• Time in Patent Office: 2,275 Days
• Field of Search: 364/488, 364/489, 364/490, 364/491, 370/254, 716/2, 716/11, 716/12, 716/13, 716/14
• US Class Current: 716/129
• CPC Class Codes: G06F 30/394 Routing G06F30/396 takes precedence

Abstract

In laying out electonic devices on a substrate the routing of nets is important in minimizing conductor area and improving performance. A method for routing of nets in an electonic device which has a plurality of clusters is disclosed which separates the intra cluster routing and the channel routing between the clusters. For the intra cluster routing a topological graph is proposed to be used for mapping a subgraph which is representative of the nodes in a net belonging to a cluster to be routed.

Claims

1. A method for routing nets in an electronic device having a plurality of clusters, said clusters being separated by a channel area between the clusters, and said clusters having a plurality of nodes, each of said nodes being assigned to one of said nets, said method comprising the steps of:

a) for each set of nodes belonging to the same net;

establishing a minimal Steiner tree between a sub set of said clusters which have at least one of said nodes of said set of nodes, said minimal Steiner tree logically interconnecting at least one of said nodes of said set of nodes of each of said clusters of said sub set of clusters;

b) for each of said Steiner trees found in step a);

determining logical nodes where said Steiner tree intersects a boundary of said channel area;

including said logical nodes in a graph representation of said net, so that first sub graphs covering said clusters and second sub graphs covering said channel area result; and

c) for each cluster;

routing each of said first sub graphs found in step b) independently from channel routing of said second sub graphs found in step b).

2. The method according to claim 1 further comprising the steps of

d) for each of said clusters: for each node of said cluster forming a second graph representation to model potential electrical connectivities to other nodes within said cluster or to channel boundaries irrespective of any assignment of nodes to specific nets;

e) routing each of said first sub graphs found in step b) of claim 1 in accordance with the electrical connectivities as modeled by said second graphs.

3. The method according to claim 2, whereby said second graph representation includes vertices to represent potential electrical conductors and edges to represent potential electrical connections between said electrical conductors, whereby an edge can have one of the following types:

i) a first type of edge which represents that an electrical connectivity between electrical conductors can be established;

ii) a second type of edge which establishes a mutual exclusion relation with respect to different nets; and

iii) a third type of edge which establishes a channel border relation for representation of said logical nodes.

4. A method for routing nets in an electronic device having a plurality of clusters, said clusters being separated by a channel area between the clusters, and said clusters having a plurality of nodes, each of said nodes being assigned to one of said nets, said method comprising the steps of:

a) for each set of nodes belonging to the same net;

establishing a minimal Steiner tree between a sub set of said clusters which have at least one of said nodes of said set of nodes, said minimal Steiner tree logically interconnecting at least one of said nodes of said set of nodes of each of said clusters of said sub set of clusters;

b) for each of said Steiner trees found in step a);

determining logical nodes where said Steiner tree intersects a boundary of said channel area;

including said logical nodes in a graph representation of said net, so that first sub graphs covering said clusters and second sub graphs covering said channel area result;

c) for each cluster;

routing each of said first sub graphs found in step b) independently from channel routing of said second sub graphs found in step b);

d) for each of said clusters;

for each node of said cluster forming a second graph representation to model potential electrical connectivities to other nodes within said cluster or to channel boundaries irrespective of any assignment of nodes to specific nets;

e) routing each of said first sub graphs found in step b in accordance with the electrical connectivities as modeled by said second graphs; and

for each of said clusters;

for each of said first sub graphs covering said cluster;

f) establishing a list of logical components comprising said nodes of said first sub graph, each of said nodes of said first sub graph being initially defined to be a separate logical component in said list;

g) repetitively selecting one of said logical components from said list until there is only one single logical component left in said list;

h) routing from the selected component to another logical component of the same list, if possible;

i) in case of finding a route in said step h);

removing said selected component and said other component from said list;

uniting said selected component and said other component to create a new logical component;

inserting said united component into said component list;

j) in case of not finding a route in said step h);

ripping up an obstructing route of another one of said first sub graphs which has been processed previously;

k) in case of ripping up an obstructing route in said step j);

finding an alternative route to replace said obstructing route.

5. The method according to claim 4 whereby said step k) is carried out by logically splitting said united component of said other first sub graph into at least two logical components by ripping up said obstructing route and carrying out said step g) and said step h) to find said alternative route.

6. The method according to claim 4 whereby the logical component of said list is the most constrained component.

7. An electronic device having a plurality of clusters, said clusters being separated by a channel area between the clusters, and said clusters having a plurality of nodes, each of said nodes being assigned to one of a plurality of nets, said nets being routed in accordance with a method comprising the steps of

a) for each set of nodes belonging to the same net:

establishing a minimal Steiner tree between a sub set of said clusters which have at least one of said nodes of said set of nodes, said minimal Steiner tree logically interconnecting at least one of said nodes of said set of nodes of each of said clusters of said sub set of clusters;

b) for each of said Steiner trees found in step a);

determining logical nodes where said Steiner tree intersects a boundary of said channel area;

including said logical nodes in a graph representation of said net, so that first sub graphs covering said clusters and second sub graphs covering said channel area result;

c) for each cluster;

routing each of said first sub graphs found in step b) independently from channel routing of said second sub graphs found in step b).

8. The electronic device according to claim 7, said method further comprising the steps of

d) for each of said clusters: for each node of said cluster forming a second graph representation to model potential electrical connectivities to said node within said cluster;

e) routing each of said first sub graphs found in step b) of claim 7 in accordance with the electrical connectivities as modeled by said second graphs.

9. The electronic device according to claim 8, said method further comprising the steps of

for each of said clusters:

for each of said first sub graphs covering said cluster;

f) establishing a list of logical components comprising said nodes of said first sub graph, each of said nodes of said first sub graph being initially defined to be a separate logical component in said list;

g) repetitively selecting one of said logical components from said list until there is only one single logical component left in said list;

h) routing from the selected component to another logical component of the same list, if possible;

i) in case of finding a route in said step h) removing said selected component and said other component from said list;

uniting said selected component and said other component to create a new logical component;

inserting said united component into said component list;

j) in case of not finding a route in said step h);

ripping up an obstructing route of another one of said first sub graphs which has been processed previously;

k) in case of ripping up an obstructing route in said step j);

finding an alternative route to replace said obstructing route.

10. The electronic device according to claim 9, said method being characterized in that said step k) of claim 9 is carried out by logically splitting said united component of said other first sub graph into at least two logical components by ripping up said obstructing route and in that said step g) and said step h) of claim 9 are tarried out to find said alternative route.

11. The electronic device according to claim 10, said method being characterized in that said one of said logical components selected in said step g) of claim 9 is the logical component of said list which is the most constrained component.

12. A general purpose digital computer for routing of nets in an electronic device, said computer being programmed to carry out method for routing of nets of an electronic device having a plurality of cluster, said clusters being separated by a channel area between the clusters, and said clusters having a plurality of nodes, each of said nodes being assigned to one of said nets, said method comprising the step of:

a) for each set of nodes belonging to the same net;

establishing a minimal Steiner tree between a sub set of said clusters which have at least one of said nodes of said set of nodes, said minimal Steiner tree logically interconnecting at least one of said nodes of said set of nodes of each of said clusters of said sub set of clusters;

said computer being characterized by the method steps of;

b) for each of said Steiner trees found in step a);

determining logical nodes where said Steiner tree intersects a boundary of said channel area;

including said logical nodes in a graph representation of said net, so that first sub graphs covering said clusters and second sub graphs covering said channel area result;

c) for each cluster;

routing each of said first sub graphs found in step b) independently from channel routing of said second sub graphs found in step b).

13. A method for routing electrical connections between nodes in electronic devices, said devices having pluralities of clusters separated by channel areas, pluralities of nodes forming nets to be electrically connected together, wherein at least one net has nodes in different clusters to be electrically connected across said channel areas and nodes to be electrically connected within a single cluster, the method comprising the steps of:

a) for each particular net, logically interconnecting some nodes of said net by a minimal Steiner tree which interconnects all the clusters having nodes of that particular net by at least a single node;

b) for each particular net of step a), determining logical nodes where said logical interconnections of said Steiner trees intersect a channel area boundary and providing first graphs to represent clusters with nodes belonging to said particular net and the corresponding interconnections, and second graphs to represent channel areas of the corresponding intersections; and

c) for each cluster, routing electrical connections within said clusters for said first graphs found in step b) independently from channel routing of electrical connections across channel areas for said second graph found in step b).