Paper Info
Title
An Enhanced Multilevel Algorithm for Circuit Placement
Abstract
This paper presents several important enhancements to therecently published multilevel placement package mPL.The improvements include (i) unconstrained quadratic relaxation on small, noncontiguous subproblems at every level of the hierarchy; (ii) improved interpolation (declustering)based on techniques from algebraic multigrid (AMG), and(iii) iterated V-cycles with additional geometric informationfor aggregation in subsequent V-cycles. The enhanced version of mPL, named mPL2, improves the total wirelength result by about 12% compared to the original version. The attractive scalability properties of the mPL run time have beenlargely retained, and the overall run time remains very competitive. Compared to gordian-l-domino on uniform-cell-size IBM/ISPD98 benchmarks, a speed-up of well over8x on large circuits (驴 100,000 cells or nets) is obtainedalong with an average improvement in total wirelength ofabout 2%. Compared to Dragon [32] on the same benchmarks, a speed-up of about 5x is obtained at the cost ofabout 4% increased wirelength. On the recently publishedPEKO synthetic benchmarks, mPL2 generates surprisinglyhigh-quality placements - roughly 60% closer to the optimal than those produced by Capo 8.5 and Dragon - inrun time about twice as long as Capo's and about 1/10th of Dragon's.
Year
DOI
Venue
2003
10.1109/ICCAD.2003.30
Proceedings of the 2003 IEEE/ACM international conference on Computer-aided design
Keywords
Field
DocType
differential equations,interpolation,mems,algebraic multigrid,quadratic programming,quadratic program,dynamics,iterative methods,resonant frequency
Iterative method,Interpolation,Quadratic equation,Algorithm,Electronic engineering,Quadratic programming,Electronic circuit,Iterated function,Multigrid method,Mathematics,Scalability
Conference
ISBN
Citations 
PageRank 
1-58113-762-1
30
1.83
References 
Authors
17
5
Name
Order
Citations
PageRank
Tony F. Chan18733659.77
Jason Cong27069515.06
Tim Kong3553.49
Joseph R. Shinnerl442827.27
Kenton Sze523511.93