Vlsi Physical Design Automation: Lecture 5. Circuit Partitioning (iii) Spectral And Flow

EE382V Fall 2006

VLSI Physical Design Automation Lecture 5. Circuit Partitioning (III) Spectral and Flow Prof. David Pan [email protected] 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

1 b

c 3

4

3

d

a b = A c d

a 0 1 0 3

b 1 0 0 4

c 0 0 0 3

d 3 4 3 0

a b = D c d

a 4 0 0 0

b 0 5 0 0

c 0 0 3 0

d 0 0 0 10

D: degree matrix; A: adjacency matrix; D-A: Laplacian matrix Eigenvectors of D-A form the Laplacian spectrum of G

4

Eigenvalues and Eigenvectors x

A  a11 a12  ...  an1 an 2

If

Ax

 x1   a11 x1 + a12 x2 +  + a1n xn  a1n       =    ann  xn   an1 x1 + an 2 x2 +  + ann xn

    

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

xTAx

 a11  = (x1 , , xn ) a  n1 n =  ∑xi ai1,  i =1 =

∑x x a i

 a1n  x1           ann  xn   x1  n    ∑xi ain,      i =1  xn 

j ij

i, j

6

Basic Idea of Laplacian Spectrum Based Graph Partitioning ❁Given a bisection ( X, X’ ), define a partitioning vector

−1 = = x ( x1 , x2 , , xn ) s.t. xi  1

i ∈X 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)

T x Qx =

∑Q x x ij i

j

= xT Dx − xT Ax

∑d x = ∑d x =

=

2 i i

− ∑Aij xi xj

2 i i

−

∑( x

( i , j ) ∈E

i

∑2 a x x

( i , j )∈E

− xj )2

= 4 * C(X, X’)

ij i

…. j

x1 x2 x3

xn

squared wirelength 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. T (i) x Qx =

∑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] n

n

2n nodes 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