US6845495B2 — Multidirectional router

Claim 1

Independent Claim 122 words

A method for routing a multi -layered integrated circuit, comprising: receiving parameters for an integrated circuit having n layers, wherein n is at least two; constructing a routing graph for a level k of the n layers of the integrated circuit, the k level partitioned into k-level tiles, wherein at least one edge is provided to join a first tile and a second tile in the k level routing graph; calculating capacities of the at least one edge joining the first tile and the second tile, the edge at least one of regular and normal; adding occupancies based on previous level net routing (k+1) and calculating penalties of edges; and routing nets based on the routing graph, calculated capacities and added occupancies.

Claim 2

Independent Claim 122 words

A method for routing a multi -layered integrated circuit, comprising: receiving parameters for an integrated circuit having n layers, wherein n is at least two; constructing a routing graph for a level k of the n layers of the integrated circuit, the k level partitioned into k-level tiles, wherein at least one edge is provided to join a first tile and a second tile in the k level routing graph; calculating capacities of the at least one edge joining the first tile and the second tile, the edge at least one of regular and normal; adding occupancies based on previous level net routing (k+1) and calculating penalties of edges; and routing nets based on the routing graph, calculated capacities and added occupancies.

Claim 3

Dependent Claim 32 words

The method as described in claim 1 , wherein after routing nets, if k is more than zero, the constructing, calculating, adding and routing steps are repeated after subtracting one from k.

Claim 4

Dependent Claim 30 words

The method as described in claim 1 , wherein after routing nets, if k is equal to zero, the adding and routing steps are repeated after subtracting one from k.

Claim 5

Dependent Claim 23 words

The method as described in claim 1 , wherein after routing nets, if k is less than zero, legal net routing is obtained.

Claim 6

Dependent Claim 28 words

The method as described in claim 1 , wherein routing nets includes routing nets in a net routing area and routing open nets in all integrated circuit areas.

Claim 7

Dependent Claim 29 words

The method as described in claim 1 , wherein the parameters include at least one of netlist, grid lines slop, distance between neighboring grid lines, and wire blockage information.

Claim 8

Dependent Claim 20 words

The method as described in claim 6 , wherein the parameters include parameter information for n layers of the chip.

Claim 9

Dependent Claim 30 words

The method as described in claim 1 , wherein a tile is a square section, with one side of each tile of the layer directed along a layer grid line.

Claim 10

Dependent Claim 24 words

The method as described in claim 8 , wherein a tile is sized so that each tile side is approximately equal to one grid.

Claim 11

Dependent Claim 20 words

The method as described in claim 8 , wherein grid lines are positioned generally through a middle of a tile.

Claim 12

Dependent Claim 18 words

The method as described in claim 1 , wherein the routing graph includes a vertex including a tile.

Claim 13

Dependent Claim 38 words

The method as described in claim 1 , wherein capacity for a regular edge is equal to the height of a tile corresponding to the edge expressed in grids minus the number of grid covered by routing blockages.

Claim 14

Dependent Claim 26 words

The method as described in claim 1 , wherein capacity for a normal edge is half of the number of vias included in the corresponding tiles.

Claim 15

Dependent Claim 31 words

The method as described in claim 1 , wherein adding occupancies based on previous level net routing includes if pervious level net routing is not available, occupancies are set to zero.

Claim 16

Dependent Claim 30 words

The method as described in claim 1 , wherein the penalty for passing through an edge is a function of the quotient occupancy/capacity and of the length of the edge.

Claim 17

Dependent Claim 28 words

The method as described in claim 1 , wherein the penalty at least one of increases as a function of occupancy/capacity and increases as a function of length.

Claim 18

Dependent Claim 18 words

The method as described in claim 16 , wherein the penalty is computed as follows length•e occupancy/capacity +length.

Claim 19

Dependent Claim 32 words

The method as described in claim 1 , wherein routing nets includes arriving at a set of edges such that any two different pins of the net are connected by the set.

Claim 20

Dependent Claim 36 words

The method as described in claim 1 , wherein routing nets includes implementing a procedure to route nets, wherein the input of the procedure is a net, and the output is a routing of the net.

Claim 21

Dependent Claim 45 words

The method as described in claim 19 , wherein the procedure to route nets includes if an input net has two pins including a first pin and a second pin, a neighborhood of the first pin is grown until the neighborhood intersects the second pin.

Claim 22

Dependent Claim 22 words

The method as described in claim 20 , wherein a least-penalty path connecting the first pin and the second pin is chosen.

Claim 23

Dependent Claim 37 words

The method as described in claim 20 , wherein the procedure to route nets includes if an input net has three pins, the neighborhoods of all pins are grown until a vertex is reached in another pin.

Claim 24

Dependent Claim 31 words

The method as described in claim 22 , wherein if a vertex in the intersection of all neighborhoods is provided, a sum of penalties to all three pins from that vertex.

