Routability Driven Analytical Placement for Mixed

Routability Driven Analytical Placement
for Mixed-Size Circuit Designs
Meng-Kai Hsu, Sheng Chou, Tzu-Hen Lin,
and Yao-Wen Chang
Electronics Engineering,
National Taiwan University
 Introduction
 Preliminaries
 Proposed algorithm
 Experimental results
 Conclusion
 mixed-size circuit designs which integrate a large number of
pre-designed macros (e.g., embedded memories, IP blocks)
and standard cells with very different sizes have become a
mainstream for modern circuit designs.
 Considering routability during placement is of particular
significance for modern mixed-size circuit designs with very
large-scale interconnections
 A new routability-driven analytical placement algorithm
 pin density
 the density of pins
 the routing directions of the pins
 routing overflow optimization
 A novel sigmoid function based overflow refinement method
 macro porosity consideration
 a new virtual macro expansion technique
 A routability-driven legalization and a detailed placement
technique are proposed
Analytical Placement Framework
 The circuit placement problem can be formulated as a
hypergraph  = (,) placement problem.
vertices  = {1, 2, ..., } represent blocks
hyperedges  = {1, 2, ..., } represent nets
 and  be the  and  coordinates of the center of block 
Two type blocks
 pre-placed blocks and movable blocks
Analytical Placement Framework
 We intend to determine the optimal positions of movable
blocks so that the target cost (e.g., wirelength) is minimized
and there is no overlap among blocks.
 The placement problem is usually solved in three steps:
 (1) global placement
 (2) legalization
 (3) detailed placement
 Generally, global placement has the most crucial impact on
the overall
Analytical Placement Framework
 the global placement problem can be formulated as a
constrained minimization problem as follows:
(x, y) is the wirelength function
 (x, y) is the potential function that is the total area of
movable blocks in bin 
  is the maximum allowable area of movable blocks
in bin 
Analytical Placement Framework
 Equation (1) can be solved by the quadratic penalty method,
implying that we solve a sequence of unconstrained
minimization problems of the form
 solve the unconstrained problem in Equation (2) by the
conjugate gradient (CG) method
Congestion Estimation
 The global routing problem is often solved with a grid graph
 After dividing the routing region into uniform and nonoverlapping regions called G-cells, each G-cell is denoted as a
node, and two adjacent G-cells are connected by a routing
 the capacity of a routing edge denotes the number of routing
tracks that are available for nets crossing the corresponding
Congestion Estimation
 Since the exact routing is unknown during placement,
routability is an abstract concept.
 In this paper, we adopt the L-shaped probabilistic routing
model since it is efficient and can produce sufficiently
accurate estimation for routing congestion
 To estimate the routing congestion, nets are first
decomposed into 2-pin nets by FLUTE
 then each 2-pin net is routed by upper-L and lower-L
patterns with 50% probability for each direction.
The proposed algorithm
 The proposed algorithm consists of three stages:
 routability-driven global placement with pin density control,
 routability-driven legalization with routing congestion
optimization, and
 routability-driven detailed placement
The proposed algorithm
Routability-Driven Global Placement
 three aspects:
 (1) pin density,
 (2) routing overflow optimization
 (3) macro porosity consideration
 There are two stages in the multilevel framework:
 (1) the coarsening stage, and
 first-choice (FC) clustering algorithm
 (2) the uncoarsening stage
 the placement problem in Equation (2) is solved from the coarsest level to
the finest level.
The proposed algorithm
Routability-Driven Global Placement
 Pin Density Control
The proposed algorithm
Routability-Driven Global Placement
 Pin Density Control
 To control the total number of pins in a G-cell
 formulate pin density penalties in the density constraints in Equation
(x, y) is the pin density in bin , which is the ratio between the
total number of pins in b and the total number of allowed pins in each
  is the total movable area for placement
 By subtracting the maximum potential of a bin  by its pin density
 pin density of a G-cell is the summation of pin densities on its
corresponding routing edges.
Routability Optimization
Congestion Removal
 congested region identification
 build a congestion map by using L-shaped probabilistic routing and
calculate the routing overflow of each bin.
 adaptive base potential modification
 If the overflow of a bin is smaller than the average, we slightly reduce
the base potential.
 On the contrary, if the overflow of a bin is larger than the average, we
reduce the base potential more aggressively
 Gaussian filtering
 nonlinear optimization
 optimize the objective in Equation (2) subject to the modified base
Routability Optimization
Overflow Refinement
 a nonlinear formulation based on L-shaped probabilistic
 decompose each multi-pin net into 2-pin nets by FLUTE
 Then, we optimize the overflow by solving a constrained
minimization problem of the form
 denotes the expected usage of routing edge 
 e denotes the routing capacity of the routing edge
Routability Optimization
Overflow Refinement
 In order to represent the equation of  in terms of block
positions, we first define a 0-1 logic function (, , ) as
 For a vertical edge from (, ) to (, e), its expected
usage is defined as:
 (1 (), 1 ()) and (2 (), 2 ()) are the coordinates of
the connected pins of a two-pin net 
Routability Optimization
Overflow Refinement
 Since the 0-1 logic function (, , ) is neither smooth nor
differentiable, we propose to use a sigmoid function to make
the function differentiable
 is a quite expensive operation in practice
 Therefore, we propose to use a quadratic sigmoid function in
our analytical framework:
 is the reciprocal of the G-cell size
Routability Optimization
Overflow Refinement
 With the quadratic sigmoid function, we can define the
smoothed 0-1 logic function as follows
 ˆ(− ) transforms the condition  <  while ˆ(− )
transforms the condition  < .
 quadratic penalty method
 overall nonlinear formulation:
Routability Optimization
Virtual Macro Expansion
 For modern mixed-size circuit designs, macro porosity
brings significant challenges for routability-driven placement
 the number of blocks placed near macros should be reduced
to improve the routability
 expand the original boundaries of macros during placement
virtually to reserve spaces near macros for global routing
 The expansion ratio is then defined as
 is the metal blockage ratio of a macro 
  is the fraction of whitespace
Routability-Driven Legalization
 removes all overlaps of a given global placement result
 Consider routing congestion of candidate positions for
legalizing cells
 minimum displacement
 with minimum congestion cost
Routability-Driven Detailed Placement
 Revise cell shifting and cell swapping
 (1) routability-driven cell matching
 find a minimum weighted matching of cells and placement locations
within a selected window
 The matching cost is evaluated as a weighted sum of total overflow
and wirelength:
 : total overflow
 is a user-specified parameter
 Incremental update cost
 (2) routability-driven cell swapping.
 selects  adjacent cells in a single placement row and enumerates all
possible permutations of these cells to find the minimum total
 This paper has presented a novel routability-driven analytical
placement framework for mixed-size circuit designs
 Experimental results have shown that our algorithm can
achieve the best average overflow and routed wirelength,
compared with the participating teams for the 2011 ACM
ISPD Routability-Driven Placement Contest.

similar documents