EP0145925A2 — Iterative method for establishing connections bet…

Claim 1

Independent Claim 293 words

A method of establishing a plurality of connections, using global routing techniques on a data processing machine, each connection joining two pins using links arranged between nodes in a rectangular grid having X and Y coordinates in one or more planes labelled by a Z coordinate, wherein said connections are formed substantially from I, L, Z and U-shaped paths comprising the steps of: a) inputting information pertaining to grid specifications and connection listings; b) randomly assigning an initial path for each connection on said grid using a randomly oriented substantially L-shaped path, unless said pins lie along the same X or Y coordinate in which case an I-shaped path is used, and randomly assigning each of said initial paths to one of said one or more planes; c) beginning a pass through said connections by defining a penalty function in terms of specified costs; d) selecting one of said connections which has not been considered previously during this pass and removing from said grid the path assigned to said connection; e) calculating said penalty function for each of the substantially I, L, Z, and U-shaped paths which joins the two pins of said connection and whose length does not exceed a specified value; f) selecting one of said paths based on the value of said penalty function; g) assigning said selected path to said connection; h) repeating steps d) through g) above until a desired number of connections have been routed thereby completing a pass; i) generating data describing X, Y and Z coordinates of the paths assigned to said routed connections; j) repeating steps c) through i) above until a desired number of passes have been completed; and k) utilizing said data to establish said plurality of connections corresponding to said data.

Claim 2

Independent Claim 293 words

A method of establishing a plurality of connections, using global routing techniques on a data processing machine, each connection joining two pins using links arranged between nodes in a rectangular grid having X and Y coordinates in one or more planes labelled by a Z coordinate, wherein said connections are formed substantially from I, L, Z and U-shaped paths comprising the steps of: a) inputting information pertaining to grid specifications and connection listings; b) randomly assigning an initial path for each connection on said grid using a randomly oriented substantially L-shaped path, unless said pins lie along the same X or Y coordinate in which case an I-shaped path is used, and randomly assigning each of said initial paths to one of said one or more planes; c) beginning a pass through said connections by defining a penalty function in terms of specified costs; d) selecting one of said connections which has not been considered previously during this pass and removing from said grid the path assigned to said connection; e) calculating said penalty function for each of the substantially I, L, Z, and U-shaped paths which joins the two pins of said connection and whose length does not exceed a specified value; f) selecting one of said paths based on the value of said penalty function; g) assigning said selected path to said connection; h) repeating steps d) through g) above until a desired number of connections have been routed thereby completing a pass; i) generating data describing X, Y and Z coordinates of the paths assigned to said routed connections; j) repeating steps c) through i) above until a desired number of passes have been completed; and k) utilizing said data to establish said plurality of connections corresponding to said data.

Claim 3

Dependent Claim 27 words

The method of claim 1 wherein the step of selecting one of said paths is performed by selecting that path having a penalty function of smallest value.

Claim 4

Dependent Claim 92 words

The method of claim 1 wherein the step of defining a penalty function includes the following: a cost (WX) per link of path along the X coordinate; a cost (WY) per link of path along the Y coordinate; a cost (BEND) for each bend present in the path; and, a cost (CONG) for each unit by which the number of wires passing through a link (LOAD), exceeds some preselected fraction (THRESH), of the maximum number (CAPACITY) of paths allowed to pass through that link, each of said costs being a real number.

Claim 5

Dependent Claim 16 words

The method of claim 3 wherein the costs may vary as a function of node location.

Claim 6

Dependent Claim 19 words

The method of claim 3 wherein the costs may vary as a function of which connection is being routed.

Claim 7

Dependent Claim 18 words

The method of claim 1 wherein the step of utilizing said data includes the step of generating artwork.

Claim 8

Dependent Claim 20 words

The method of claim 1 wherein the step of utilizing said data includes the step of controlling connection fabrication apparatus.

Claim 9

Independent Claim 71 words

The method of any one of claims 1 to 7, wherein the step of selecting one of said paths comprises: assigning a non-negative, numerical weight to each said path, the weight depending upon the value of the penalty function, and decreasing as the value of the penalty function increases; selecting a path from among said paths, with a probability proportional to said weight; and assigning said selected path to said connection.

Claim 10

Independent Claim 43 words

