...

3A-5 - ASP-DAC

by user

on
Category:

geometry

0

views

Report

Comments

Transcript

3A-5 - ASP-DAC
A Theoretical Study on Wire Length
Estimation Algorithms for
Placement with Opaque Blocks
Tan Yan*, Shuting Li
Yasuhiro Takashima, Hiroshi Murata
The University of Kitakyushu
* Now with University of Illinois at Urbana-Champaign
Motivation
 “Opaque” blocks makes HPWL inexact
Because of IP blocks, analog blocks, memory module…
Lead to timing violation, unroutable nets…
T
t
HPWL
S
s
MWL
Motivation—cont’d
 Exact wire length estimation for Block Placement
the obstacle-avoiding shortest path length
 Time complexity: O(n)? O(n2)? O(nlogn)?...
 Time complexity is almost the same as HPWL!
Already proposed in Computational Geometry
 However
Not well-known in CAD community
Need interpretation to be applicable to CAD!
Our Contribution
We restate the results in
[P.J.de Rezende ’85] & [M.J.Atallah ’91]
Simplify the discussion (with Block Placement
notions)
CAD-oriented language
Tailor the theory to fit into Physical Design
background
Problem Formulation
Input:
Block location
Pin location (on block boundaries)
ABLR relations * (obtainable from Sequence
Pair, etc)
Output:
Rectilinear block-avoiding shortest path length
for every 2-pin net
 = Minimal Wire Length (MWL)
Assumption
 2-pin net
 s on S, t on T
S≠T
 S is left-to T
 ys ≤ yt
t
S
s
T
Locus
UR locus
RU
locus
v
Theorem 1
MWL = HPWL ↔ RU locus of s goes
below or through t
 Proof omitted
t T
RU
locus
RU
locus
t T
s
S
s
S
MWL > HPWL
MWL = HPWL
AB-region
Lemma 2
There exists an MWL routing inside the
AB-region
t
s
S
T
Horizontal Visibility Graph (HVG)
p
q
(a) The RU/RD edge and the
LU/LD edge (dotted edges)
p
q’s
LAB
t
T
s
S
p’s
RAB
q
(b) The corresponding routing of (a)
(c) The Horizontal Visibility Graph (HVG)
of net (s,t)
MWL = shortest path length
Lemma 4: There exists a path (s,t) on the visibility
graph that corresponds to an MWL routing.
t
T
s
S
 Only linear number of edges, but still captures
MWL!
Visibility graph of a placement
The overall flow
and so on …
Time complexity
M = # of blocks, N = # of nets
Building visibility graph:
O(M logM)
Estimating one net:
O(M)
Total:
O(M logM + NM)
Shortest path on channel graph takes O(NM2)
Use LUT to enhance the speed
b1
a1
S1
s1
s2
S2
A
Blocks in
between
B
b2
T2
t2
t1
T1
a2
 No path between two vertices? (a2b2)
 Need to judge whether RU locus above t ?
 How to find out A & B promptly?
Two lemmas:
 Lemma 5: Two vertices s and t on visibility graph. If
there is no path between them, then MWL = HPWL
 Lemma 6: If t is above s’s RU locus and there exists a
shortest path between them, then its length = HPWL.
d
a
b
c
 MWL(a,b) = HPWL
 ShortestPath(c,d)
= MWL (c,d) = HPWL
Theorem 3
The MWL of any two vertices on the
visibility graph can be obtained by shortest
path algorithm:
Shortest path exists, MWL = path length
Otherwise, MWL = HPWL
How it works
Lookup table
MWL = shortest
path length
No path!
MWL = HPWL
And so on…
Time complexity
Building LUT:
O(M2)
Estimating one net:
O(1)
Total:
O(M2+N)
Almost the same as HPWL!
Future works
Integration of routing congestion
Extension to handle multi-pin nets
Application to global router
Experimental study
Thank you!
Q&A
Proof of Theorem 1
MWL = HPWL ↔ RU locus of s goes
below or through t
RU
locus DL
locus
t T
s
S
(b) No HPWL routing exists if the
RU locus of s goes above t
s
S
t
t T
T
RU
locus
s
S
(c) The light gray blocks makes (d) If RU locus and DL locus intersect,
then there exists a HPWL routing
S below T
Proof of Lemma 2
There exists an MWL routing completely
inside AB-region
t
s
S
t’
s’
T
Proof of Lemma 4
There exists a path p from s to t on HVG
that corresponds to an MWL routing.
t
s
S
v
T
v
Proof of Lemma 6
 If t is above s’s RU locus and there exists a
shortest path between them, then its length =
HPWL.
t
w
u
s
t
v
(a) u’s RU locus goes below t
u
s
z
(b) u’s RU locus goes above t
Fly UP