Iterative method for establishing connections and resulting product

Claim 3

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

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

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

Claim 6

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

Claim 7

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

Claim 8

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

Claim 9

The method of claim 1 wherein said costs relate to path shape complexity and path position with respect to other paths and component on said grid.

Claim 12

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

Claim 13

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

Claim 16

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

Claim 17

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

Claim 18

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

Claim 19

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

Claim 20

The method of claim 12 wherein the mazerouter procedure at a given execution of step (e) comprises the following additional steps: (e)(1) calculating a lowest cost routing using one value of a penalty parameter; (e)(2) incrementing or decrementing the value of said penalty parameter to generate a new penalty parameter value if a property of the resulting routing has a value exceeding the upper limit of a user specified range of allowable values or is less than a minimum value of said user specified range, respectively; (e)(3) recalculating a lowest cost routing using said new penalty parameter value; and (e)(4) repeating the steps (e)(1) to (e)(3) a user specified number of times or until said property has a value within said user specified range, whichever occurs first.

Claim 23

The method of claim 18 wherein costs (Wx) and (Wy) vary as a function of link location on the grid.

Claim 24

The method of claim 18 wherein the cost (OVER) varies as a function of node location on the grid.

Claim 25

The method of claim 18 wherein the cost (OVER) varies as a function of the locations of other path crossings on the grid.

Claim 26

The method of claim 18 where one or more costs vary as a function of which connection is being routed.

Claim 27

The method of claim 18 wherein the costs (Wx) and (Wy) are chosen to be substantially equal to each other for one or more planes and for one or more passes.

Claim 28

The method of claim 18 wherein the step for defining each penalty function includes the further step of categorizing certain costs as (COST ILLEGAL) and certain other costs as (COST LEGAL) and varying the relative values of said costs such that the ratio (COST ILLEGAL)/(COST LEGAL) increases for a first series of passes, decreases for a next series of passes, and increases again for a final series of passes.

Claim 29

The method of claim 18 wherein the mazerouter procedure at a given execution of step (g) comprises the following additional steps: (g)(1) calculating a lowest cost routing using one value of a penalty parameter; (g)(2) incrementing or decrementing the value of said penalty parameter to generate a new penalty parameter value if a property of the resulting routing has a value exceeding the upper limit of a user specified range of allowable values or is less than a minimum value of said user specified range, respectively; (g)(3) recalculating a lowest cost routing using said new penalty parameter value; and (g)(4) repeating the steps (g)(1) to (g)(3) a user specified number of times or until said property has a value within said user specified range, whichever occurs first.

Claim 32

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

Claim 33

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

Claim 34

The method of claim 26 wherein the mazerouter procedure at a give execution of step (g) comprises the following additional steps: (g)(1) calculating a lowest cost routing using one value of a penalty parameter; (g)(2) incrementing or decrementing the value of said penalty parameter to generate a new penalty parameter value if a property of the resulting routing has a value exceeding the upper limit of a user specified range of allowable values or is less than a minimum value of said user specified range, respectively; (g)(3) recalculating a lowest cost routing using said new penalty parameter value; and (g)(4) repeating steps (g)(1)-(g)(3) a user specified number of times or until said property has a value within said user specified range, whichever occurs first.

Claim 37

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

Claim 38

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

Claim 39

The method of claim 30 wherein the mazerouter procedure at a given execution of step (f) comprises the following additional steps: (f)(1) calculating a lowest cost routing using one value of a penalty parameter; (f)(2) incrementing or decrementing the value of said penalty parameter to generate a new penalty parameter value if a property of the resulting routing has a value exceeding the upper limit of a user specified range of allowable values or is less than a minimum value of said user specified range, respectively; (f)(3) recalculating a lowest cost routing using said new penalty parameter value; and (f)(4) repeating steps (f)(1)-(f)(3) a user specified number of times or until said property has a value within said user specified range, whichever occurs first.

Claim 42

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

Claim 43

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

Claim 44

The method of claim 34 wherein the mazerouter procedure at a given execution of step (o) comprises the following additional steps: (o)(1) calculating a lowest cost routing using one value of a penalty parameter; (o)(2) incrementing or decrementing the value of said penalty parameter to generate a new penalty parameter value if a property of the resulting routing has a value exceeding the upper limit of a user specified range of allowable value or is less than a minimum value of said user specified range, respectively; (o)(3) recalculating a lowest cost routing using said new penalty parameter value; and (o)(4) repeating steps (o)(1)-(o)(3) a user specified number of times or until said property has a value within said user specified range, whichever occurs first.

Claim 45

