Floorplan evaluation, global routing, and buffer insertion for integrated circuits
View Patent ↗A method and system for evaluating a floorplan and for defining a global buffered routing for an integrated circuit including constructing a graphical representation of the integrated circuit floorplan, including wire capacity and buffer capacity; formulating an integer linear program from said graphical representation; finding a solution to said integer linear program.
1. A method for evaluating a floorplan and for defining a global buffered routing for an integrated circuit, the method comprising the steps of:
constructing a tile graph from the integrated circuit (IC) floorplan, including wire capacity and buffer capacities;
constructing a gadget graph from said tile graph such that feasible buffered routings of every net are in one-to-one correspondence to simple paths between a net source and a net sink in said gadget graph;
formulating an integer linear program from said gadget graph; and
finding a solution to said integer linear program.
2. The method recited in claim 1 , wherein
said tile graph comprises a tile graph G=(V, E, b, w), b→N, W:E→N, where,
V, a set of tiles v that represents the IC floorplan;
E, a set of two-dimensional edges between any two of said tiles vεV that are contiguous;
b(v), a set of buffer capacities, each of said buffer capacities being a number of buffer sites located in each of said tiles vεV;
w(e), a set of wire capacities, each of said wire capacities being a number of wire routing channels across each of said edges eεE; and
a netlist set N of nets N i such that N={N 1 , N 2 , . . . , N k } to be included in the floorplan, each of said nets N i specified by sets of source tiles S i εV, said source tiles S i being tiles v to which at least one net sources s i may be assigned and by sets of sink tiles T i εV, said sink tiles T i being tiles v to which at least one net sink t i may be assigned.
3. The method recited in claim 2 , further comprising:
formulating a floorplan evaluation problem from said tile graph G, said floorplan evaluation problem including
a statement of what is given, said given statement including
said tile graph G;
said netlist N;
a wireload upper-bound of U>0;
a buffer congestion upper-bound of μ o # 1; and
a wire congestion upper-bound of v 0 # 1; and
a statement of what is to be found, said find statement including
feasible buffered routings (P i , B i ), among a set R i of all feasible buffered routings (P i , B i ), for each of said nets N i , each of said feasible buffered routings (P i , B i ) including
a path P i =(v 0 , v 1 , . . . , v li ) in said tile graph C and a set of buffers B i ⊂ {v 0 , . . . , v li } such that
tile v 0 εS i ;
tile v li εT i ;
buffer capacity b(v i )∃1 for every tile v i εB i ;
a length along said path P i between tile v 0 and a first buffer in B i has at most said wireload upper-bound U;
a length between consecutive buffers in B i has at most said wireload upper-bound U; and
a length between a last buffer in B i and tile v li has at most said wireload upper-bound U; and wherein each of said feasible buffered routings (P i , B i ) has a relative buffer congestion of μ# μ 0 , wherein said relative buffer congestion
μ
=
max
v
∈
V
{
i
:
v
∈
B
i
}
b
(
v
)
;
has a relative wire congestion of v# v 0 , wherein said relative wire congestion
v
=
max
e
∈
E
{
i
:
e
∈
P
i
}
w
(
e
)
;
and minimizes a total wire and buffer area.
4. The method recited in claim 3 , wherein
said a gadget graph comprises a gadget graph H, said gadget graph H being constructed from said tile graph G and includes
a vertex set V(H)={s i , t i |1# i# k}∪{v j |vεV(G), 1# j# U }; and
a directed arc set E(H) including
directed arc set E src ={(s i , v U )|vεS i , 1# i# k};
directed arc set E sink ={(v j , t i ) vεT i , 0# j# U, 1# i k};
directed arc set E u, v ={(u j-1 , v j ), (v j-1 , u j )|1# j# U}, and
directed arc set E v ={(v j , v U )|1# j# U }, such that
E
(
H
)
=
E
src
⋃
E
sink
⋃
(
⋃
(
u
,
v
)
∈
E
(
G
)
E
u
,
v
)
⋃
(
⋃
v
∈
V
(
G
)
E
v
)
.
5. The method recited in claim 4 , wherein
said formulating said integer linear program from said gadget graph includes
denoting the set of all simple paths p from said at least one net source s i , to said at least one net sink t i , as set P i ; and
formulating said floorplan evaluation problem from said gadget graph as said integer linear program
min
∑
p
=
P
(
α
∑
v
∈
V
(
G
)
p
⋂
E
v
+
β
∑
(
u
,
v
)
∈
E
(
G
)
p
⋂
E
u
,
v
)
x
p
,
said integer linear program being subject to
∑
p
∈
P
p
⋂
E
v
x
p
≤
μ
0
b
(
v
)
,
v
∈
V
(
G
)
;
∑
p
∈
P
p
⋂
E
u
,
v
x
p
≤
v
0
w
(
u
,
v
)
,
(
u
,
v
)
∈
E
(
G
)
;
∑
x
p
=
1
,
p
∈
P
i
i
=
1
,
…
,
k
;
and
x
p
∈
{
0
,
1
}
,
p
∈
P
.
6. The method recited in claim 5 , wherein said finding said solution to said integer linear program includes
introducing an upper-bound D on said total wire and buffer area;
formulating a linear program (min λ), said linear program (min λ) being subject to
∑
p
=
P
(
α
∑
v
∈
V
(
G
)
p
⋂
E
v
+
β
∑
(
u
,
v
)
∈
E
(
G
)
p
⋂
E
u
,
v
)
x
p
≤
λ
D
;
∑
p
∈
P
p
⋂
E
v
x
p
≤
λ
μ
0
b
(
v
)
,
v
∈
V
(
G
)
;
∑
p
∈
P
p
⋂
E
u
,
v
x
p
≤
λ
v
0
w
(
u
,
v
)
,
(
u
,
v
)
∈
E
(
G
)
;
∑
x
p
=
1
,
p
∈
P
i
i
=
1
,
…
,
k
;
and
x
p
≥
0
,
p
∈
P
;
and
finding a minimum upper-bound D for which an optimum objective value for said linear program (min λ)λ*#1.
7. The method recited in claim 6 , wherein
said finding a minimum upper-bound D for which an optimum objective value for said linear program (min λ)λ*≦1 is performed by use of an algorithm, said algorithm simultaneously approximating said linear program (min λ) and a dual linear program
max
∑
i
=
1
k
l
i
,
said dual linear program being subject to
∑
v
∈
V
(
G
)
μ
0
b
(
v
)
y
v
+
∑
(
u
,
v
)
∈
E
(
G
)
v
0
w
(
u
,
v
)
z
u
,
v
+
D
u
=
1
;
∑
v
∈
V
(
G
)
p
⋂
E
v
(
y
v
+
α
u
)
+
∑
(
u
,
v
)
∈
E
(
G
)
p
⋂
E
u
,
v
(
z
u
,
v
+
β
u
)
≥
l
i
,
p
∈
P
i
;
y
v
≥
0
,
v
∈
V
(
G
)
;
and
z
e
≥
0
,
e
∈
E
(
G
)
.
8. The method recited in claim 7 , wherein
said algorithm finds a (1+ε 0 )-approximation with
O
(
1
ɛ
0
2
λ
*
k
log
n
)
shortest path calculations, using
ɛ
=
min
{
1
γ
,
1
γ
(
1
+
ɛ
0
-
1
)
,
1
4
(
1
-
(
1
1
+
e
0
)
1
6
)
}
and
∂
=
(
1
-
ɛ
′
n
+
m
)
1
ɛ
,
wherein
n is the number of vertices of tile graph G,
m is the number of said edges of tile graph G, and ε′:=ε(1+ε)(1+εγ).
9. The method recited in claim 1 , further comprising:
evaluating routing and buffer resources using said solution.
10. The method recited in claim 9 , wherein
said evaluating includes computing a tradeoff curve for a total routing area, a wire congestion, and a buffer congestion.
11. The method recited in claim 1 , further comprising:
defining at least one feasible buffered routing using said solution.
12. The method recited in claim 11 , wherein
said defining said at least one feasible buffered routing includes randomly choosing a path from among a plurality of paths yielded by said solution.
13. The method recited in claim 1 , wherein
said gadget graph includes a representation of a flexibility for assignment of pins in the floorplan.
14. The method of claim 1 , wherein
said gadget graph includes a representation of polarity constraints associated with inverting buffers.
15. The method recited in claim 1 , wherein
said gadget graph includes a representation of a plurality of buffer sizes.
16. The method recited in claim 1 , wherein
said gadget graph includes a representation of a plurality of wire sizes.
17. The method recited in claim 1 , wherein
said gadget graph includes a representation of delay constraints.
18. The method recited in claim 1 , wherein
said finding a solution to said integer linear program includes finding a solution for at least one net with a single source and a single sink.
19. The method recited in claim 1 , wherein
said finding a solution to said integer linear program includes finding a solution for at least one net with a single source and a plurality of sinks.
20. The method recited in claim 1 , wherein
said tile graph includes tiles of a plurality of sizes.
21. The method recited in claim 1 , wherein said tile graph includes a representation on constraints on a numbers of buffers in specified sets of tiles.
22. A computer-readable medium having computer-readable instructions for performing the method recited in claim 1 .
23. A method for evaluating a floorplan and for defining a global buffered routing for an integrated circuit, the method comprising the steps of:
constructing a tile graph from the integrated circuit floorplan, formulating a floorplan evaluation problem from said tile graph, and constructing a gadget graph from said tile graph such that feasible buffered routings of every net are in one-to-one correspondence to paths between net source and a net sink in said gadget graph;
formulating said floorplan evaluation problem as an integer linear program from said gadget graph; and
finding a solution to said integer linear program, including,
finding a solution to a fractional relaxation of said integer linear program, and
rounding said solution to said fractional relaxation to an integer solution using randomized rounding.
24. A computer-readable medium having computer-readable instructions for performing the method recited in claim 23 .