Global wiring by removal of redundant paths

• US 4,831,725 A
• Filed: 06/10/1988
• Issued: 05/23/1989
• Est. Priority Date: 06/10/1988
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Lewitan, Hirsh, Hickson, Jerome B. Jr., Dunham, Bradford
• Primary Examiner(s): Eley, Timothy V.
• Application Number:
  US07/205,138
• Time in Patent Office: 347 Days
• Field of Search: 29/825, 29/829, 29/846, 29/847, 29/850, 29/407, 364/488, 364/489, 364/490, 364/491, 437/8
• US Class Current: 29/847
• CPC Class Codes: G06F 30/394 Routing G06F30/396 takes precedence
• CPC Class Codes: Y10T 29/49156 with selective destruction of conductive paths
• CPC Class Codes: Y10T 29/49162 by using wire as conductive path
• CPC Class Codes: Y10T 29/49764 with testing or indicating

Abstract

A method for interconnecting nodes in each of a number of nets. This invention involves generating initial zones for all nets and determining cumulative demand for path spaces needed by these initial zones. The demand is then compared with the supply, and scores are determined for the paths of the initial zones. Redundant paths with the worst scores are then gradually deleted until there are no redundant paths. If however, demand for path spaces still exceeds supply, expanded zones are generated in areas where demand exceeds supply and redundant paths are gradually deleted until there are no redundant paths. The paths remaining after deletion from the expanded zones are then used to interconnect the nodes of the nets. The nodes are then interconnected using the remaining paths.

Claims

1. A method for interconnecting nodes in each of a member of nets, comprising the steps of:

(a) generating an initial zone for each net of said nets to be formed, said initial zone, for each net, being a corresponding first subset of a set of all paths which could be used for interconnecting all nodes of said each net, said corresponding first subset also being a corresponding second subset of a set of all segments which could be used for interconnecting said all nodes of said each net with each segment being a part of at least one minimum path of said corresponding first subset;

(b) determining cumulative demand for path spaces created by all initial zones generated in step (a);

(c) selecting a net of said nets;

(d) selecting a number of redundant paths of an initial zone for said net selected step (c);

(e) comparing said demand found in step (b) with the supply of available path spaces in an area used by said number of redundant paths selected in step (d);

(f) determining a score for each of said redundant paths, said score being a function of at least said comparison of step (e);

(g) deleting a redundant path from said initial zone for said net selected in step (c), said redundant path being one which has a worst score of any of said paths selected in step (d), no segment of a redundant path of said initial zone for said selected net being deleted if said segment is part of all minimum paths of said initial zone for said selected net;

(h) repeat steps (c) through (g) selecting nets and paths and deleting paths until all redundant paths have been deleted from said each initial zone for all of said nets, said cumulative demand for path space being recalculated for each repetition of this step without including paths which were deleted in prior repetitions of step (g); and

2. A method as recited in claim 1, wherein an initial zone is generated with the number of redundant paths in one direction being greater than the number of redundant paths in another direction.

3. A method as recited in claim 1, wherein an initial zone has only minimum length paths.

4. A method for interconnecting nodes in each of a number of nets, comprising the steps of:

(a) generating an initial zone for each net of said nets to be formed, said initial zone, for each net, being a corresponding first subset of a set of all paths which could be used for interconnecting all nodes of said each net, said corresponding first subset also being a corresponding second subset of a set of all segments which could be used for interconnecting said all nodes of said each net with each segment being a part of at least one minimum path of said corresponding first subset

(b) determining cumulative demand for path spaces created by all initial zones generated in step (a);

(c) comparing said cumulative demand found in step (b) with the supply of available path spaces;

(d) determining a score for each path of paths of said initial zones, said score being a function of at least the comparison of step (c);

(e) selecting a net of said nets;

(f) deleting a redundant path of said paths from an initial zone of said initial zones for a net selected in step (e), said redundant path being one which has a worst said score of any of said paths in said initial zone, no segment of a redundant path of said initial zone for said selected net being deleted if said segment is part of all minimum paths of said initial zone for said selected net;