A circuit board wherein a plurality of connections are formed between specified pins according to the 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, said method comprising the steps of: (a) inputting information to said data processing machine 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, 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 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 (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 through said connections begun in step (c); (e) determining if said selected connections is to be rerouted; (f) removing from said grid the path assigned to said selected connection to be rerouted; (g) rerouting said selected connection using a mazerouter procedure to calculate a path having a penalty function of smallest value; (h) assigning said calculated path to said selected 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; (l) establishing said plurality of connections corresponding to said data.

Claim 46

A circuit board wherein a plurality of connections are formed between specified pins according to the 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, said method comprising the steps of: (a) inputting information to said data processing machine 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, 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 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 (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 through said connections begun in step (c); (e) determining if said selected connections is to be rerouted; (f) removing from said grid the path assigned to said selected connection to be rerouted; (g) rerouting said selected connection using a mazerouter procedure to calculate a path having a penalty function of smallest value; (h) assigning said calculated path to said selected 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; (l) establishing said plurality of connections corresponding to said data.

Claim 47

A circuit board wherein a plurality of connections are formed between specified pins according to the 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, said method comprising the steps of: (a) inputting information to said data processing machine pertaining to grid model specifications, such as blockage and via locations, and connection listings and information related to one or more connections pertaining to a perimeter of a swath within which the connection preferentially is to be routed; (b) randomly assigning an initial path for each connection on said grid for which no perimeter information has been provided, 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, 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 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 (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; and a cost (BORDER) for each link that the path uses outside said perimeter; (d) selecting one of said connections which has not been considered previously during this pass through said connections which pass was initiated in step (c); (e) determining if said selected connection is to be routed during this pass; (f) removing from said grid, the path assigned to said selected connection to be routed if said connection has been previously routed; (g) using a mazerouter procedure to calculate a path having a penalty function of smallest value, which joins the two pins of said selected connection; (h) assigning said calculated path to said selected connection; (i) repeating steps (d) through (h) above until a desired number of connections have been selected thereby completing this pass; (j) generating data describing the x, y and z coordinates of the paths assigned to said routed connections; (k) repeating steps (c) through (j) above until a desired number of passes have been completed; and (l) utilizing said data to establish said plurality of connections using said data.

Claim 48

A circuit board wherein a plurality of connections are formed between specified pins according to the 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, said method comprising the steps of: (a) inputting information to said data processing machine pertaining to grid model specifications, such as blockage and via locations, and connection listings and information related to one or more connections pertaining to a perimeter of a swath within which the connection preferentially is to be routed; (b) randomly assigning an initial path for each connection on said grid for which no perimeter information has been provided, 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, 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 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 (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; and a cost (BORDER) for each link that the path uses outside said perimeter; (d) selecting one of said connections which has not been considered previously during this pass through said connections which pass was initiated in step (c); (e) determining if said selected connection is to be routed during this pass; (f) removing from said grid, the path assigned to said selected connection to be routed if said connection has been previously routed; (g) using a mazerouter procedure to calculate a path having a penalty function of smallest value, which joins the two pins of said selected connection; (h) assigning said calculated path to said selected connection; (i) repeating steps (d) through (h) above until a desired number of connections have been selected thereby completing this pass; (j) generating data describing the x, y and z coordinates of the paths assigned to said routed connections; (k) repeating steps (c) through (j) above until a desired number of passes have been completed; and (l) utilizing said data to establish said plurality of connections using said data.

Claim 49

A circuit board wherein a plurality of connections are formed between specified pins according to the 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, said method comprising the steps of: (a) inputting information to said data processing machine 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 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 (REGION) for each link that the path uses within specified regions within user 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 selected job is to be routed during this pass; (e) removing from said grid the path assigned to said selected job to be routed, if said selected job has been routed previously; (f) routing said selected 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 and 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 establishing said plurality of routed jobs corresponding to said data.

Claim 50

A circuit board wherein a plurality of connections are formed between specified pins according to the 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, said method comprising the steps of: (a) inputting information to said data processing machine 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 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 (REGION) for each link that the path uses within specified regions within user 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 selected job is to be routed during this pass; (e) removing from said grid the path assigned to said selected job to be routed, if said selected job has been routed previously; (f) routing said selected 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 and 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 establishing said plurality of routed jobs corresponding to said data.

Claim 51

A circuit board wherein a plurality of connections are formed between specified pins according to the 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 to said data processing machine pertaining to grid model 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 coordinates 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 pass, and removing from said global grid the path assigned to said selected connection; (e) calculating said penalty function for each substantially I, L, Z and U-shaped path which joins the two pins of said selected 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 selected 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) assuming, for each connection, a global swath comprising those global cells through which said connection has been globally routed; (l) beginning a detailed routing pass through said connections by defining said penalty function in terms of specified costs wherein said costs are non-negative, 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 selected in step (m), if said connection selected in step (m) has been routed previously on the detailed grid; (o) routing said removed connection selected in step (m) using a mazerouter procedure to calculate a path having a penalty function of smallest value which joins the two pins of said connection selected in step (m) on said detailed grid; (p) assigning said calculated path to said connection selected in step (m); (g) 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 (l) 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 52

A circuit board wherein a plurality of connections are formed between specified pins according to the 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 to said data processing machine pertaining to grid model 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 coordinates 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 pass, and removing from said global grid the path assigned to said selected connection; (e) calculating said penalty function for each substantially I, L, Z and U-shaped path which joins the two pins of said selected 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 selected 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) assuming, for each connection, a global swath comprising those global cells through which said connection has been globally routed; (l) beginning a detailed routing pass through said connections by defining said penalty function in terms of specified costs wherein said costs are non-negative, 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 selected in step (m), if said connection selected in step (m) has been routed previously on the detailed grid; (o) routing said removed connection selected in step (m) using a mazerouter procedure to calculate a path having a penalty function of smallest value which joins the two pins of said connection selected in step (m) on said detailed grid; (p) assigning said calculated path to said connection selected in step (m); (g) 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 (l) 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.