Routing method in computer aided customization of a two level automated universal array

• US 4,613,941 A
• Filed: 07/02/1985
• Issued: 09/23/1986
• Est. Priority Date: 07/02/1985
• Status: Expired due to Fees

• Current Assignee: The United States of America As Represented By The Secretary of Agriculture
• Original Assignee: The United States Of America As Represented By The Secretary Of The Army
• Inventors: Smith, David C., Noto, Richard
• Primary Examiner(s): Gellner, Michael L.
• Application Number:
  US06/751,339
• Time in Patent Office: 448 Days
• Field of Search: 364/488, 364/489, 364/490, 364/491
• US Class Current: 716/55
• CPC Class Codes: G06F 30/394 Routing G06F30/396 takes precedence

Abstract

A routing method implemented in the stored programs of a digital computer ich is programmably operated to generate the wire interconnect masks for a two level metallization automated universal array having undefined roadbeds between rows of cells comprised of identical semiconductor device basic units which are further interconnected to provide a particular integrated circuit structure. Conductor routing is provided by a computer aided design system that, among other things, carries out a route analysis process which determines in which roadbed each wire should be tentatively routed in conjunction with generating a routing density profile for minimizing congestion for a particular circuit design and when the roadbed density is exceeded, certain wires are removed under a set of criteria for routing by a pathfinder routing process. Following route analysis, detailed routing and rerouting is performed sequentially by a direct routing process, a greedy channel routing process, and a pathfinder routing process with rerouting being performed after each channel router and pathfinding process. Furthermore, the greedy channel routing process makes a single pass from left to right in all wires which cross successive points simultaneously and, if necessary, deleting a wire or wires which are then rerouted by the pathfinding process.

Claims

1. A method carried out by a computer for converting a multiple level metal universal array into a custom integrated circuit in which pre-placed basic units are arranged in parallel cell rows in a semiconductor device basic unit row region, with said cell rows being spaced apart by undefined wiring roadbeds adapted to contain conductors which run parallel to or perpendicular to the roadbeds on at least two intermediate levels of metallization separated by a dielectric layer and interconnected by selectively located vias, comprising the steps of:

(A) executing an input routine wherein input data for a predetermined integrated circuit design are entered into said computer;

(B) executing a cell placement routine which places said basic units in a predetermined configuration in said cell rows of said basic unit row region so as to maximize the effectiveness of the subsequent conductor routing;

(C) executing a conductor routing routine for enhancing the success of conductor routing further comprising the steps of performing an initial route analysis process for the desired circuit design to determine in which roadbed each wire should be routed and eliminating certain projected wires for subsequent pathfinder routing under a predetermined set of criteria when the wiring density exceeds the available tracks in any given roadbed due to the fact that if said wires are not removed, the probability for 100% completion of conductor routing is minimum and thereafter performing a conductor routing process including a direct routing process which operates to route very short wires of a predetermined class of wires, a channel routing process which operates to route most of the remaining wires while additionally eliminating certain wires from a roadbed for subsequent pathfinder routing under another predetermined set of criteria, also when the wiring density exceeds the available tracks in any given roadbed, and a pathfinder routing process which operates to route wires previously eliminated by said previous route analysis and channel routing process; and

(D) executing an output routine for converting cell placement and conductor routing data provided by steps (B) and (C) into respective customization masks for the levels of metallization and their interconnection vias as well as the contact level.

2. The method as defined by claim 1 wherein said step of performing route analysis in step (C) further includes the steps of:

(a) smashing all nodes into pin pairs or single wires;

(b) performing an initial pin reassignment and cell reorientation step whereby all allowable combinations of assignment and cell orientation are tried and evaluated;

(c) resmashing all nodes into pin pairs;

(d) performing an initial roadbed assignment of conductors;

(e) performing a dummy feedthrough placement for a predetermined class of conductors;

(f) resmashing all nodes with real pins and dummy feedthroughs;

(g) determining a final roadbed assignment of conductors;

(h) minimizing roadbed congestion by wire removal for said pathfinder routing process; and

(i) setting up a routing area and associated array.

3. The method as defined by claim 2 wherein said step (a) of smashing all nodes into pin pairs comprises attempting to minimize the vertical and horizontal distance for each node while permitting class 5 wires to skip cell rows of said basic unit row region,

a class 5 wire being defined as a conductor between pins on two different cell rows of said basic unit row region.

4. The method as defined by claim 2 wherein said step (d) of performing an initial roadbed assignment additionally includes the step of generating a routing density profile for each roadbed and in accordance therewith tentatively choosing a roadbed for each wire depending upon another predetermined set of criteria for the roadbed region traversed.

5. The method as defined by claim 4 wherein said another predetermined set of criteria is a function of the roadbed density in the region traversed and the specific class of wires being assigned, the classes of wires further including:

