Transcript Document

Quadratic VLSI Placement
Manolis Pantelias
General

Various types of VLSI placement






Simulated-Annealing
Quadratic or Force-Directed
Min-Cut
Nonlinear Programming
Mix of the above
Quadratic placers

Try to minimize a quadratic wirelength objective function



Indirect measure of the wirelength but can be minimized
quite efficiently
Results in a large amount of overlap among cells
Additional techniques needed
Proud
R. S. Tsay, E. Kuh and
C. P. Hsu, “Proud: A
Sea-of-Gates
Placement Algorithm”
Objective function

Don’t minimize the wirelength but the squared wirelength:

cij between module i and module j could be the number of nets
connecting the two modules
Connectivity matrix C = [cij]
B=D–C
D is a diagonal matrix with:




Only the one-dimensional problem needs to be considered because
of the symmetry between x and y
Electric Network Analogy




Objective function xTBx can be interpreted as the power
dissipation of an n-node linear resistive network
Vector x corresponds to the voltage vector
x = [x1 x2]T, x1 is of dimension m and is to be determined, x2 is
due to the fixed I/O pads
B contains the conductance of the nodes

–bij is the conductance between node i and node j
Electric Network Analogy (Cont’d)

Placement problem is equivalent to
that of choosing voltage vector for
which power is a minimum



Solve for Ax1 = b


B11x1 + B12x2 = 0
B21x1 + B22x2 = i2
Where A = B11, b = - B12x2
Solved with iterating method
(successive over-relaxation or SOR)
Placement and Partitioning






How to avoid module overlap?
Solution: Iterative partitioning in a hierarchical way
Add module areas from left to right until roughly half of the total
area, that defines partition-line
Make modules to the right of partition-line fixed, modules to the
left of partition-line movable
Project fixed modules to center-line
Perform global placement in the left-plane (of center-line)
Placement and Partitioning (Cont’d)





Make all modules in the left-plane fixed,
project to the center line
Make modules to the right of cut-line
movables
Perform global placement in the right-plane
Proceed with horizontal cuts on each half
Continue until each block contains one and
only module
BGS Iteration





For a given hierarchy perform the previous partitioning more than
once
Assume a vertical cut
y1 splits into y1a, y1b for each half
y1a* and y1b* are perturbed solution from y1a and y1b because of the
partitioning process
2-5 iterations give very good results at each hierarchy
Problems


A bad decision at a higher level affects
the placement results of lower levels
Difficult to overcome a bad partitioning
of a higher level

Backtracking?
KraftWerk
Hans Eisenmann and F.
Johannes,
“Generic Global Placement and
Floorplanning”
Force Directed Approach


Transform the placement problem to the
classical mechanics problem of a system of
objects attached to springs.
Analogies:




Module (Block/Cell/Gate) = Object
Net = Spring
Net weight = Spring constant.
Optimal placement = Equilibrium configuration
An Example
Resultant
Force
Force Calculation


Hooke’s Law:
 Force = Spring Constant x Distance
Can consider forces in x- and y-direction separately:
Distance d ij  ( x j  xi ) 2  ( y j  yi ) 2
Net Cost cij
F  cij ( x j  xi ) 2  ( y j  yi ) 2
Fx
Fx  cij ( x j  xi )
Fy  cij ( y j  yi )
(xi, yi)
(xj, yj)
F
Fy
Problem Formulation



Equilibrium: Sj cij (xj - xi) = 0 for all module i.
However, trivial solution: xj = xi for all i, j.
Everything placed on the same position!
Need to have some way to avoid
overlapping.


Have connections to fixed I/O pins on the
boundary of the placement region.
Push cells away from dense region to sparse
region
Kraftwerk Approach
Iteratively solve the quadratic formulation:
Min
f ( p)  12 pT Cp  d T p  const

 Cp  d  0
// equivalent to spring force
// equilibrium
Spread cells by additional forces:

Cp  d  f  0

Density-based force proposed

