Method and apparatus for minimization of process defects while routing
First Claim
1. A method for optimizing the routing of nets in an integrated circuit device, said method comprising:
- a. dividing an integrated circuit design with lines in a first direction and lines in a second direction, wherein said first direction is substantially orthogonal to said second direction;
b. forming a routing graph with vertices corresponding to locations where lines in said first direction and lines in said second direction cross and with edges connecting the vertices;
c. for each of a plurality of the edges in said routing graph, computing an individual edge occupancy value, wherein the individual edge occupancy value is computed by determining at least one of a probability of a wire passing through said edge and a number of actual wires passing through said edge;
d. for an edge in said plurality of edges, computing a penalty value as a function of the individual edge occupancy value of a different edge; and
e. routing a net as a function of said penalty value.
10 Assignments
0 Petitions
Accused Products
Abstract
A method for optimizing the routing of nets in an integrated circuit device, said method comprising the steps of dividing an integrated circuit design with lines in a first direction and lines in a second direction, wherein said first direction is substantially orthogonal to said second direction, forming a routing graph with vertices corresponding to locations where lines in said first direction and lines in said second direction cross and edges connect vertices, for each edge in a plurality of edges in said routing graph, computing an individual edge occupancy value, for an edge in said plurality of edges, computing a penalty value as a function of the individual edge occupancy value of a different edge, and routing a net as a function of said penalty value.
-
Citations
31 Claims
-
1. A method for optimizing the routing of nets in an integrated circuit device, said method comprising:
-
a. dividing an integrated circuit design with lines in a first direction and lines in a second direction, wherein said first direction is substantially orthogonal to said second direction;
b. forming a routing graph with vertices corresponding to locations where lines in said first direction and lines in said second direction cross and with edges connecting the vertices;
c. for each of a plurality of the edges in said routing graph, computing an individual edge occupancy value, wherein the individual edge occupancy value is computed by determining at least one of a probability of a wire passing through said edge and a number of actual wires passing through said edge;
d. for an edge in said plurality of edges, computing a penalty value as a function of the individual edge occupancy value of a different edge; and
e. routing a net as a function of said penalty value. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9)
-
-
10. A method for distributing wires between layers in an integrated circuit design, said method comprising:
-
a. for a particular half-channel, marking grid lines in a first direction containing beginnings or ends of wires;
b. dividing said half-channel into strips based on the markings made in step a;
c. forming a routing graph that includes two vertices for each strip, wherein each of the two vertices corresponds to a different one of plural routing layers;
d. computing a capacity value for an edge between the two vertices corresponding to one of the strips; and
e. routing a net on said plural routing layers as a function of the capacity value. - View Dependent Claims (11, 12, 13, 14, 15)
-
-
16. An apparatus for optimizing the routing of nets in an integrated circuit device, said apparatus comprising:
-
a. means for dividing an integrated circuit design with lines in a first direction and lines in a second direction, wherein said first direction is substantially orthogonal to said second direction;
b. means for forming a routing graph with vertices corresponding to locations where lines in said first direction and lines in said second direction cross and with edges connecting the vertices;
c. means for, for each of a plurality of the edges in said routing graph, computing an individual edge occupancy value, wherein the individual edge occupancy value is computed by determining at least one of a probability of a wire passing through said edge and a number of actual wires passing through said edge;
d. means for, for an edge in said plurality of edges, computing a penalty value as a function of the individual edge occupancy value of a different edge; and
e. means for routing a net as a function of said penalty value. - View Dependent Claims (17, 18, 19, 20, 21, 22, 23, 24)
-
-
25. An apparatus for distributing wires between layers in an integrated circuit design, said apparatus comprising:
-
a. for a particular half-channel, means for marking grid lines in a first direction containing beginnings or ends of wires;
b. means for dividing said half-channel into strips based on the markings made by means a;
c. means for forming a routing graph that includes two vertices for each strip, wherein each of the two vertices corresponds to a different one of plural routing layers;
d. means for computing a capacity value for an edge between the two vertices corresponding to one of the strips; and
e. means for routing a net on said plural routing layers as a function of the capacity value. - View Dependent Claims (26, 27, 28, 29, 30)
-
-
31. A computer storage device with instructions thereon for optimizing the routing of nets in an integrated circuit device, said storage device comprising:
-
a. a computer encoded instruction for dividing an integrated circuit design with lines in a first direction and lines in a second direction, wherein said first direction is substantially orthogonal to said second direction;
b. a computer encoded instruction for forming a routing graph with vertices corresponding to locations where lines in said first direction and lines in said second direction cross and with edges connecting the vertices;
c. a computer encoded instruction for, for each of a plurality of the edges in said routing graph, computing an individual edge occupancy value, wherein the individual edge occupancy value is computed by determining at least one of a probability of a wire passing through said edge and a number of actual wires passing through said edge;
d. a computer encoded instruction for, for an edge in said plurality of edges, computing a penalty value as a function of the individual edge occupancy value of a different edge; and
e. a computer encoded instruction for routing a net as a function of said penalty value.
-
Specification