class 1 wires which are defined as wires between a pair of pins on the same cell row of said basic unit row region;

class 2 wires which are defined as wires between a pair of pins on the same side row of input/output pads located on either side of said basic unit row region;

class 4 wires which are defined as wires between a pin on a cell row of said basic unit row region and a pin on a side row of input/output pads;

class 5 wires which are defined as wires between pins on two different cell rows of said basic unit row region; and

class 6 wires which are defined as wires spanning the width of said basic unit row region and connected between respective pins on opposite side rows of input/output pads.

6. The method as defined by claim 5 wherein said step (d) of performing an initial roadbed assignment includes the steps of:

(i) assigning class 1 wires to a roadbed on either side of the specific cell row depending upon the routing density thereat,

(ii) assigning class 2 wires to the side of a roadbed,

(iii) assigning class 4 wires to a roadbed on either side of a specific cell row of said basic unit row region depending upon which is closer to a sink or destination pin at said side row of input/output pads,

(iv) preventing class 5 wires from skipping cell rows of said basic unit row region, and

(v) excluding the assignment of class 6 wires to any roadbed and thereafter routing said wires by said pathfinder routing process.

7. The method as defined by claim 6 wherein said step (i) for assigning class 1 wires further comprises the steps of:

(vi) assigning a class 1 wire in the roadbed having the lower density where the routing density on either side of a cell row is greater than 75%;

(vii) assigning a class 1 wire to the same roadbed as an existing wire where the average density in the roadbeds on both sides of a cell row is less than 75% and a wire already exists in one of the roadbeds for the same node pin; and

(viii) where a routing density of less than 75% exists in the roadbeds in both sides of a cell row and the sum of adjacent unused pin positions is unequal, then assigning a class 1 wire in the roadbed adjacent the greater number of unused pin positions.

8. The method as defined by claim 2 wherein said step (e) of performing dummy feedthrough placement comprises the steps of:

(i) determining unused and unguarded pin positions on the cell row for routing skipped cell row class 5 wires permitted during steps (a) and (c);

(ii) smashing said class 5 skip row wires into a pair of class 5 non-skipped cell row wires terminating at the selected unused pin; and

(iii) thereafter making a set of iterative passes to improve the feedthrough position and said pair of class 5 non-skipped cell row wires to improve their placement in terms of routing density,

a class 5 wire being defined as a wire between two pins respectively located on two different cell rows of said basic unit row region.

9. The method as defined by claim 2 wherein said step (g) of determining final roadbed assignment also includes the step of generating a routing density profile for each roadbed for placing conductors in adjoining roadbeds of a cell row as a function of roadbed density and the class of wires being assigned to said roadbeds.

10. The method as defined by claim 2 wherein said step (h) of minimizing roadbed congestion by wire removal further comprises the steps of:

(i) analyzing each roadbed assignment to determine if the roadbed density is exceeded, and

(ii) eliminating class 1 and class 5 wires in accordance with the following criteria if said roadbed density is exceeded;

(1) the candidate wire must span some portion of the congested area; and

(2) the pins for the candidate wire must not be in the area of congestion;

class 1 wires being defined as conductors between two pins in the same cell row of said basic unit row region and class 5 wires being defined as conductors between pins on two different cell rows of said basic unit row region.

11. The method of claim 10 and additionally including the following steps until the best fit obtains:

(iii) determining the wire which traverses the span of highest density within the congested area;

(iv) determining the wire with pins with the minimum density in the vicinity of the pins; and

(v) selecting a class 5 wire for removal before a class 1 wire.

12. The method as defined by claim 1 wherein said step of performing a channel routing process comprises a greedy channel routing process including the step of removing a wire from a roadbed in accordance with the following criteria:

(1) the wire must be currently being routed in a particular roadbed;

(2) eliminate class 2, class 4, and class 6 wires from consideration while considering class 1 and class 5 wires for elimination; and

(3) select class 1 and 5 wires having pins which are not in a congested area;

class 1 wires being defined as conductors between respective pin pairs on the same cell row of said basic unit region, class 2 wires being defined as conductors between respective pin pairs on the same side row of input/output pads adjacent said basic unit region, class 4 wires being defined as conductors between a pin on a cell row of said basic unit region and a side row of input/output pads, class 5 wires being defined as conductors between respective pin pairs on two different cell rows of said basic unit row region, and class 6 wires being defined as conductors spanning the width of the basic unit row region to respective pin pairs on opposing side rows of input/output pads.

13. The method as defined by claim 12 wherein said step of removing a wire from a roadbed applies the following additional criteria until the best wire is found for elimination;

(4) the wire must be within the tolerance of all those with the longest span of the congestion;

(5) the wire has pins with the least dense area or at least less than 80 % density; and

(6) class 5 wires are selected for elimination over class 1 wires.