The method of any one of claims 1 to 7, wherein the step of calculating said penalty function is performed using a mazerouter procedure to calculate a path having a penalty function of smallest value, which joins the two pins of said connection.

Claim 11

Independent Claim 396 words

A method of establishing a plurality of connections, using detailed routing techniques on a data processing machine, each connection joining two pins using links arranged between nodes in a rectangular grid having x and y coordinates in one or more planes labelled by a z coordinate, comprising the steps of: a) inputting information pertaining to grid model specifications, such as blockage and via locations, and connection listings; b) randomly assigning an initial path for each connection on said grid using a randomly oriented substantially L-shaped path unless said pins lie along the same x or y coordinates in which an I-shaped path is used, an randomly assigning each of said initial paths to one of said one or more planes; c) beginning a pass through said connections be defining a penalty function in terms of specified costs constituting non-negative numbers wherein said costs include: a cost (Wx) per link of path in a x direction; a cost (Wy) per link of path in a y direction; a cost (OVER) for using a node already used by another path or occupied by a blockage; a cost (BEND) for each path bend; a cost (VIA) for each via used; a cost (VIAOVER) for using a via already occupied by another path; a cost (VIAOVER) for using a via already occupied by another path; a cost (REGION) for each link that the path uses within user specified regions within one or more of said planes; a cost (ADJAC) for each link that the path uses, which link lies adjacent to another path within the same plane or adjacent planes; d) selecting one of said connections which has not been considered previously during this pass; e) determining if said connection is to be rerouted; f) removing from said grid the path assigned to said connection to be rerouted; g) rerouting said connection using a mazerouter procedure to calculate a path having a penalty function of smallest value; h) assigning said calculated path to said connection; i) repeating steps d) through h) above until a desired number of connections have been selected thereby completing a pass; j) generating data describing the x, y and z coordinates of the paths assigned to said routed connections; and k) repeating steps c) through j) above until a desired number of passes have been completed; 1) establishing said plurality of connections corresponding to said data.

Claim 12

Independent Claim 396 words

A method of establishing a plurality of connections, using detailed routing techniques on a data processing machine, each connection joining two pins using links arranged between nodes in a rectangular grid having x and y coordinates in one or more planes labelled by a z coordinate, comprising the steps of: a) inputting information pertaining to grid model specifications, such as blockage and via locations, and connection listings; b) randomly assigning an initial path for each connection on said grid using a randomly oriented substantially L-shaped path unless said pins lie along the same x or y coordinates in which an I-shaped path is used, an randomly assigning each of said initial paths to one of said one or more planes; c) beginning a pass through said connections be defining a penalty function in terms of specified costs constituting non-negative numbers wherein said costs include: a cost (Wx) per link of path in a x direction; a cost (Wy) per link of path in a y direction; a cost (OVER) for using a node already used by another path or occupied by a blockage; a cost (BEND) for each path bend; a cost (VIA) for each via used; a cost (VIAOVER) for using a via already occupied by another path; a cost (VIAOVER) for using a via already occupied by another path; a cost (REGION) for each link that the path uses within user specified regions within one or more of said planes; a cost (ADJAC) for each link that the path uses, which link lies adjacent to another path within the same plane or adjacent planes; d) selecting one of said connections which has not been considered previously during this pass; e) determining if said connection is to be rerouted; f) removing from said grid the path assigned to said connection to be rerouted; g) rerouting said connection using a mazerouter procedure to calculate a path having a penalty function of smallest value; h) assigning said calculated path to said connection; i) repeating steps d) through h) above until a desired number of connections have been selected thereby completing a pass; j) generating data describing the x, y and z coordinates of the paths assigned to said routed connections; and k) repeating steps c) through j) above until a desired number of passes have been completed; 1) establishing said plurality of connections corresponding to said data.

Claim 13

Dependent Claim 51 words

The method of claim 11, further comprising inputting information related to one or more connections pertaining to a perimeter of a swath within which the connection preferentially is to be routed; and in which said costs further include: a cost (BORDER) for each link that the path uses outside said perimeter.

Claim 14

Independent Claim 381 words

