SimPL: An Effective Placement Algorithm

SimPL: An Effective Placement Algorithm Myung-Chul Kim, Dong-Jin Lee and Igor L. Markov University of Michigan, Department of EECS, 2260 Hayward St., Ann Arbor, MI 48109-2121 {mckima, ejdjsy, imarkov}@eecs.umich.edu Abstract—We propose a self-contained, flat, force- directed algorithm for global placement that is simpler than existing placers and easier to integrate into timing- closure flows. It maintains lower-bound and upper-bound placements that converge to a final solution. The upper- bound placement is produced by a novel rough legaliza- tion algorithm. Our

placer SimPL outperforms mPL6, NTUPlace3, FastPlace3, APlace2 and Capo simultane- ously in runtime and solution quality, running 6.4 times faster than mPL6 and reducing wirelength by 2% on the ISPD 2005 benchmark suite. I. INTRODUCTION Global placement currently remains at the core of physical design and is a gating factor for downstream optimizations during timing closure [2]. Despite im- pressive improvements reported by researchers [15] and industry software in the last five years, state-of- the-art algorithms and tools for placement suffer sev- eral key shortcomings which are becoming more pro- nounced at recent technology nodes. These shortcom- ings fall into four categories: (i) speed, (ii) solution quality, (iii) simplicity and integration with other op- timizations, (iv) support for multithreaded execution. We propose the SimPL algorithm that simultaneously improves results in the first three categories and lends itself naturally to parallelism on multicore CPUs. State-of-the-art algorithms for global placement form two families: (i) force-directed placers, such as Kraftwerk2 [20], FastPlace3 [22] and RQL [23], and (ii) non-linear optimization techniques, such as APlace2 [12], NTUPlace3 [7] and mPL6 [6]. Force- directed algorithms model total net length by a quadratic function of cell locations and minimize it by solving a large sparse system of linear equations. To discourage cell overlap, forces are added pulling cells away from high-density areas. These forces are modeled by pseudopins and pseudonets, which ex- tend the original quadratic function [11]. They are updated after each linear-system solve until iterations converge. Non-linear optimization models net length by more sophisticated differentiable functions with linear asymptotic behavior which are then minimized by advanced numerical analysis techniques [12]. Cell density is modeledby functional terms, which are more accurate than forces, but also require updates after each change to placement [7], [12]. Algorithms in both categories are directly used in the industry or closely resemble those in industry placers. Tools based on non-linear optimization achieve the best results reported for academic implementations [7] and EDA vendor tools, but are significantly slower, which is problematic for modern flat SoC placement instances with tens of millions of movable objects. To scale the basic non-linear optimization framework, all tools in this family employ netlist clustering and multilevel extensions, sometimes at the cost of solution quality. Such multilevel placers perform many sequen- tial steps, obstructing efficient parallelization. More- over, clustering and refinement do not fully benefit from modern multicore CPUs. Due to their complexity, multilevel placers are...

Website: www.eecs.umich.edu | Filesize: -
No of Page(s): 8
Download SimPL: An Effective Placement Algorithm - University of Michigan.pdf