Claim 25

Dependent Claim 155 words

The method as described in claim 23 , wherein there is a vertex in the intersection of all neighborhoods, the sum of penalties of all three pins are found from that vertex such that a vertex P 0 for which that sum is minimal is found, and is denoted by Pen 0 , then, for each P i (i=1, 2, 3), the sum of penalties to other two pins is found from the pin P, and that sum is denoted by Pen i , so that if Pen 0 =min{Pen i , i=0, 1, 2, 3} then the net routing is the union of the three least-penalty paths from P 0 to all pins P 1 , P 2 and P 3 , if Pen 1 ==min{Pen i , i=0, 1, 2, 3} then the net routing is the union of the two paths from P 1 to pins P 2 and P 3 .

Claim 26

Dependent Claim 28 words

The method as described in claim 20 , wherein the procedure to route nets includes more than three pins, the net is partitioned into at least two subnets.

Claim 27

Dependent Claim 99 words

The method as described in claim 25 , wherein for each pin, a center of gravity is calculated and then the pins are sorted in ascending order of abscissae of the center of gravity, such as let {x 1 , . . . , x n } be the ordering set of abscissae, X m is found such that X m+1 −X m =max{x i+1 −X i , i=1, 2, . . . n−1}, the point X m divides net into 2 subnets wherein the first subnet includes from m first pins and the second subnet contains another pins.

Claim 28

Dependent Claim 138 words

The method as described in claim 26 , wherein the net {P 1 , . . . ,P n } is portioned into 2 subnets {P 1 , . . . ,P m } and {P m+1 , . . . , P n }, the neighborhoods of the following set: m ∪P i i=1 and may be grown until a vertex from the following set is reached: n ∪p i i=m+1 the least-penalty path from one set to another is chosen and this path is included in the routing of the net, after which, a Procedure to Route Net is recursively applied to the subnets {P 1 , . . . ,P m ,} and {P m+1 , . . . , P n }, the procedure based on the number of pins included in the subnets.

Claim 29

Dependent Claim 18 words

The method as described in claim 1 , wherein routing nets includes implementing a procedure to grow neighborhoods.

Claim 30

Dependent Claim 100 words

The method as described in claim 28 , wherein the input of the procedure to grow neighborhoods is a set Sour of vertices of the routing graph, which may be referred to as a source set, and a set DestV, referred to as a destination set, the output of Procedure to Grow neighborhoods includes a number d=Dist(Sour,Dest), set M d (Sour), a vertex last ∈M d (Sour) ∩Dest and the array Prev[VertexNumber], where Prev[N(a)]=0 if a ∉M d (Sour)/Sour and Prev[N(a)]=b otherwise, where (b,a) is the last edge in a least-penalty path connecting the set Sour and the vertex a.

Claim 31

Independent Claim 140 words

A method for routing a multi-layered integrated circuit wherein arbitrary routing directions are supported on an arbitrary number of layers of the integrated circuit, comprising: receiving parameters for an integrated circuit having n layers, wherein n is at least two; constructing a routing graph for layers of the integrated circuit, the levels partitioned into tiles, wherein at least one edge is provided to join a first tile and a second tile in the routing graph, the tiles positioned generally corresponding to a layer grid line of the level; and routing based on the routing graph, wherein the plane of the layer is divided by parallel lines (y cosα i )+(x sinα i )=j d i , j=0, ±1, ±2, . . . , where α i is an inclination of the lines, d i is the distance between neighboring lines.

Claim 32

Independent Claim 140 words

A method for routing a multi-layered integrated circuit wherein arbitrary routing directions are supported on an arbitrary number of layers of the integrated circuit, comprising: receiving parameters for an integrated circuit having n layers, wherein n is at least two; constructing a routing graph for layers of the integrated circuit, the levels partitioned into tiles, wherein at least one edge is provided to join a first tile and a second tile in the routing graph, the tiles positioned generally corresponding to a layer grid line of the level; and routing based on the routing graph, wherein the plane of the layer is divided by parallel lines (y cosα i )+(x sinα i )=j d i , j=0, ±1, ±2, . . . , where α i is an inclination of the lines, d i is the distance between neighboring lines.

Annuity Stage	Window Opens	Payment Deadline	Surcharge Period Until	Estimated Fee	Status
3.5 Years (Year 4)	2008-01-18	2008-07-19	2009-01-18	$2000.00	Window Closed / Lapsed
7.5 Years (Year 8)	2012-01-18	2012-07-19	2013-01-18	$3760.00	Window Closed / Lapsed
11.5 Years (Year 12)	2016-01-18	2016-07-19	2017-01-18	$7700.00	Window Closed / Lapsed

Multidirectional router

Abstract

Inventors

Bibliographic Details

Claims Analysis

References Cited (Backward Citations)

USPTO Annuity & Maintenance Windows

Assigned Categories & Tags

Assign Category Tag