A method of establishing a plurality of routed jobs, using detailed routing techniques on a data processing machine, wherein each job is defined to be (i) a pair of pins, (ii) a pin and a path, or (iii) two paths; each routed job using links arranged between nodes in a rectangular grid having x and y coordinates in one or more planes labelled by a z coordinate, comprising the steps of: a) inputting information pertaining to grid model specifications, such as blockage and via locations, and a job list and a job priority list which identifies a specific order for routing said jobs; b) beginning a pass through said jobs by defining a penalty function in terms of specified costs constituting non- negative numbers wherein said costs include: a cost (Wx) per link of path in an x direction; a cost (Wy) per link of path in a y direction; a cost (OVER) for using a node already used by another path or occupied by a blockage; a cost (BEND) for each path bend; a cost (VIA) for each via used; a cost (VIAOVER) for using a via already occupied by another path; a cost (REGION) for routing along each link that the path uses within specified regions within one or more of said planes; a cost (ADJAC) for each link that the path uses, which link lies adjacent to another path within the same or adjacent planes; c) selecting one of said jobs which has not been considered previously during this pass, according to said job priority list; d) determining if said job is to be routed during this pass; e) removing from said grid the path assigned to said job to be routed, if said job has been routed previously; f) routing said job using a mazerouter procedure to calculate a path having a penalty function of smallest value; g) repeating steps c) through f) above until a desired number of jobs have been selected thereby completing this pass; h) generating data describing the x, y, z coordinates of the paths assigned to said plurality of jobs; i) repeating steps b) through h) above until a desired number of passes have been completed; and j) utilizing said data to establish said plurality of routed jobs corresponding to said data.

Claim 15

Independent Claim 381 words

A method of establishing a plurality of routed jobs, using detailed routing techniques on a data processing machine, wherein each job is defined to be (i) a pair of pins, (ii) a pin and a path, or (iii) two paths; each routed job using links arranged between nodes in a rectangular grid having x and y coordinates in one or more planes labelled by a z coordinate, comprising the steps of: a) inputting information pertaining to grid model specifications, such as blockage and via locations, and a job list and a job priority list which identifies a specific order for routing said jobs; b) beginning a pass through said jobs by defining a penalty function in terms of specified costs constituting non- negative numbers wherein said costs include: a cost (Wx) per link of path in an x direction; a cost (Wy) per link of path in a y direction; a cost (OVER) for using a node already used by another path or occupied by a blockage; a cost (BEND) for each path bend; a cost (VIA) for each via used; a cost (VIAOVER) for using a via already occupied by another path; a cost (REGION) for routing along each link that the path uses within specified regions within one or more of said planes; a cost (ADJAC) for each link that the path uses, which link lies adjacent to another path within the same or adjacent planes; c) selecting one of said jobs which has not been considered previously during this pass, according to said job priority list; d) determining if said job is to be routed during this pass; e) removing from said grid the path assigned to said job to be routed, if said job has been routed previously; f) routing said job using a mazerouter procedure to calculate a path having a penalty function of smallest value; g) repeating steps c) through f) above until a desired number of jobs have been selected thereby completing this pass; h) generating data describing the x, y, z coordinates of the paths assigned to said plurality of jobs; i) repeating steps b) through h) above until a desired number of passes have been completed; and j) utilizing said data to establish said plurality of routed jobs corresponding to said data.

Claim 16

Dependent Claim 19 words

13 The method of claim 12 wherein the step of utilizing said data includes the step of generating artwork.

Claim 17

Dependent Claim 21 words

14 The method of claim 12 wherein the step of utilizing said data includes the step of controlling connection fabrication apparatus.

Claim 18

Dependent Claim 528 words

