APlace: A High Quality, Large-Scale Analytical Placer
Sep 05, 2005 |
Analytical placement methods
have received increased attention from both academia and industry in recent
years. We propose and implement APlace, a general analytical placement
framework, which has high solution quality and strong extensibility.
APlace regards global placement as a constrained nonlinear optimization problem:
APlace divides the placement area into uniform grids, and seek to minimize
certain placement objectives such as total half-perimeter wirelength (HPWL)
under the constraint that total module area in every grid is equalized. APlace
applies smooth approximations of placement objectives and density control
function and solves the constrained optimization problem using the simple
Quadratic Penalty method and a Conjugate Gradient solver.
The general APlace framework has been extended to address a variety of placement
tasks across many aspects of physical implementation, such as mixed-size
placement, timing-driven placement, power-aware placement, voltage-drop-aware
placement and I/O-core co-placement, and is shown to be competitive in a wide
variety of contexts.
Recently, APlace won the First Place at ISPD05 Placement Contest.
We have published six conference papers at ISPD04, ICCAD04, ISPD05, DAC05,
ICCD05 and ICCAD05 and a journal version at TCAD05.
II. Features and Known Limitations
- Regards global placement as a constrained nonlinear optimization problem,
applies smooth approximation of placement objectives and optimizes using
Quadratic Penalty method and a Conjugate Gradient solver
- High solution quality in terms of half-perimenter wirelength: APlace is
among the best state-of-the art academic placement tools.
- Strong extensibility: APlace has been extended to address a variety of
placement tasks and is shown to be competitive in a wide variety of contexts.
Able to place circuits with 2.1 million components on a Linux machine with
1.6GHz CPU and 2G memory in 40 hours.
- Able to handle circuits with fixed
and movable macro blocks, blockages in the placement region, and large amount
- Able to place cells and I/O pads for peripheral and
area-array I/O designs simultaneously. Connectivity information between movable cells and
fixed I/O pads at the placement boundary is not necessary.
- Slower than Capo, FastPlace, mPL5 and FengShui. APlace is on average
3X slower than Capo on IBM ISPD05 circuits.
- Cannot handle irregular row-spacing (eg. Bookshelf Format
MCNC benchmarks released by Dr. Patrick Madden).
- Does not perform well on PEKO circuits.
III. Performance Results
Click here to try APlace online.
- A. B. Kahng, and Q. Wang, "Implementation
and Extensibility of an Analytic Placer", Proc. ACM/IEEE Intl. Symp.
Physical Design, April 2004, pp. 18-25.
A. B. Kahng, and Q. Wang, "An
Analytic Placer for Mixed-Size Placement and Timing-Driven Placement",
Proc. ACM/IEEE Intl. Conf. Computer-Aided Design, Nov. 2004, pp. 565-572.
A. B. Kahng, and Q. Wang, "Implementation
and Extensibility of an Analytic Placer", IEEE Transactions on
Computer-Aided Design 24(5) (2005), pp. 734-747.
A. B. Kahng, S. Reda and Q. Wang, "APlace:
A General Analytic Placement Framework", Proc. ACM/IEEE Intl. Symp.
Physical Design, April 2005, pp. 233-235. (Short Invited,
1st Place of ISPD05 Placement Contest)
Y.-S. Cheon, P.-H. Ho, A. B. Kahng, S. Reda and Q. Wang, "Power-Aware
Placement", Proc. Design Automation Conference, 2005, pp. 795-800.
A. B. Kahng, B. Liu and Q. Wang, "Supply
Voltage Degradation Aware Placement", Proc. ACM/IEEE Intl. Conf. on
Computer Design, October 2005, to appear.
A. B. Kahng, S. Reda and Q. Wang, "Architecture
and Details of a High Quality, Large-Scale Analytical Placer", Proc.
ACM/IEEE Intl. Conf. on Computer-Aided Design, November 2005,to appear. (Best