EE382V Fall 2006
VLSI Physical Design Automation
Lecture 5. Circuit Partitioning (III)
Spectral and Flow
Prof. David Pan
dpan@ece.utexas.edu
Office: ACES 5.434
10/18/08 1
Recap of what we have learned
❁KL Algorithm
❁FM algorithm
❁ Variation and Extension
❁Multilevel partition (hMetis)
❁Simulated Annealing
2
Partitioning Algorithms
❁Two elegant partition algorithms
❁ although not the fastest
❁Learn how to formulate the problem!
❁=> Key to VLSI CAD
(1) Spectral based partitioning algorithms
(2) Max-flow based partition algorithm
3
Spectral Based Partitioning Algorithms
a c a b c d a b c d
a 0 1 0 3 a 4 0 0 0
3 3
1 b 1 0 0 4 b 0 5 0 0
A = D =
c 0 0 0 3 c 0 0 3 0
b 4 d d 0 0 0 10
d 3 4 3 0
D: degree matrix; A: adjacency matrix; D-A: Laplacian matrix
Eigenvectors of D-A form the Laplacian spectrum of G
4
Eigenvalues and Eigenvectors
A x Ax
x1 a11 x1 + a12 x2 + + a1n xn
a11 a12 a1n
=
...
an1 an 2 ann xn an1 x1 + an 2 x2 + + ann xn
If Ax=λx
then λ is an eigenvalue of A
x is an eignevector of A w.r.t. λ
(note that Kx is also a eigenvector, for any constant K).
5
A Basic Property
a11 a1n x1
xTAx = (x1 , , xn )
a
n1 ann xn
x1
n n
= ∑xi ai1, ∑xi ain,
i =1 i =1
xn
= ∑x x a i j ij
i, j
6
Basic Idea of Laplacian Spectrum Based Graph
Partitioning
❁Given a bisection ( X, X’ ), define a partitioning vector
−1 i ∈X
= =
x ( x1 , x2 , , xn ) s.t. xi
1 i ∈ X'
clearly, x ⊥ 1, x ≠ 0 ( 1 = (1, 1, …, 1 ), 0 =(0, 0, …, 0))
❁For a partition vector x: ∑ (x
( i , j )∈ E
i − xj )2= 4 * C(X, X’)
❁Let S = {x | x ⊥ 1 and x ≠ 0}. Finding best partition vector x
such that the total edge cut C(X,X’) is minimum is relaxed to finding
x in S such that ∑ ( xi − xj )2 is minimum
( i , j )∈ E
❁Linear placement interpretation: ….
minimize total squared wirelength x1 x2 x3 xn
7
Property of Laplacian Matrix
(1) x Qx =
T
∑Q x x ij i j
= xT Dx − xT Ax
= ∑d x i i
2
− ∑Aij xi xj
….
= ∑d x 2
i i
− ∑2 a x x ij i j
( i , j )∈E x1 x2 x3 xn
= ∑( x i
− xj )2 squared wirelength
( i , j ) ∈E
= 4 * C(X, X’) If x is a partition vector
T
Therefore, we want to minimize
x Qx
8
Property of Laplacian Matrix (Cont’d)
( 2 ) Q is symmetric and semi-definite, i.e.
(i) x Qx =
T
∑Q x x
ij i j
≥0
(ii) all eigenvalues of Q are ≥0
( 3 ) The smallest eigenvalue of Q is 0
corresponding eigenvector of Q is x0= (1, 1, …, 1 )
(not interesting, all modules overlap and x0∉S )
( 4 ) According to Courant-Fischer minimax principle:
the 2nd smallest eigenvalue satisfies:
xT Qx
λ = min 2
x in | x |
S
9
Results on Spectral Based Graph Partitioning
❁ Min bisection cost c(x, x’) ≥ n⋅λ/4
❁ Min ratio-cut cost c(x,x’)/|x|⋅|x’| ≥ λ/n
❁ The second smallest eigenvalue gives the
best linear placement
❁ Compute the best bisection or ratio-cut
based on the second smallest
eigenvector
10
Computing the Eigenvector
❁Only need one eigenvector
(the second smallest one)
❁Q is symmetric and sparse
❁Use block Lanczos Algorithm
11
Interpreting the Eigenvector
❁Linear Ordering of modules
❁Try all splitting points, choose the best one
using bisection of ratio-cut metric
23 10 22 34 6 21 8
23 10 22 34 6 21 8
12
Experiments on Special Graphs
❁GBUI(2n, d, b) [Bui-Chaudhurl-Leighton 1987]
2n nodes
n n d-regular
min-bisection≈b
GBUI Results
Cluster 2
Value of Xi
Module i
Cluster 1
13
Some Applications of Laplacian Spectrum
❁Placement and floorplan
[Hall 1970]
[Otten 1982]
[Frankle-Karp 1986]
[Tsay-Kuh 1986]
❁Bisection lower bound and computation
[Donath-Hoffman 1973]
[Barnes 1982]
[Boppana 1987]
❁Ratio-cut lower bound and computation
[Hagen-Kahng 1991]
[Cong-Hagen-Kahng 1992]
14