Push cells away from dense region to sparse region
 
k
r  r'
f ( x, y ) 
D
(
x
'
,
y
'
)
  2 dx' dy '






2
r  r'


where r  ( x, y ) and r '  ( x' , y ' )




The force exerted on a cell by another cell is repelling and
proportional to the inverse of their distance.
The force exerted on a cell by a place is attracting and
proportional to the inverse of their distance
Some Details



Let fi be the additional force applied to cell i
The proportional constant k is chosen so that the
maximum of all fi is the same as the force of a net
with length K(W+H)
K is a user-defined parameter



K=0.2 for standard operation
K=1.0 for fast operation
Can be extended to handle timing, mixed block
placement and floorplanning, congestion, heatdriven placement, incremental changes, etc.
Some Potential Problems of Kraftwerk

Convergence is difficult to control

Large K  oscillation

Small K  slow convergence



Example:
Layout of a multiplier
Density-based force is expensive
to compute
 
k  
r  r'
f ( x, y ) 
D( x' , y ' )   2 dx' dy '


2    
r  r'
FastPlace
Natarajan Viswanathan and Chris Chu,
“FastPlace: Efficient Analytical
Placement using Cell Shifting, Iterative
Local Refinement and a Hybrid Net
Model”
FastPlace Approach

Framework:
repeat
Solve the convex quadratic program 
Reduce wirelength by iterative heuristic 
Spread the cells 
until the cells are evenly distributed 

Special features of FastPlace:



Cell Shifting

Easy-to-compute technique 

Enable fast convergence 
Hybrid Net Model

Speed up solving of convex QP 
Iterative Local Refinement

Minimize wirelength based on linear objective 
Cell Shifting
1. Shifting of bin boundary
Uniform Bin Structure
Non-uniform Bin Structure
2. Shifting of cells linearly within each bin

Apply to all rows and all columns independently
Cell Shifting – Animation …
Bin
i
Bin
i
Bin
i+1
Bin
i+1
k
j
Ui
l
OBi-1
OBi
OBi+1
Ui+1
OBi-1 OBi OBi+1
k
j
l
NBi
NBi
Pseudo pin and Pseudo net
Pseudo pin


Need to add forces to
prevent cells from
collapsing back
Done by adding pseudo
pins and pseudo nets

Only diagonal and linear
terms of the quadratic
system need to be
updated

Takes a single pass of
O(n) time to regenerate
matrix Q (which is
common for both x and
y problems)
Pseudo
pin
Pseudo
net
Pseudo net
Additional
Force
Target Position
Original Position
Iterative Local Refinement






Iteratively go through all the cells one by one
For each cell, consider moving it in four directions by a certain
distance
Compute a score for each direction based on

Half-perimeter wirelength (HPWL) reduction

Cell density at the source and destination regions
Move in the direction with highest positive score
(Do not move if no positive score)
V
Distance moved (H or V) is
decreasing over iterations
H
H
Detailed placement is handled
by the same heuristic
V
Clique, Star and Hybrid Net Models




Runtime is proportional to # of non-zero entries in Q
Each non-zero entry in Q corresponds to one 2-pin net
Traditionally, placers model each multi-pin net by a clique
Hybrid Net Model is a mix of Clique and Star Models
Star Node
Clique Model
Star Model
# pins
2
3
4
5
6
…
Net Model
Clique
Clique
Star
Star
Star
…
Hybrid Model
Equivalence of Clique and Star Models


Lemma: By setting the net weights appropriately,
clique and star net models are equivalent.
Proof: When star node is at equilibrium position,
total forces on each cell are the same for
clique and star net models.
Star Node
Weight = γW
Clique Model
Weight = γ kW
for a k-pin net
Star Model
Comparison

FastPlace is fast compared to
Kraftwerk (based on published data)

20-25x faster



With cell shifting technique can converge in
around 20 iterations.
KraftWerk may need hundreds of iterations to
converge.
10% better in wirelength

hybrid net model