(g) repeating steps (c) through (f) until each of the initial zones generated in step (a) has no redundant paths, said cumulative demand for path spaces being recalculated for each repetition of this step without including paths which were deleted in prior repetitions of step (f); and

(h) interconnecting nodes of each net using available path spaces and paths, for each net, which paths remain undeleted after the completion of step (g).

5. A method for interconnecting nodes in each of a number of nets, comprising the steps of:

(a) generating an initial zone for each net of said nets to be formed, said initial zone, for each net, being a corresponding first sunset of a set of all paths which could be used for interconnecting all nodes of said each net, said corresponding first subset also being a corresponding second subset of a set of all segments which could be used for interconnecting said all nodes of said each net with each segment being a part of at least one minimum path of said corresponding first subset;

(b) determining cumulative demand for path spaces created by all initial zones generated in step (a);

(c) selecting a net of said nets;

(d) selecting a number of redundant paths of an initial zone for said net selected in step (c);

(e) comparing said demand found in step (b) with the supply of available path spaces in a first area;

(f) determining a score for each of said redundant paths, said score being a function of at least said comparison of step (e);

(g) deleting a redundant path from said initial zone for said net selected in step (c), said redundant path being one which has a worst score of any of said paths selected in step (d), no segment of a redundant path of said initial zone for said selected net being deleted if said segment is part of all minimum paths of said initial zone for said selected net;

(h) repeat steps (c) through (g) selecting nets and paths and deleting paths until all redundant paths have been deleted from said each initial zone for all of said nets, said cumulative demand for path space being recalculated for each repetition of this step without including paths which were deleted in prior repetitions of step (g);

after having completed steps (a) through (h) and if demand for path spaces still exceeds the supply of available path spaces, the following additional steps are to be taken;

(i) selecting a second area where demand for path spaces still exceeds supply;

(j) generating an expanded zone on said second area for each sub-net, said expanded zone for each sub-net being any set of paths used to interconnect nodes of each sub-net, said expanded zone for each sub-net containing redundant paths, each said sub-net being that part of a net within said second area and also including nodes formed as points at the intersection of remaining paths and the perimeter of said second area, said remaining paths being paths remaining undeleted after completion of step (h);

(k) determining cumulative demand for path spaces in said second area;

(l) selecting a sub-net in said second area;

(m) selecting a number of redundant paths of said expanded zone for said sub-net selected in step (1);

(n) comparing said cumulative demand found in step (k) for path spaces with the supply of available path spaces in said second area;

(o) determining a score for each of the redundant paths selected in step (m), said score being a function of at least said comparison of step (n);

(p) deleting a path from said redundant paths selected in step (m), said path of this step being one which has a worst score as determined in step (o), no segment of a redundant path of said initial zone for said selected net being deleted if said segment is part of all minimum paths of said initial zone for said selected net;

(g) repeating steps (1) through (p) until each of said expanded zones generated in step (j) has no redundant paths, said cumulative demand for path spaces being recalculated for each repetition of this step without including paths which were deleted in prior repetitions of step (p);

(r) repeating steps (i) through (q) choosing areas wherein demand for path spaces still exceeds supply; and

(s) interconnecting nodes of each net using available path spaces and paths remaining after step (r)

6. A method for interconnecting nodes in each of a number of nets, comprising the steps of:

(a) generating an initial zone for each net of said nets to be formed, said initial zone, for each net, being a corresponding first subset of a set of all paths which could be used for interconnecting all nodes of said each net, said corresponding first subset also being a corresponding second subset of a set of all segments which could be used for interconnecting said all nodes of said each net with each segment being a part of at least one minimum path of said corresponding first subset;

(b) determining cumulative demand for path spaces created by all initial zones generated in step (a);

(c) comparing said cumulative demand found in step (b) with the supply of available path spaces;

(d) determining a score for each path of paths of said initial zones, said score being a function of at least the comparison of step (c);

