ePlace: Electrostatics Based Placement Using Nesterov's Method

related works: ePlace-MS, ePlace-3D

Authors: Jingwei Lu and Chung-Kuan Cheng
Affiliation: Department of Computer Science and Engineering, University of California, San Diego, USA
Contact: francesco DOT ljw AT gmail DOT com

[Animation]           [Publication]           [Overview]           [Results]           [Download]           [License]


Animation

Electrostatic field animation of density-driven
placement progression of ISPD05 ADAPTEC1 with
221K nets, 63 fixed macros and movable standard cells.
Cell layout animation of wirelength & density-driven
placement progression of ISPD05 ADAPTEC1 with 221K
nets, 63 fixed macros and 210K movable standard cells.


Related Publications

  • J. Lu, H. Zhuang, P. Chen, H. Chang, C.-C. Chang, Y.-C. Wong, L. Sha, D. J.-H. Huang, Y. Luo, C.-C. Teng and C.-K. Cheng, "ePlace-MS: Electrostatics based Placement for Mixed-Size Circuits", IEEE TCAD 34(5) (2015), pp. 685-698. (pdf).
  • J. Lu, P. Chen, C.-C. Chang, L. Sha, D. J.-H. Huang, C.-C. Teng and C.-K. Cheng, "ePlace: Electrostatics based Placement using Fast Fourier Transform and Nesterov's Method", ACM TODAES 20(2) (2015), article 17. (pdf).
  • J. Lu, P. Chen, C.-C. Chang, L. Sha, D. J.-H. Huang, C.-C. Teng and C.-K. Cheng, "ePlace: Electrostatics Based Placement Using Nesterov's Method", DAC 2014, pages 1-6. (pdf).
  • J. Lu, P. Chen, C.-C. Chang, L. Sha, D. J.-H. Huang, C.-C. Teng and C.-K. Cheng, "FFTPL: An Analytic Placement Algorithm Using Fast Fourier Transform for Density Equalization", ASICON 2013, pages 1-4. (pdf).


  • Placement Overview

  • develop a novel density function eDensity based on the analogy between placement and electrostatic system
  • propose a modified Poisson's equation with Neumann boundary condition to enforce placement legality
  • propose a fast numerical solution to the Poisson's equation using spectral methods, which well satisfies the boundary condition
  • use Nesterov's method to solve the nonlinear placement problem with runtime step length prediction to resolve runtime bottleneck
  • The entire flow of ePlace.


    Experiments and Results

    We implement ePlace using C programming language. Our program together with other placers are all executed in single-thread mode on a Linux machine with Intel i7 920 2.67GHz CPU and 12GB memory. Experiments are conducted on ISPD 2005 and ISPD 2006 benchmarks for standard-cell based placement (with mLG and cGP disabled in ePlace) Solution quality is evaluated by respective official scripts.

    In ePlace, we DO NOT allow flipping or rotation of standard cells.

    For your convenience please find all the three benchmark suites (ISPD05 and ISPD06) respective official evaluation scripts (ISPD05 and ISPD06).

    We include ten previous placement algorithms for experiments and performance comparison, namely, Capo10.5, FastPlace3.0, RQL, MAPLE, ComPLx, BonnPlace, POLAR, APlace3, NTUplace3, mPL6.

    HPWL (e6) results on ISPD 2005 benchmark suite evaluated by official scripts.
    Categories
    Min-Cut
    Quadratic
    Nonlinear
    Placers
    Capo10.5 FastPlace3.0 RQL MAPLE ComPLx BonnPlace POLAR APlace3 NTUplace3 mPL6 ePlace
    Benchmarks # Cells tgt Den HPWL HPWL HPWL HPWL HPWL HPWL HPWL HPWL HPWL HPWL HPWL Solution
    ADAPTEC1211K1.088.7078.3477.8276.3677.7376.8777.2178.3580.2977.9374.61 sol
    ADAPTEC2255K1.0103.5093.4788.5186.9588.8486.3686.1695.6890.1892.0484.83 sol
    ADAPTEC3452K1.0235.78213.48210.96209.78203.45202.00201.30218.52233.77214.16194.51 sol
    ADAPTEC4 496K 1.0205.97196.88188.86179.91183.16181.53182.37209.28215.02 193.89 179.02 sol
    BIGBLUE1 278K 1.0107.58 96.23 94.98 93.74 94.41 94.8594.67100.02 98.65 96.80 90.98 sol
    BIGBLUE2 558K 1.0163.75154.89150.03144.55145.37144.21143.85153.75158.27152.34 141.97 sol
    BIGBLUE3 1097K 1.0407.28369.19323.09323.05337.72317.71324.53411.59346.33344.25 308.81 sol
    BIGBLUE4 2177K 1.0952.20834.05797.66775.71788.30781.79781.06871.29829.09829.44 756.07 sol
    Average HPWL
    21.14% 10.00% 5.40% 3.21% 4.50% 2.83% 3.08% 14.33% 12.05% 8.33% 0.00%
    Average Runtime
    8.94× 0.53× 0.91× 2.84× 0.52× 3.05× 0.52× 9.13× 1.40× 3.78× 1.00×


    Scaled HPWL (e6) results on ISPD 2006 benchmark suite evaluated by official scripts.
    For NEWBLUE1, please use the respective MMS script to evaluate its density overflow.
    Categories
    Min-Cut
    Quadratic
    Nonlinear
    Placers
    Capo10.5 FastPlace3.0 RQL MAPLE ComPLx BonnPlace POLAR APlace3 NTUplace3 mPL6 ePlace
    Benchmarks # Cells tgt Den HPWL HPWL HPWL HPWL HPWL HPWL HPWL HPWL HPWL HPWL Solution
    ADAPTEC5 843K 0.5 494.64472.72443.28407.33415.77438.47520.97444.41428.31397.53 sol
    NEWBLUE1 330K 0.8 98.48 74.11 64.43 69.25 64.75 67.52 73.3161.01 72.62 62.31 sol
    NEWBLUE2 442K 0.9 309.53206.04199.60191.66193.06191.25198.24194.80201.91182.69 sol
    NEWBLUE3 494K 0.8 361.25297.46269.33268.07273.42271.28273.64275.08285.26266.80 sol
    NEWBLUE4 646K 0.5 362.40308.35308.75282.49292.82305.14384.12296.62298.20276.13 sol
    NEWBLUE5 1233K 0.5 659.57621.47537.49515.04507.74521.85613.86537.92535.80492.62 sol
    NEWBLUE6 1255K 0.8 668.66549.87515.69494.82501.05512.06522.73534.96523.47464.44 sol
    NEWBLUE7 2508K 0.8 1518.751105.431057.801032.601041.211045.201098.901096.161085.68989.96 sol
    Average HPWL
    43.73% 16.25% 7.99% 4.59% 4.86% 7.16% 18.38% 7.74% 10.11% 0.00%
    Average Runtime
    6.68× 0.59× N/A N/A 0.55× 0.69× 10.21× 1.63× 3.71× 1.00×


    Application for software

    Please fill out the following agreement form. We will email you the placement software upon receiving your submission of agreement.

    First name:

    Last name:

    Email:

    Affiliation:

    Purpose of usage:

    I agree with the following license terms.


    License terms

    READ THIS LICENSE AGREEMENT CAREFULLY BEFORE USING THIS PRODUCT. BY USING THIS PRODUCT YOU INDICATE YOUR ACCEPTANCE OF THE TERMS OF THE FOLLOWING AGREEMENT. THESE TERMS APPLY TO YOU AND ANY SUBSEQUENT LICENSEE OF THIS PRODUCT.

    License Agreement for ePlace.

    Copyright (c) 2014 by Jingwei Lu and Chung-Kuan Cheng ("Authors")
    http://vlsi-cuda.ucsd.edu/~ljw/ePlace/ ("URL")
    All rights reserved

    Redistribution and use in source and binary forms, with or without modification, are permitted provided that the following conditions are met:

  • Redistributions of source code must retain the above copyright notice, this list of conditions and the following disclaimer.
  • Redistributions in binary form must reproduce the above copyright notice, this list of conditions and the following disclaimer in the documentation and/or other materials provided with the distribution.
  • Neither the names nor any trademark of the Authors may be used to endorse or promote products derived from this software without specific prior written permission.
  • Use is limited to academic research groups only. Users who are interested in industry or commercial purposes must notify Authors and request separate license agreement.
  • Redistributions of the Code in executable form, or a program dependent upon the Code, must show at launch a prominent display (e.g., splash screen or banner text) of the copyright information, including Authors' attribution, shown above.


  • THIS FREE SOFTWARE IS PROVIDED BY THE AUTHOR "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR ANY CONTRIBUTOR BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, EFFECTS OF UNAUTHORIZED OR MALICIOUS NETWORK ACCESS; PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.