An Effective Routability-Driven Placer by Iterative Cell Movement

Ripple: An Effective
Routability-Driven Placer by
Iterative Cell Movement
Xu He, Tao Huang, Linfu Xiao, Haitong Tian, Guxin
Cui and Evangeline F.Y. Young
Department of Computer Science and Engineering,
The Chinese University of Hong Kong
ICCAD 2011
Problem formulation
Overall flow
Routing congestion estimation
Cell movement and detail placement
Experimental results
• Routability has become an important issue
in physical design.
– Placement greatly affects it.
• Traditional placement algorithms majorly
focuses on HPWL minimization.
– Shorter wirelength generally has better
routability, but not always.
• Large macros occupy metal layers and
hence forming routing blockages.
– Need to handle it.
The proposed placer
• The proposed routability driven placer,
Ripple, uses lower-upper-bound
framework during global placement.
– Based on simPL, a force-directed quadratic
placer which uses conjugate gradient (CG)
• A flat placer whose congestion estimation
will always be done after a rough
legalization step.
– Much more accurate.
Review: Conjugate Gradient
• If we want to solve  = 
– Let   =
solution .
−  T  that has the same
• min   ↔  ( − )
– Iteratively solve  =  − 
– +1 =  −

– +1 =  + +1 +1 ℎ +1 =


The proposed placer (cont.)
• Global placement of this placer contains
– Lower bound computation is to reduce routing
demand and wirelength.
• “Produces an illegal placement that underestimates
the final result – through linear system solver.” -simPL
– Upper bound computation is to distribute
congestion evenly.
• “Produce an almost-legal placement that
overestimates the final result – through rough
legalization.” -- simPL
• This work mainly focuses on this phase.
• Applying the proposed cell inflation in alternate
directions iteratively, the total congestion can be
reduced more effectively.
• Using net-based movement to calculate the target
positions for the cells by considering congestion
and the movement of a whole net directly.
• Not only minimizing HPWL but also consider the
displacement between the cells and their target
positions calculated to optimize congestion.
Problem formulation
• Given:
– A netlist N = (E,V ) with nets E and nodes V,
global routing tile size with available number of
routing resource.
• Objective:
– Decide positions of movable cells so that the
total overflow and wirelength are minimized.
• Evaluation:
– Using specific router with limited runtime.
– Major objective is to minimize the total overflow
determined by the router.
Overall flow
Initial placement and objective
• Entirely ignores cell areas and
overlaps, so as to minimize a
quadratic approximation of total
interconnect length.
• Solve the quadratic optimization
Routing congestion estimation
• Using HPWL will underestimate the
Routing congestion estimation (cont.)
• Multi-pin nets are first decomposed into two-pin
nets using the RMST method.
• Consider a two-pin net p connecting from (1 , 1 )
to (2 , 2 ), the horizontal wirelength is the width of
the bounding box. The DemandH due to p for
each tile overlapping with the bounding box of p is
computed as follows:
Routing congestion estimation (cont.)
• BoundingBoxArea is the bounding box area of this
• ConnInterArea is the intersection area between
the tile and the bounding box.
• WireSpaceH is the area of one unit of wire in the
horizontal direction.
• WireAreaH is the horizontal wire area of this net
which can be obtained by multiplying the
horizontal wirelength by WireSpaceH.
• TotalTracksH is the total number of horizontal
tracks (counting all metal layers) in the tile.
Routing congestion estimation (cont.)
• The supply of a tile in the horizontal direction
SupplyH can be computed as follows:
• Btile is the set of routing blockages overlapped
with the tile.
• BInterArea(i) is the intersection area between
routing blockage i and the tile.
• BRatioH(i) is the ratio of horizontal tracks being
occupied by the routing blockage i.
• BlockageH is the routing resource occupied by all
the routing blockages overlapped with the tile in
the horizontal direction.
Routing congestion estimation (cont.)
• The level of horizontal routing congestion
CongestionH of the tile can then be
computed by:
• dw (demand weight, dw > 0) is a variable
defined to control the number of tiles to be
• The less the value of CongestionH, the
more congested a tile is. If CongestionH <
0, the tile is said to be over congested.
Cell movement
• Two methods
– Cell inflation and spreading.
– Net-based movement.
• Three issues of inflation and spreading.
– Where should cell inflation be used?
– What is the inflation ratio?
– How to spread the cells?
• This work considers all of them as a whole
for the horizontal and vertical directions
Cell inflation
• If almost all the tiles are congested,
inflating the cells in all the tiles is
helpless to distribute the routing
demand evenly.
– Reduce the variable dw to control the
number of tiles to be inflated.
Cell inflation (cont.)
• Three levels of inflation ratio.
– where 1 = 0.3, 1 = 0.4, 1 = 0.6, 2 =
0, 2 = −0.2, 2 = −0.4
Cell inflation (cont.)
• The total inflation area of the cells for each
cell inflation process is also limited.
• Sort all CongestionH < 0 tiles and the cells
in the most congested tiles are inflated first
until the total inflation area reaches .
–  is set to 35% of the total available area.
Cell spreading
• After cell inflation, we will spread the cells
in those tiles whose cell density is larger
than a certain threshold  ℎ 0 ≤  ≤ 1.
• Modified rough legalization for reducing
Net-based movement
• The proposed cell movement method does
not consider how one whole net should be
moved according to the congestion.
• Net-based movement
– Compute a target position for each cell and will
consider the movement of a net as a whole.
• Two steps
– Move the nets’ bounding boxes away from the
congested regions, since it is the nets instead
of the cells using the routing resource directly.
– Move the cells on the nets according to the
target positions of the nets.
Calculate average congestion
and position of bounding box
center of a net.
Get the desired bounding box
center of a net.
Obtain the min-displacement
from the bounding box center.
A simple example
Congestion driven detail placement
• First step: global placement oriented.
– Swap cells with the swapping window around
the global placement position.
– Finish when HPWL is not improved after a
number of swapping iterations.
• Second step: net-based movement
– Swapping cells with the swapping window
around the position calculated by net-based
– Finish when several swapping iterations
without congestion improvement.
Experimental results
• Environments
– C++ with g++ 4.1.2
– Linux OS with Intel Core 2 Duo 2.8GHz
and 4GB RAM
– Single threaded
• Use ISPD 2011 benchmarks
– CGrip router with the same configuration
for global routing.
Benchmark statistics
Overflow evaluation
CGrip and routing settings
• CGrip is an integer programming
based global router.
• Setting of ISPD 2011 benchmark
Trend over iterations
Runtime profiling
• In terms of total runtime of the global
Congestion estimation: 42.9%.
Conjugate gradient optimization: 28.5%.
Rough legalization: 25.4%.
Cell inflation: 0.4%.
Net-based movement: 2.7%.
Runtime profiling (cont.)
Overflow comparison – detailed placement
Overflow comparisons - placers
• Propose a routability-driven placement
algorithm based on the lower-upper-bound
• Two method to reduce congestions.
– Cell inflation and net-based movement.
• Combined detail placement approach.
– HPWL and congestion driven.
• Achieve the lowest average overflow than
those in the ISPD 2011 contest.

similar documents