(e) selecting a net of said nets;

(f) deleting a redundant path of said paths from an initial zone, of said initial zones, for a net selected in step (e), said redundant path being one which has a worst said score of any of said paths in said initial zone, no segment of a redundant path of said initial zone for said selected net being deleted if said segment is part of all minimum paths of said initial zone for said selected net;

(g) repeating steps (c) through (f) until each of the initial zones generated in step (a) has no redundant paths, said cumulative demand for path spaces being recalculated for each repetition of this step without including paths which were deleted in prior repetitions of step (f);

after having completed steps (a) through (g) and if demand for path spaces still exceeds the supply of available path spaces, the following additional steps are to be taken;

(h) selecting an area where demand for path spaces still exceeds supply;

(i) generating an expanded zone on said area for each sub-net, said expanded zone for each sub-net being any set of paths used to interconnect nodes of each sub-net, said expanded zone for each sub-net containing redundant paths, each said sub-net being that part of a net within said area and also including nodes formed as points at the intersection of remaining paths and the perimeter of said area, said remaining paths being paths remaining undeleted after completion of step (g);

(j) determining cumulative demand for path spaces in said area, said cumulative demand being the path spaces needed in said area for expanded zones generated in step (i);

(k) comparing said cumulative path demand for spaces with the supply of available path spaces in said area;

(l) determining a score for each of the paths of said expanded zones generated in step (i), said score of this step being a function of at least the comparison of step (k);

(m) selecting a sub-net in said area;

(n) deleting a path from said expanded zone for said sub-net, said path being one which has a worst score as determined in step (1);

(o) repeating steps (k) through (n) until each of said expanded zones generated in step (i) has no redundant paths, said cumulative demand for path spaces being recalculated for each repetition of this step without including paths which were deleted in prior repetitions of step (n);

(p) repeating steps (h) through (o) choosing areas wherein demand for path spaces still exceeds supply; and

(g) interconnecting nodes of each net using available path spaces and paths remaining after step (p).

7. A global wiring method for interconnecting nodes in each of a number of nets on a circuit chip, comprising the steps of:

(a) generating an initial zone for each net of said nets to be formed on said chip, said initial zone, for each net, being a corresponding first subset of a set of all paths which could be used for interconnecting all nodes of said each net, said corresponding first subset also being a corresponding second subset of a set of all segments which could be used for interconnecting said all nodes of said each net with each segment being a part of at least one minimum path of said corresponding first subset;

(b) determining cumulative demand for wire spaces created by all initial zones generated in step (a);

(c) selecting a net of said nets;

(d) selecting a number of redundant paths of an initial zone for said net selected in step (c);

(e) comparing said demand found in step (b) with the supply of available wire spaces in an area on said chip, said area being used by said number of redundant paths selected in step (d);

(f) determining a score for each of said redundant paths, said score being a function of at least said comparison of step (e);

(g) deleting a redundant path from said number of redundant paths from said initial zone for said net selected in step (c), said redundant path being one which has a worst score of any of said number of paths selected in step (d), no segment of a redundant path of said initial zone for said selected net being deleted if said segment is part of all minimum paths of said initial zone for said selected net;

(h) repeat steps (c) through (g) selecting nets and paths and deleting paths until all redundant paths have been deleted from said each initial zone for all of said nets, said cumulative demand for wire space being recalculated for each repetition of this step without including paths which were deleted in prior repetitions of step (g); and

(i) interconnecting with electrical conductors nodes of each net using available wire spaces and paths remaining after step (h).

8. A global wiring method for interconnecting nodes in each of a number of nets on a circuit chip, comprising the steps of:

(a) generating an initial zone for each net of said nets to be formed on said chip, said initial zone, for each net, being a corresponding first subset of a set of all paths which could be used for interconnecting all nodes of said each net, said corresponding first subset also being a corresponding second subset of a set of all segments which could be used for interconnecting said all nodes of said each net with each segment being a part of at least one minimum path of said corresponding first subset;