1 5 A method of establishing a plurality of connections, using global and detailed routing techniques on a data processing machine, each connection joining two pins, using a global grid comprising links arranged between nodes in a rectangular grid having X and Y coordinates in one or more planes labelled by a Z coordinate, and a detailed grid comprising links arranged between nodes in a rectangular grid having x and y coordinates in one or more planes labelled by a z coordinate, comprising the steps of: a) inputting information pertaining to grid specifications and connection listings including global and detailed grid positions of said pins; b) randomly assigning an initial path for each connection on said global grid using a randomly oriented, substantially L-shaped path, unless said pins lie along the same X or Y coordinate in which case an I-shaped path is used, and randomly assigning each of said initial paths to one of said one or more planes; c) beginning a global routing pass through said connections by defining a penalty function in terms of specified costs wherein said costs are real numbers; d) selecting one of said connections which has not been considered previously during this global routing pass, and removing from said global grid the path assigned to said connection; e) calculating said penalty function for each substantially I, L, Z and U-shaped path which joins the two pins of said connection, and whose length does not exceed a specified value; f) selecting one of said paths based on the value of said penalty function; g) assigning said selected path to said connection; h) repeating steps d) through g) above until a desired number of connections have been rerouted thereby completing one global routing pass; i) generating data describing X, Y and Z coordinates of the paths assigned to said plurality of connections; j) repeating steps c) through i) above until a desired number of global routing passes have been completed; k) defining, for each connection, a global swath comprising those global cells through which said connection has been globally routed; 1) beginning a detailed routing pass through said connections by defining said penalty function in terms of specified costs wherein said costs are nonnegative, real numbers; m) selecting one of said connections which has not been considered previously during this detailed routing pass; n) removing from said detailed grid, the path assigned to said connection to be routed, if said connection has been routed previously on the detailed grid; o) routing said removed connection using a mazerouter procedure to calculate a path having a penalty function of smallest value which joins the two pins of said connection on said detailed grid; p) assigning said calculated path to said connection; q) repeating steps m) through p) above until a desired number of connections have been selected thereby completing a detailed routing pass; r) generating data describing x, y and z coordinates of the paths assigned to said plurality of connections; and s) repeating steps 1) through r) above until a desired number of detailed routing passes have been completed; and t) utilizing said data to establish said plurality of connections corresponding to said data.

Claim 19

Dependent Claim 528 words

1 5 A method of establishing a plurality of connections, using global and detailed routing techniques on a data processing machine, each connection joining two pins, using a global grid comprising links arranged between nodes in a rectangular grid having X and Y coordinates in one or more planes labelled by a Z coordinate, and a detailed grid comprising links arranged between nodes in a rectangular grid having x and y coordinates in one or more planes labelled by a z coordinate, comprising the steps of: a) inputting information pertaining to grid specifications and connection listings including global and detailed grid positions of said pins; b) randomly assigning an initial path for each connection on said global grid using a randomly oriented, substantially L-shaped path, unless said pins lie along the same X or Y coordinate in which case an I-shaped path is used, and randomly assigning each of said initial paths to one of said one or more planes; c) beginning a global routing pass through said connections by defining a penalty function in terms of specified costs wherein said costs are real numbers; d) selecting one of said connections which has not been considered previously during this global routing pass, and removing from said global grid the path assigned to said connection; e) calculating said penalty function for each substantially I, L, Z and U-shaped path which joins the two pins of said connection, and whose length does not exceed a specified value; f) selecting one of said paths based on the value of said penalty function; g) assigning said selected path to said connection; h) repeating steps d) through g) above until a desired number of connections have been rerouted thereby completing one global routing pass; i) generating data describing X, Y and Z coordinates of the paths assigned to said plurality of connections; j) repeating steps c) through i) above until a desired number of global routing passes have been completed; k) defining, for each connection, a global swath comprising those global cells through which said connection has been globally routed; 1) beginning a detailed routing pass through said connections by defining said penalty function in terms of specified costs wherein said costs are nonnegative, real numbers; m) selecting one of said connections which has not been considered previously during this detailed routing pass; n) removing from said detailed grid, the path assigned to said connection to be routed, if said connection has been routed previously on the detailed grid; o) routing said removed connection using a mazerouter procedure to calculate a path having a penalty function of smallest value which joins the two pins of said connection on said detailed grid; p) assigning said calculated path to said connection; q) repeating steps m) through p) above until a desired number of connections have been selected thereby completing a detailed routing pass; r) generating data describing x, y and z coordinates of the paths assigned to said plurality of connections; and s) repeating steps 1) through r) above until a desired number of detailed routing passes have been completed; and t) utilizing said data to establish said plurality of connections corresponding to said data.

Claim 20

Dependent Claim 25 words

A circuit board wherein a plurality of connections are formed between specified pins according to the method of any one of claims 1 to 15.

Iterative method for establishing connections between nodes and the resulting product

Abstract

Inventors

Bibliographic Details

Claims Analysis

References Cited (Backward Citations)

USPTO Annuity & Maintenance Windows

Assigned Categories & Tags

Assign Category Tag