Paper Info
Title
Multilevel generalized force-directed method for circuit placement
Abstract
Automatic circuit placement has received renewed interest recently given the rapid increase of circuit complexity, increase of interconnect delay, and potential sub-optimality of existing placement algorithms [13]. In this paper we present a generalized force-directed algorithm embedded in mPL2's [12] multilevel framework. Our new algorithm, named mPL5, produces the shortest wirelength among all published placers with very competitive runtime on the IBM circuits used in [29]. The new contributions and enhancements are: (1) We develop a new analytical placement algorithm using a density constrained minimization formulation which can be viewed as a generalization of the force-directed method in [16]; (2) We analyze and identify the advantages of our new algorithm over the force-directed method; (3) We successfully incorporate the generalized force-directed algorithm into a multilevel framework which significantly improves wirelength and speed. Compared to Capo9.0, our algorithm mPL5 produces 8% shorter wirelength and is 2X faster. Compared to Dragon3.01, mPL5 has 3% shorter wirelength and is 12X faster. Compared to Fengshui5.0, it has 5% shorter wirelength and is 2X faster. Compared to the ultra-fast placement algorithm: FastPlace, mPL5 produces 8% shorter wirelength but is 6X slower. A fast mode of mPL5 (mPL5-fast) can produce 1% shorter wirelength than Fast-Place1.0 and is only 2X slower. Moreover, mPL5-fast has demonstrated better scalability than FastPlace1.0.
Year
DOI
Venue
2005
10.1145/1055137.1055177
ISPD
Keywords
Field
DocType
force-directed method,multilevel,standard cell placement
Mathematical optimization,IBM,Generalized forces,Circuit complexity,Computer science,Parallel computing,Minification,Interconnection,Electronic circuit,Scalability
Conference
ISBN
Citations 
PageRank 
1-59593-021-3
80
4.54
References 
Authors
16
3
Name
Order
Citations
PageRank
Tony F. Chan18733659.77
Jason Cong27069515.06
Kenton Sze323511.93