(b) determining cumulative demand for wire spaces through cells on said chip created by all initial zones generated in step (a);

(c) comparing said cumulative demand found in step (b) with the supply of available wire spaces in each of said cells;

(d) determining a score for each path of paths of said initial zones, said score being a function of at least the comparison of step (c);

(e) selecting a net of said nets;

(f) deleting a redundant path from an initial zone for a net selected in step (e), said redundant path being one which has a worst said score of any of said paths in said initial zone for said net selected in step (e), to segment of a redundant path of said initial zone for said selected net being deleted if said segment is part of all minimum paths of said initial zone for said selected net;

(g) repeating steps (c) through (f) until each of the initial zones generated in step (a) has no redundant paths, said cumulative demand for wire spaces being recalculated for each repetition of this step without including paths which were deleted in prior repetitions of step (f); and

(h) interconnecting nodes of each net to be formed on said chip using available path spaces and paths, for each net, which paths were not deleted after the completion of step (g).

9. A global wiring method for interconnecting nodes in each of a number of nets on a circuit chip, comprising the steps of:

(a) generating an initial zone for each net of said nets to be formed on said chip, said initial zone, for each net, being a corresponding first subset of a set of all paths which could be used for interconnecting all nodes of said each net, said corresponding first subset also being a corresponding second subset of a set of all segments which could be used for interconnecting said all nodes of said each net with each segment being apart of at least one minimum path of said corresponding first subset

(b) determining cumulative demand for wire spaces through cells on said chip created by all initial zones generated in step (a);

(c) comparing said cumulative demand found in step (b) with the supply of available wire spaces in each of said cells;

(d) determining a score for each path of paths of said initial zones, said score being a function of at least the comparison of step (c);

(e) selecting a net of said nets;

(f) deleting a redundant path from an initial zone, of said initial zones, for a net selected in step (e), said redundant path being one which has a worst said score of any of said paths in said initial zone for said net selected in step, no segment of a redundant paths of said initial zone for said selected net being deleted if said segment is part of all minimum paths of said initial zone for said selected net (e);

(g) repeating steps (c) through (f) until each of the initial zones generated in step (a) has no redundant paths, said cumulative demand for wire spaces being recalculated for each repetition of this step without including paths which were deleted in prior repetitions of step (f);

after having completed steps (a) through (h) and if demand for path spaces still exceeds the supply of available path spaces, the following additional steps are to be taken;

(h) selecting an area on said chip where demand for wire spaces still exceeds supply;

(i) generating an expanded zone on said area for each sub-net, said expanded zone for each sub-net being any set of paths used to interconnect nodes of each sub-net, said expanded zone for each sub-net containing redundant paths, each said sub-net being that part of a net within said area on said chip and also including nodes formed as points at the intersection of remaining paths and the perimeter of said area, said remaining paths being paths remaining undeleted after completion of step (g);

(j) determining cumulative demand for wire spaces through cells in said area on said chip, said cumulative demand being the wire spaces needed in each cell in said area on said chip for expanded zones generated in step (i);

(k) comparing said cumulative demand for wire spaces with the supply of available wire spaces in each cell in said area of said chip;

(l) determining a score for each of the paths of said expanded zones generated in step (i), said score of this step being a function of at least the comparison of step (k);

(m) selecting a sub-net in said area;

(n) deleting a path from said expanded zone for said sub-net selected in step (m), said path of this step being one which has a worst said score as determined in step (1) for any path of said sub-net selected in step (m), no segment of a redundant path of said initial zone for said selected net being deleted if said segment is part of all minimum paths of said initial zone for said selected net;

(o) repeating steps (j) through (n) until each of said expanded zones generated in step (i) has no redundant paths, said cumulative demand for wires spaces in said area being recalculated for each repetition of this step without including paths which were deleted in prior repetitions of step (n);

(p) repeating steps (h) through (o) choosing areas wherein demand for path spaces still exceeds supply; and

(q) interconnecting nodes of each to be formed on said chip using available wire spaces and paths remaining after step