Iterative method for establishing connections and resulting product
First Claim
1. 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 to said data processing machine 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 through said connections which pass was initiated in step (c) and removing from said grid the path assigned to said selected 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 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 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.
1 Assignment
0 Petitions
Accused Products
Abstract
A method for establishing connections by automatically routing a plurality of paths between individual components using initially simple connection path shapes. The method is used to create an interconnection package with better use of wiring space. Each connection, in turn, is removed if previously routed, rerouted and evaluated according to specified penalty costs to minimize undesirable routing characteristics. This method is particularly advantageous in providing automatic path routing in directionally uncommitted planes for wiring highly integrated electric circuits, or the like.
331 Citations
41 Claims
-
1. 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 to said data processing machine 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 through said connections which pass was initiated in step (c) and removing from said grid the path assigned to said selected 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 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 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. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8)
-
-
9. 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 from substantially I, L, Z and U-shaped paths comprising the steps of:
-
(a) inputting information to said data processing machine 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 through said connections which pass was initiated in step (c) and removing from said grid the path assigned to said selected 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 selected connection and whose length does not exceed a specified value; (f) assigning a non-negative, numerical weight to each of said paths, the weight depending upon the value of the penalty function, and decreasing as the value of the penalty function increases; (g) selecting a path from among said paths, with a probability proportional to said weight; (h) assigning said selected path to said selected connection; (i) repeating steps (d) through (h) above until a desired number of connections have been routed thereby completing a pass; (j) generating data describing 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 corresponding to said data. - View Dependent Claims (10, 11)
-
-
12. A method of establishing a plurality of connections, using global routing techniques on a data processing machine, each connection join 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 to said data processing machine 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 through said connections which pass was initiated in step (c) and removing from said grid the path assigned to said connection; (e) using a mazerouter procedure to calculate a path having a penalty function of smallest value, which joins the two pins of said selected connection; (f) assigning said calculated path to said selected connection; (g) repeating steps (d) through (f) above until a desired number of connections have been routed thereby completing a pass; (h) generating data describing X, Y and Z coordinates of the paths assigned to said routed connections; (i) repeating steps (c) through (h) above until a desired number of passes have been completed; and (j) utilizing said data to establish said plurality of connections corresponding to said data. - View Dependent Claims (13, 14, 15, 16, 17)
-
-
18. 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 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 which pass was initiated in step (c); (e) determining if said selected connection 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; and (l) establishing said plurality of connections corresponding to said data. - View Dependent Claims (19, 20, 21, 22, 23, 24, 25)
-
-
26. 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 to said data processing machine pertaining to grid model specifications, such as blockage and via locations, 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 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 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 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 detailed 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. - View Dependent Claims (27, 28, 29)
-
-
30. 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 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 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 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 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 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 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. - View Dependent Claims (31, 32, 33)
- each 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;
-
34. 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 to said data processing machine 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 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 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 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 selected in step (m), if said connection selected in step (m) has been routed previously on the detailed grid; (o) routing said 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. - View Dependent Claims (35, 36, 37)
-
-
38. 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.
-
-
39. 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.
-
-
40. 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.
- 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;
-
41. 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.
-
Specification