ePlace-MS: Electrostatics based Placement for Mixed-Size circuits

Authors: Jingwei Lu, Hao Zhuang and Chung-Kuan Cheng
Affiliation: Department of Computer Science and Engineering, University of California, San Diego, USA
Contact: jlu AT cs DOT ucsd DOT edu, ckcheng AT ucsd DOT edu

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


Animation

Electrostatic field animation of density-only placement
progression on MMS ADAPTEC1 with 221K nets, 63
movable macros and 210K movable standard cells.
Cell layout animation of wirelength & density-driven
placement progression on MMS ADAPTEC1 with 221K
nets, 63 movable 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-MS.
    Total HPWL and object overlap (OVLP) at different stages
    and iterations of placement on MMS ADAPTEC1.


    Experiments and Results

    We implement ePlace-MS 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 MMS benchmarks for modern mixed-size placement. Solution quality is evaluated by respective official scripts.

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

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

    We include seven previous mixed-size placement algorithms for experiments and performance comparison, namely, Capo10.5, FastPlace3.0, ComPLx, POLAR, NTUplace3, mPL6, FLOP.

    HPWL and scaled HPWL (e6) results on MMS benchmark suite evaluated by official scripts.
    Here NR="no rotation or flipping of standard cells or macros".
    Categories
    Constructive
    One-Stage
    Placers
    Capo10.5 FLOP-NR FLOP FastPlace3.0 ComPLx POLAR mPL6 NTUplace3-NR NTUplace3 ePlace-MS
    Benchmarks # Marcos tgt Den HPWL HPWL HPWL HPWL HPWL HPWL HPWL HPWL HPWL HPWL Solution
    ADAPTEC1 63 1.0 84.77 77.18 76.83 82.39 79.05 92.17 77.84 75.92 75.55 67.15 sol
    ADAPTEC2 127 1.0 92.61 87.17 84.14 88.53 99.11 149.43 88.40 84.89 78.50 77.37 sol
    ADAPTEC3 58 1.0202.37 182.21 175.99187.98 175.78 197.48180.64 170.88 169.74 164.50 sol
    ADAPTEC4 69 1.0202.38 166.55 161.68187.50 156.75 175.19162.02 167.13 166.68 148.38 sol
    BIGBLUE1 32 1.0112.58 95.45 94.92 104.91 96.18 99.12 99.36 96.42 96.57 86.82 sol
    BIGBLUE2 959 1.0149.54 150.66 153.02 145.89 147.19 157.72144.37 148.12 147.17 130.18 sol
    BIGBLUE3 2549 1.0583.37 372.79 346.24 400.40 344.63 420.28319.63 324.39 338.47 302.29 sol
    BIGBLUE4 199 1.0915.37 807.53 777.84 775.43 772.53 814.07804.00 797.17 799.66 657.92 sol
    ADAPTEC5 76 0.5565.88 381.83 357.83 338.77 338.67 380.45376.30 295.24 294.24 315.76 sol
    NEWBLUE1 64 0.8110.54 73.36 67.97 73.91 65.26 70.68 66.93 61.13 61.25 62.56 sol
    NEWBLUE2 3748 0.9303.25 231.94 187.40 197.15 187.87 197.65179.18 164.27 163.76 166.59 sol
    NEWBLUE3 51 0.81282.19344.71 345.99 325.72 269.47 601.17415.86 N/A 280.92 304.24 sol
    NEWBLUE4 81 0.5300.69 256.91 256.54 270.70 256.97 277.60277.69 231.59 229.36 229.95 sol
    NEWBLUE5 91 0.5570.32 516.71 510.83 500.09 453.05 450.69515.49 414.81 420.46 393.21 sol
    NEWBLUE6 74 0.8609.16 502.24 493.64 512.19 452.83 475.78482.44 471.51 474.86 410.04 sol
    NEWBLUE7 161 0.81481.451113.071078.181016.101010.001107.591038.66 N/A 1100.84897.81 sol
    Average HPWL
    64.42% 18.92% 14.31% 18.22% 10.90% 31.46% 16.13% 7.40% 7.13% 0.00%
    Average Runtime
    14.69× 2.02× 2.14× 0.37× 1.15× 0.67× 6.34× 0.81× 1.05× 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-MS

    Copyright (c) 2014 by Jingwei Lu and Chung-Kuan Cheng ("Authors")
    http://vlsi-cuda.ucsd.edu/~ljw/ePlace-MS/ ("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.