UC San Diego

We develop a flat, analytic and nonlinear placement algorithm ePlace, which is more effective, generalized, simpler and faster than previous works. Based on the analogy between placement instance and electrostatic system, we develop a novel placement density function eDensity, which models every object as positive charge and the density cost as the potential energy of the electrostatic system. The electric potential and field distribution are coupled with density using a modified Poisson's equation, which is numerically solved by spectral methods using fast Fourier transform (FFT). Rather than conjugate gradient (CG) method by previous placers, we propose to use Nesterov's method for faster convergence. The efficiency bottleneck on line search is resolved by steplength prediction through an equation of Lipschitz constant. Through empirical validation, ePlace outperforms all prior placers with better quality and efficiency. On average of ISPD 2005 benchmarks, ePlace outperforms the leading placer BonnPlace with 2.83% shorter wirelength and runs 3.05x faster. On average of ISPD 2006 benchmarks, ePlace outperforms the leading placer MAPLE with 4.59% shorter wirelength and runs 2.84x faster. Based on the above placement prototype, we develop ePlace-MS, an electrostatics based placement algorithm for mixed-size circuits. The density function eDensity is extended to handle the mixed-size placement. We conduct detailed analysis on the correctness of the gradient formulation and the numerical solution, as well as the rationale of density equalization with its advantages over prior density functions. Nesterov's method is shown with high yet stable performance over mixed-size circuits. The steplength prediction methodology is enhanced with backtracking strategy to prevent overestimation. A nonlinear preconditioner is developed to minimize the topological and physical differences between large macros and standard cells. Besides, we devise a simulated annealer for direct macro-layout legalization. All the above innovations are integrated into our mixed-size placement prototype ePlace-MS, which outperforms all the related works in literature with better quality and efficiency. Compared to the leading-edge mixed-size placer NTUplace3, ePlace-MS produces up to 22.98% and on average 8.22% shorter wirelength over all the sixteen modern mixed -size (MMS) benchmark circuits with the same runtime